BZOJ 3196: Tyvj 1730 二逼平衡树

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作： 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)));
            }
        }
    }
}

日期： 2016-11-17

标签： BZOJ 线段树 树套树 树状数组

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/80/ 查看。