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=500010, seed=233333, inf=1e9+1;
struct treap{int sum, mx, rnd, size, ls, rs;}tree[maxn];
int n, x, tott, root, ans;
void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}
inline void build(int &x)
{
    tree[x=++tott].rnd=rand()<<15|rand();
    tree[x].sum=tree[x].mx=tree[x].size=1;
}
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+1;
    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=0, r=x;
    else if(k==tree[x].size) l=x, r=0;
    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-1), 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(0, tree[x].mx)+1; 
    merge(x, x, tmp); merge(root, x, y);
    return ans=max(ans, tree[tmp].sum);
}
int main()
{
    srand(seed); read(n); tree[0].mx=-inf; tree[0].rnd=inf;
    for(int i=1;i<=n;i++) read(x), printf("%d\n", solve(x)); 
}

View Code

　　貌似还可以用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=500010;
int n, mx, ans, x;
int tree1[maxn], tree2[maxn], pos[maxn], p[maxn], f[maxn];
void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', 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=0; for(;x;x-=x&-x) sum=max(sum, tree2[x]); return sum;}
int main()
{
    read(n);
    for(mx=1;mx<n;mx<<=1);
    for(int i=1;i<=mx;i++) 
        tree1[i]+=(i<=n), i+(i&-i)<=mx&&(tree1[i+(i&-i)]+=tree1[i]);
    for(int i=1;i<=n;i++) read(p[i]), p[i]++;
    for(int i=n;i;i--)
    {
        int l=0, r=mx, k=0;
        while(l<r)
        {
            int mid=(l+r)>>1;
            k+=tree1[mid];
            if(k<p[i]) l=mid+1;
            else k-=tree1[mid], r=mid;
        }
        pos[l]=i;
        add1(l, -1); 
    }
    for(int i=1, tmp;i<=n;i++) 
        f[pos[i]]=query2(pos[i]-1)+1, add2(pos[i], f[pos[i]]);
    for(int i=1;i<=n;i++) ans=max(ans, f[i]), printf("%d\n", ans);
}

View Code

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

推荐阅读