bzoj3173: [Tjoi2013]最长上升子序列（fhqtreap）

　　这题用fhqtreap可以在线。

　　fhqtreap上维护以i结尾的最长上升子序列，数字按从小到大加入， 因为前面的数与新加入的数无关， 后面的数比新加入的数小， 所以新加入的数对原序列其他数的值没有影响。

　　然后就可以直接fhqtreap模拟啦

　　忘记所有答案取max WA了半天T T

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#define lt tree[x].ls

#define rt tree[x].rs

using namespace std;

const int maxn=, seed=, inf=1e9+;

struct treap{int sum, mx, rnd, size, ls, rs;}tree[maxn];

int n, x, tott, root, ans;

void read(int &k)

{

    int f=; k=; char c=getchar();

    while(c<'' || c>'') c=='-' && (f=-), c=getchar();

    while(c<='' && c>='') k=k*+c-'', c=getchar();

    k*=f;

}

inline void build(int &x)

{

    tree[x=++tott].rnd=rand()<<|rand();

    tree[x].sum=tree[x].mx=tree[x].size=;

}

inline int max(int a, int b){return a>b?a:b;}

inline void up(int x)

{

    if(!x) return;

    tree[x].size=tree[lt].size+tree[rt].size+;

    tree[x].mx=max(tree[x].sum, max(tree[lt].mx, tree[rt].mx));

}

void split(int x, int &l, int &r, int k)

{

    if(!k) l=, r=x;

    else if(k==tree[x].size) l=x, r=;

    else if(k<=tree[lt].size) r=x, split(lt, l, lt, k), up(x);

    else l=x, split(rt, rt, r, k-tree[lt].size-), up(x);

}

void merge(int &x, int l, int r)

{

    if(!l || !r) x=l+r;

    else if(tree[l].rnd<tree[r].rnd) x=l, merge(rt, rt, r), up(x);

    else x=r, merge(lt, l, lt), up(x);

}

inline int solve(int pos)

{

    int x, y, tmp;

    build(tmp); split(root, x, y, pos);

    tree[tmp].sum=tree[tmp].mx=max(, tree[x].mx)+;

    merge(x, x, tmp); merge(root, x, y);

    return ans=max(ans, tree[tmp].sum);

}

int main()

{

    srand(seed); read(n); tree[].mx=-inf; tree[].rnd=inf;

    for(int i=;i<=n;i++) read(x), printf("%d\n", solve(x));

}

　　貌似还可以用BIT， 过会再补

　　先把所有数设成1，1表示<=x的数，0表示>x的数，然后从n到1扫一遍，对于每个要求的位置pos，就是找到前缀为pos的位置插入，至于怎么找到前缀为pos的位置，就用BIT求第k大的方法就好了。

　　求出原序列之后， 求每一个数结尾的LIS就好了

　　注意：BIT求第k大的时候add是单点修改

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

using namespace std;

const int maxn=;

int n, mx, ans, x;

int tree1[maxn], tree2[maxn], pos[maxn], p[maxn], f[maxn];

void read(int &k)

{

    int f=; k=; char c=getchar();

    while(c<'' || c>'') c=='-' && (f=-), c=getchar();

    while(c<='' && c>='') k=k*+c-'', c=getchar();

    k*=f;

}

inline int max(int a, int b){return a>b?a:b;}

inline void add1(int x, int delta){for(;x<=mx;x+=x&-x) tree1[x]+=delta;}

inline void add2(int x, int delta){for(;x<=n;x+=x&-x) tree2[x]=max(tree2[x], delta);}

inline int query2(int x){int sum=; for(;x;x-=x&-x) sum=max(sum, tree2[x]); return sum;}

int main()

{

    read(n);

    for(mx=;mx<n;mx<<=);

    for(int i=;i<=mx;i++)

        tree1[i]+=(i<=n), i+(i&-i)<=mx&&(tree1[i+(i&-i)]+=tree1[i]);

    for(int i=;i<=n;i++) read(p[i]), p[i]++;

    for(int i=n;i;i--)

    {

        int l=, r=mx, k=;

        while(l<r)

        {

            int mid=(l+r)>>;

            k+=tree1[mid];

            if(k<p[i]) l=mid+;

            else k-=tree1[mid], r=mid;

        }

        pos[l]=i;

        add1(l, -);

    }

    for(int i=, tmp;i<=n;i++)

        f[pos[i]]=query2(pos[i]-)+, add2(pos[i], f[pos[i]]);

    for(int i=;i<=n;i++) ans=max(ans, f[i]), printf("%d\n", ans);

}