BZOJ 1901 Dynamic Rankings

明明是树状数组套主席树裸题我为什么要写权值线段树套平衡树……

如果是全局的查询就用权值线段树对吧。
那么这里考虑套一个平衡树来维护下标。

由于是 FHQ Treap，
成功地卡常卡不过……

此代码无法在 BZOJ 上通过。

代码：

#include <cstdio>
#include <cstdlib>
#define ls(p) p->lson
#define rs(p) p->rson
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    while(ch < '0' || ch > '9')
        w |= ch == '-',ch = gc();
    while(ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
    w ? x = -x : x;
}

const int N = 1e5;
const int A = 1e9;
int n,m;
int a[N + 10];
int seg_tot,segroot;
int ls[(N << 8) + 10],rs[(N << 8) + 10];
struct node
{
    int val,rnd,sz;
    node *lson,*rson;
} *rt[(N << 8) + 10];
inline node *new_node(int v)
{
    node *ret = new node();
    ret->val = v;
    ret->rnd = rand();
    ret->sz = 1;
    return ret;
}
inline void up(node *p)
{
    p->sz = 1;
    if(ls(p))
        p->sz += ls(p)->sz;
    if(rs(p))
        p->sz += rs(p)->sz;
}
node *merge(node *x,node *y)
{
    if(!x || !y)
        return !x ? y : x;
    if(x->rnd < y->rnd)
    {
        rs(x) = merge(rs(x),y);
        up(x);
        return x;
    }
    else
    {
        ls(y) = merge(x,ls(y));
        up(y);
        return y;
    }
}
void split(node *p,int v,node *&x,node *&y)
{
    if(!p)
    {
        x = y = NULL;
        return ;
    }
    if(p->val <= v)
        x = p,split(rs(p),v,rs(p),y);
    else
        y = p,split(ls(p),v,x,ls(p));
    up(p);
}
void update(int x,int v,int k,int &p,int tl,int tr)
{
    if(!p)
        p = ++seg_tot;
    node *a,*b,*c;
    if(~k)
    {
        split(rt[p],x,a,b);
        rt[p] = merge(merge(a,new_node(x)),b);
    }
    else
    {
        split(rt[p],x,a,c);
        split(a,x - 1,a,b);
        if(b)
            delete b;
        rt[p] = merge(a,c);
    }
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    if(v <= mid)
        update(x,v,k,ls[p],tl,mid);
    else
        update(x,v,k,rs[p],mid + 1,tr);
}
int query(int l,int r,int k,int p,int tl,int tr)
{
    if(tl == tr)
        return tl;
    node *a,*b,*c;
    int cnt = 0;
    split(rt[ls[p]],r,a,c);
    split(a,l - 1,a,b);
    if(b)
        cnt = b->sz;
    rt[ls[p]] = merge(merge(a,b),c);
    int mid = tl + tr >> 1;
    if(k <= cnt)
        return query(l,r,k,ls[p],tl,mid);
    else
        return query(l,r,k - cnt,rs[p],mid + 1,tr);
}
int main()
{
    read(n),read(m);
    for(register int i = 1;i <= n;++i)
        read(a[i]),update(i,a[i],1,segroot,0,A);
    char op;
    int l,r,v;
    while(m--)
    {
        op = 0;
        while(op ^ 'Q' && op ^ 'C')
            op = gc();
        if(op == 'Q')
        {
            read(l),read(r),read(v);
            printf("%d\n",query(l,r,v,segroot,0,A));
        }
        else
        {
            read(l),read(v);
            update(l,a[l],-1,segroot,0,A);
            a[l] = v;
            update(l,a[l],1,segroot,0,A);
        }
    }
}