BZOJ3065 带插入区间Ｋ小值（替罪羊树套线段树）

问题描述

从前有n只跳蚤排成一行做早操，每只跳蚤都有自己的一个弹跳力a[i]。跳蚤国王看着这些跳蚤国欣欣向荣的情景，感到非常高兴。这时跳蚤国王决定理性愉悦一下，查询区间k小值。

他每次向它的随从伏特提出这样的问题: 从左往右第x个到第y个跳蚤中，a[i]第k小的值是多少。 这可难不倒伏特，他在脑袋里使用函数式线段树前缀和的方法水掉了跳蚤国王的询问。

这时伏特发现有些跳蚤跳久了弹跳力会有变化，有的会增大，有的会减少。 这可难不倒伏特，他在脑袋里使用树状数组套线段树的方法水掉了跳蚤国王的询问。（orz 主席树）

这时伏特发现有些迟到的跳蚤会插入到这一行的某个位置上，他感到非常生气，因为……他不会做了。 请你帮一帮伏特吧。

快捷版题意：带插入、修改的区间k小值在线查询。

输入格式

第一行一个正整数n，表示原来有n只跳蚤排成一行做早操。

第二行有n个用空格隔开的非负整数，从左至右代表每只跳蚤的弹跳力。

第三行一个正整数q，表示下面有多少个操作。

下面一共q行，一共三种操作对原序列的操作：（假设此时一共m只跳蚤）

Q x y k: 询问从左至右第x只跳蚤到从左至右第y只跳蚤中，弹跳力第k小的跳蚤的弹跳力是多少。(1 <= x <= y <= m, 1 <= k <= y - x + 1)

M x val: 将从左至右第x只跳蚤的弹跳力改为val。 (1 <= x <= m)

I x val: 在从左至右第x只跳蚤的前面插入一只弹跳力为val的跳蚤。即插入后从左至右第x只跳蚤是我刚插入的跳蚤。 (1 <= x <= m + 1)

为了体现在线操作，设lastAns为上一次查询的时候程序输出的结果，如果之前没有查询过，则lastAns = 0。

则输入的时候实际是：

Q _x _y _k ——> 表示 Q _x^lastAns _y^lastAns _k^lastAns

M _x _val ——> 表示 M _x^lastAns _val^lastAns

I _x _val ——> 表示 I _x^lastAns _val^lastAns

简单来说就是操作中输入的整数都要异或上一次询问的结果进行解码。

输出格式

对于每个询问输出回答，每行一个回答。

样例输入

10
10 5 8 28 0 19 2 31 1 22
30
I 6 9
M 1 11
I 8 17
M 1 31
M 6 26
Q 2 7 6
I 23 30
M 31 7
I 22 27
M 26 18
Q 26 17 31
I 5 2
I 18 13
Q 3 3 3
I 27 19
Q 23 23 30
Q 5 13 5
I 3 0
M 15 27
Q 0 28 13
Q 3 29 11
M 2 8
Q 12 5 7
I 30 19
M 11 19
Q 17 8 29
M 29 4
Q 3 0 12
I 7 18
M 29 27

样例输出

28
2
31
0
14
15
14
27
15
14

提示

原序列长度 <= 35000

插入个数 <= 35000，修改个数 <= 70000，查询个数 <= 70000 ,0 <= 每时每刻的权值 <= 70000

---

这是一道经典题了，推荐看 $\rm vfk$ 官方题解

我写的替罪羊树套权值线段树的做法

具体的说就是用替罪羊树维护序列，每个节点上挂一颗权值线段树记该节点及子节点中出现的权值

那么建树的时候直接拍扁之后暴力建就行了，一次建树是 $n\log^2n$ 的，可以接受，据说可以线段树合并少一个 $\log$

然后修改就直接做， $O(\log^2n)$

插入的话也是直接在平衡树里找位置，然后沿着链往线段树里修改就行了， $O(\log^2n)$

然后过于不平衡的时候就直接重建就行了，均摊下来 $O(n\log^3 n)$

询问的时候像主席树那样把所有会用到的线段树的根先提出来，然后在线段树上二分， $O(\log^2 n)$

然后要特别注意垃圾回收，不然很容易爆掉

---

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 70005
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
inline int _R()
{
    char t=GC;int x=0;
    while(t<48||t>57)t=GC;
    for(;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
    return x;
}
inline char _C()
{
    char t=GC;
    while(t<'A'||t>'Z')t=GC;
    return t;
}
const int U=70000;
int n,q,a[N],tot;
struct node
{
    node *ls,*rs;
    int v;
}seg[N*128],*seg_tl,*seg_null,*seg_pool[N*128],*use[N];int ty[N],dt,seg_tp;
struct nodd
{
    nodd *ls,*rs;node *rt;
    int v,sz;
}scape[N],**Rt,*rt,*tl,*null,*pool[N];int tp;
void Init()
{
    seg_tl=seg_null=seg;
    seg_null->ls=seg_null->rs=seg_null;
    rt=tl=null=scape;Rt=&null;
    null->ls=null->rs=null;
    null->rt=seg_null;
}
//seg
node *New()
{
    node *p=seg_tp?seg_pool[seg_tp--]:++seg_tl;
    p->ls=p->rs=seg_null;p->v=0;return p;
}
void del(node *&p)
{
    if(p==seg_null)return;
    seg_pool[++seg_tp]=p;
    del(p->ls);del(p->rs);
    p=seg_null;
}
void modify(node *&p,int l,int r,int x,int d)
{
    if(p==seg_null)p=New();p->v+=d;
    if(p->v==0){del(p);return;}
    if(l==r)return;
    int mid=l+r>>1;
    if(x<=mid)modify(p->ls,l,mid,x,d);
    else modify(p->rs,mid+1,r,x,d);
}
//scape
nodd *New(int x)
{
    nodd *p=tp?pool[tp--]:++tl;
    p->ls=p->rs=null;
    p->sz=1;p->v=x;
    p->rt=seg_null;
    return p;
}
void update(nodd *p){p->sz=p->ls->sz+p->rs->sz+1;}
int modify(nodd *p,int x,int k)
{
    modify(p->rt,0,U,k,1);int t;
    if(x==p->ls->sz+1)
    {
        modify(p->rt,0,U,p->v,-1);
        int t=p->v;p->v=k;return t;
    }
    if(x<=p->ls->sz)t=modify(p->ls,x,k);
    else t=modify(p->rs,x-p->ls->sz-1,k);
    modify(p->rt,0,U,t,-1);return t;
}
void build(nodd *&p,int l,int r)
{
    int mid=l+r>>1;
    p=New(a[mid]);
    for(int i=l;i<=r;i++)modify(p->rt,0,U,a[i],1);
    if(l<mid)build(p->ls,l,mid-1);
    if(mid<r)build(p->rs,mid+1,r);
    update(p);
}
void del(nodd *p)
{
    if(p==null)return;
    del(p->ls);
    a[++tot]=p->v;del(p->rt);
    pool[++tp]=p;
    del(p->rs);
}
void rebuild()
{
    tot=0;del(*Rt);
    build(*Rt,1,tot);
    Rt=&null;
}
void insert(nodd *&p,int x,int k)
{
    if(p==null){p=New(k);modify(p->rt,0,U,k,1);return;}
    if(p->ls->sz>=x)
    {
        insert(p->ls,x,k);
        if(p->ls->sz>=3*p->sz>>2)Rt=&p;
    }
    else
    {
        insert(p->rs,x-p->ls->sz-1,k);
        if(p->rs->sz>=3*p->sz>>2)Rt=&p;
    }
    modify(p->rt,0,U,k,1);update(p);
}
void getrt(nodd *p,int k,int f)
{
    if(p==null||k==0)return;
    if(k==p->sz){use[++dt]=p->rt;ty[dt]=f;return;}
    if(k<=p->ls->sz)getrt(p->ls,k,f);
    else
    {
        use[++dt]=p->rt;ty[dt]=f;
        use[++dt]=p->rs->rt;ty[dt]=-f;
        getrt(p->rs,k-p->ls->sz-1,f);
    }
}
int getans(int x,int y,int k)
{
    int l=0,r=U;dt=0;
    getrt(rt,y,1);getrt(rt,x-1,-1);
    while(l<r)
    {
        int mid=l+r>>1;int sum=0;
        for(int i=1;i<=dt;i++)sum+=ty[i]*use[i]->ls->v;
        if(sum>=k)
        {
            for(int i=1;i<=dt;i++)use[i]=use[i]->ls;
            r=mid;
        }
        else
        {
            for(int i=1;i<=dt;i++)use[i]=use[i]->rs;
            k-=sum;l=mid+1;
        }
    }
    return l;
}
int main()
{
    int i,j,k,x,y,z,las=0;char c;
    n=_R();
    for(i=1;i<=n;i++)a[i]=_R();
    q=_R();
    Init();build(rt,1,n);
    for(i=1;i<=q;i++)
    {
        c=_C();
        if(c=='M')
        {
            x=_R();y=_R();
            x^=las;y^=las;
            modify(rt,x,y);
        }
        if(c=='Q')
        {
            x=_R();y=_R();z=_R();
            x^=las;y^=las;z^=las;
            printf("%d\n",las=getans(x,y,z));
        }
        if(c=='I')
        {
            x=_R();y=_R();
            x^=las;y^=las;x--;
            insert(rt,x,y);
            if(*Rt!=null)rebuild();
        }
    }
}