BZOJ 3196: Tyvj 1730 二逼平衡树

Description

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
5.查询k在区间内的后继(后继定义为大于x，且最小的数)

Input

第一行两个数 n,m 表示长度为n的有序序列和m个操作
第二行有n个数，表示有序序列
下面有m行，opt表示操作标号
若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继

Output

对于操作1,2,4,5各输出一行，表示查询结果

Sample Input

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

Sample Output

2
4
3
4
9

HINT

1.n和m的数据范围：n,m<=50000
2.序列中每个数的数据范围：[0,1e8]
3.虽然原题没有，但事实上5操作的k可能为负数

Solution

外层树状数组，内层值域线段树，在每个节点记count,修改时分别修改，查询时用r和l-1对应的一大堆节点做差（有点像主席树）

Code

#include<bits/stdc++.h>
typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
#define xx first
#define yy second
template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline void repr(T &a,T b){if(a<b)a=b;}
template<typename T> inline void repl(T &a,T b){if(a>b)a=b;}
template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define lb(x) ((x)&(-(x)))
#define sqr(x) ((x)*(x))
struct node
{
    node *lc,*rc;
    int cnt;
    node();
}_null,*null=&_null;
node::node(){lc=rc=null;cnt=0;}
int pf;
void erase(node *x)
{
    if(x->lc!=null)erase(x->lc);
    if(x->rc!=null)erase(x->rc);
    delete x;
}
void modify(node *&x,int l,int r,int p,int v)
{
    if(x==null)x=new node;
    x->cnt+=v;
    if(!x->cnt)
    {
        erase(x);
        x=null;
        return;
    }
    if(l!=r)
    {
        int f=(l+r)/2;
        if(p<=f)
            modify(x->lc,l,f,p,v);
        else
            modify(x->rc,f+1,r,p,v);
    }
}
struct group
{
    node *x[50];
    int mul[50],sz;
    inline int cnt()
    {
        int ret=0;
        for(int i=0;i<sz;i++)ret+=x[i]->cnt*mul[i];
        return ret;
    }
    inline group* lc(group *f)
    {
        f->sz=sz;
        for(int i=0;i<sz;i++)f->x[i]=x[i]->lc,f->mul[i]=mul[i];
        return f;
    }
    inline group* rc(group *f)
    {
        f->sz=sz;
        for(int i=0;i<sz;i++)f->x[i]=x[i]->rc,f->mul[i]=mul[i];
        return f;
    }
};
int cnt(group *x,int l,int r,int ql,int qr)
{
    if(l==ql&&r==qr)return x->cnt();
    int t=(l+r)/2,ans=0;
    group ch;
    if(ql<=t)ans+=cnt(x->lc(&ch),l,t,ql,min(t,qr));
    if(qr>t)ans+=cnt(x->rc(&ch),t+1,r,max(ql,t+1),qr);
    return ans;
}
int kth(group *x,int l,int r,int rk)
{
    if(l==r)return l;
    group ch;
    x->lc(&ch);
    int lcnt;
    if((lcnt=ch.cnt())>=rk)
        return kth(&ch,l,(l+r)/2,rk);
    else
        return kth(x->rc(&ch),(l+r)/2+1,r,rk-lcnt);
}
int gmax(group *x,int l,int r,int p)
{
    if(!x->cnt())return 0;
    if(l==r)return l;
    int t=(l+r)/2;
    group ch;
    if(p<=t)return gmax(x->lc(&ch),l,t,p);
    if(r==p)
    {
        x->rc(&ch);
        if(ch.cnt())return gmax(&ch,t+1,r,p);
        return gmax(x->lc(&ch),l,t,t);
    }
    return max(gmax(x->lc(&ch),l,t,t),gmax(x->rc(&ch),t+1,r,p));
}
int gmin(group *x,int l,int r,int p)
{
    if(!x->cnt())return 0x7fffffff;
    if(l==r)return l;
    int t=(l+r)/2;
    group ch;
    if(p>t)return gmin(x->rc(&ch),t+1,r,p);
    if(l==p)
    {
        x->lc(&ch);
        if(ch.cnt())return gmin(&ch,l,t,p);
        return gmin(x->rc(&ch),t+1,r,t+1);
    }
    return min(gmin(x->lc(&ch),l,t,p),gmin(x->rc(&ch),t+1,r,t+1));
}
#define nl 0
#define nr 100000001
node *root[50001];
int v[50001];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)
        root[i]=new node;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",v+i);
        for(int j=i;j<=n;j+=lb(j))
            modify(root[j],nl,nr,v[i],1);
    }
    while(m--)
    {
        int opt,a,b,c;
        scanf("%d%d%d",&opt,&a,&b);
        if(opt==3)
        {
            for(int j=a;j<=n;j+=lb(j))
                modify(root[j],nl,nr,v[a],-1);
            v[a]=b;
            for(int j=a;j<=n;j+=lb(j))
                modify(root[j],nl,nr,v[a],1);
        }
        else
        {
            scanf("%d",&c);
            group tmp;
            tmp.sz=0;
            for(int j=b;j;j^=lb(j))
                tmp.mul[tmp.sz]=1,tmp.x[tmp.sz++]=root[j];
            for(int j=a-1;j;j^=lb(j))
                tmp.mul[tmp.sz]=-1,tmp.x[tmp.sz++]=root[j];
            if(opt==1)
            {
                printf("%d\n",cnt(&tmp,nl,nr,nl,min(nr,c-1))+1);
            }
            else if(opt==2)
            {
                printf("%d\n",kth(&tmp,nl,nr,c));
            }
            else if(opt==4)
            {
                printf("%d\n",gmax(&tmp,nl,nr,min(nr,c-1)));
            }
            else
            {
                printf("%d\n",gmin(&tmp,nl,nr,max(nl,c+1)));
            }
        }
    }
}