bzoj 3065: 带插入区间K小值（分块）

Description

从前有n只跳蚤排成一行做早操，每只跳蚤都有自己的一个弹跳力a[i]。跳蚤国王看着这些跳蚤国欣欣向荣的情景，感到非常高兴。这时跳蚤国王决定理性愉悦一下，查询区间k小值。他每次向它的随从伏特提出这样的问题: 从左往右第x个到第y个跳蚤中，a[i]第k小的值是多少。
这可难不倒伏特，他在脑袋里使用函数式线段树前缀和的方法水掉了跳蚤国王的询问。
这时伏特发现有些跳蚤跳久了弹跳力会有变化，有的会增大，有的会减少。
这可难不倒伏特，他在脑袋里使用树状数组套线段树的方法水掉了跳蚤国王的询问。（orz 主席树）
这时伏特发现有些迟到的跳蚤会插入到这一行的某个位置上，他感到非常生气，因为……他不会做了。
请你帮一帮伏特吧。
快捷版题意：带插入、修改的区间k小值在线查询。

Input

第一行一个正整数n，表示原来有n只跳蚤排成一行做早操。
第二行有n个用空格隔开的非负整数，从左至右代表每只跳蚤的弹跳力。
第三行一个正整数q，表示下面有多少个操作。
下面一共q行，一共三种操作对原序列的操作：（假设此时一共m只跳蚤）
1. Q x y k: 询问从左至右第x只跳蚤到从左至右第y只跳蚤中，弹跳力第k小的跳蚤的弹跳力是多少。
    (1 <= x <= y <= m, 1 <= k <= y - x + 1)
2. M x val: 将从左至右第x只跳蚤的弹跳力改为val。
    (1 <= x <= m)
3. 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
简单来说就是操作中输入的整数都要异或上一次询问的结果进行解码。

(祝Pascal的同学早日转C++，就不提供pascal版的描述了。)

Output

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

Sample Input

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

Sample Output

28
2
31
0
14
15
14
27
15
14

HINT

此题作为一个小小的研究来搞吧～做法有很多～不知道这题究竟有多少种做法。

请自觉O(log^2n)，我故意卡块状链表，块链A了的请受我深情一拜……

A掉的同学请在Discuss里面简要说下自己的做法吧～

原序列长度 <= 35000

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

由于是OJ上的题，所以数据无梯度。为了防止卡OJ，本题只有4组数据。

我写的是分块

用的是和这位一样的方法，很遗憾的是，他被我挤出第一页了……囧

维护块的原数组和排序后数组，然后查询时二分答案，在每个块内再二分求出比mid小的数的个数。

插入啦，修改啦，暴力搞就好。

然后每个块的大小不要用根号n，会被卡，自己试下600左右比较好。

#include<cmath>
#include<cstdio>
#include<algorithm>
#define lla la;
using namespace std;
int read_p,read_ca;
inline int read(){
    read_p=;read_ca=getchar();
    while(read_ca<''||read_ca>'') read_ca=getchar();
    while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
    return read_p;
}
int n,m,a[][],b,num,la=,s[],k[][],ne[];
char ch[];
int i,j,x,c,l,r,lc,rc,li,ri;
inline bool cmp(int a,int b){
    return a<b;
}
inline int que(int i,int x){
    int l=,r=s[i]-,mid;
    while (l<r){
        mid=(l+r+)>>;
        if (k[i][mid]>=x) r=mid-;else l=mid;
    }
    if (k[i][l]<x) l++;
    return l;
}
inline int ask(){
    l=read();r=read();x=read();
    l^=lla;r^=lla;x^=lla;
    lc=;rc=;
    for (li=;li!=-;li=ne[li])
    if ((lc+=s[li])>=l) break;
    lc=l-lc+s[li]-;
    for (ri=;ri!=-;ri=ne[ri])
    if ((rc+=s[ri])>=r) break;
    rc=r-rc+s[ri]-;
    int ll=,rr=,mid,nu;
    while (ll<rr){
        mid=(ll+rr+)>>;nu=;
        if (li!=ri){
            for (i=ne[li];i!=ri;i=ne[i]) nu+=que(i,mid);
            for (i=lc;i<s[li];i++) if (a[li][i]<mid) nu++;
            for (i=;i<=rc;i++) if (a[ri][i]<mid) nu++;
        }else for (i=lc;i<=rc;i++) if (a[li][i]<mid) nu++;
        if (nu>=x) rr=mid-;else ll=mid;
    }
    return ll;
}
inline void change(){
    x=read();c=read();
    x^=lla;c^=lla;
    l=;
    for (i=;i!=-;i=ne[i])
    if ((l+=s[i])>=x) break;
    x=x-l+s[i]-;
    for (j=;j<s[i];j++) if (k[i][j]==a[i][x]) break;
    k[i][j]=a[i][x]=c;
    while (j&&(k[i][j-]>k[i][j])) swap(k[i][j-],k[i][j]),j--;
    while ((j<s[i]-)&&(k[i][j]>k[i][j+])) swap(k[i][j+],k[i][j]),j++;
}
inline void in(){
    x=read();c=read();
    x^=lla;c^=lla;
    l=;
    for (i=;i!=-;i=ne[i]){
        l+=s[i];
        if (l>=x||ne[i]==-) break;
    }
    x-=l-s[i]+;
    for (j=s[i];j>x;j--) a[i][j]=a[i][j-];
    s[i]++;a[i][x]=c;
    if (s[i]==*b){
        s[num]=b;
        s[i]=b;
        ne[num]=ne[i];
        ne[i]=num;
        for (j=;j<b;j++) k[num][j]=a[num][j]=a[i][b+j],k[i][j]=a[i][j];
        sort(k[i],k[i]+b,cmp);sort(k[num],k[num]+b,cmp);
        num++;
    }else{
        for (j=;j<s[i]-;j++) if (c<k[i][j]) break;
        l=j;
        for (j=s[i]-;j>l;j--) k[i][j]=k[i][j-];
        k[i][l]=c;
    }
}
inline int max(int a,int b){return a>b?a:b;}
int main(){
    n=read();
    b=;
    num=(n+b-)/b;
    for (int i=;i<n;i++) k[i/b][i%b]=a[i/b][i%b]=read();
    for (int i=;i<num-;i++) s[i]=b,ne[i]=i+;s[num-]=n-b*(num-);
    ne[num-]=-;
    for (int i=;i<num;i++) sort(k[i],k[i]+s[i],cmp);
    m=read();
    while(m--){
        scanf("%s",ch);
        if (ch[]=='Q') printf("%d\n",la=ask());else
        if (ch[]=='M') change();else
        in();
    }
}

后来又写了块套线段树版本，慢了很多(45s)

#include<cmath>
#include<cstdio>
#include<algorithm>
#define lla la;
using namespace std;
int read_p,read_ca;
inline int read(){
    read_p=;read_ca=getchar();
    while(read_ca<''||read_ca>'') read_ca=getchar();
    while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
    return read_p;
}
struct tree{
    int l,r,k;
}t[];
int n,m,a[][],b,num,nnu,nm=,la=,s[],ne[],xc[],mid,root[];
char ch[];
int i,j,x,c,l,r,lc,rc,li,ri;
const int MA=;
inline bool cmp(int a,int b){
    return a<b;
}
inline void in(int &p,int x){
    if (!p) p=++nm,t[nm].l=t[nm].r=t[nm].k=;
    int o=p;
    int l=,r=MA,mid;
    while(l<r){
        t[o].k++;
        mid=l+r>>;
        if (x<=mid){
            if (!t[o].l) t[o].l=++nm,t[nm].l=t[nm].r=t[nm].k=;
            o=t[o].l;
            r=mid;
        }else{
            if (!t[o].r) t[o].r=++nm,t[nm].l=t[nm].r=t[nm].k=;
            o=t[o].r;
            l=mid+;
        }
    }
    t[o].k++;
}
inline void del(int p,int x){
    int l=,r=MA,mid;
    while(l<r){
        t[p].k--;
        mid=l+r>>;
        if (x<=mid) p=t[p].l,r=mid;else p=t[p].r,l=mid+;
    }
    t[p].k--;
}
inline int ask(){
    l=read();r=read();x=read();
    l^=lla;r^=lla;x^=lla;
    lc=;rc=;
    for (li=;li!=-;li=ne[li])
    if ((lc+=s[li])>=l) break;
    lc=l-lc+s[li]-;
    for (ri=;ri!=-;ri=ne[ri])
    if ((rc+=s[ri])>=r) break;
    rc=r-rc+s[ri]-;
    int ll=,rr=,mid,nu,rt=;
    nnu=nm;
    for (i=;i<num;i++) xc[i]=root[i];
    if (li!=ri){
        for (i=lc;i<s[li];i++) in(rt,a[li][i]);
        for (i=;i<=rc;i++) in(rt,a[ri][i]);
    }else for (i=lc;i<=rc;i++) in(rt,a[li][i]);
    int k;
    l=;r=MA;
    while(l<r){
        mid=l+r>>;k=;
        if (li!=ri)for (int i=ne[li];i!=ri;i=ne[i]) k+=t[t[xc[i]].l].k;k+=t[t[rt].l].k;
        if (k>=x){
            if (li!=ri)for (int i=ne[li];i!=ri;i=ne[i]) xc[i]=t[xc[i]].l;rt=t[rt].l;
            r=mid;
        }else{
            x-=k;
            if (li!=ri)for (int i=ne[li];i!=ri;i=ne[i]) xc[i]=t[xc[i]].r;rt=t[rt].r;
            l=mid+;
        }
    }
    nm=nnu;
    return l;
}
inline void change(){
    x=read();c=read();
    x^=lla;c^=lla;
    l=;
    for (i=;i!=-;i=ne[i])
    if ((l+=s[i])>=x) break;
    x=x-l+s[i]-;
    del(root[i],a[i][x]);
    a[i][x]=c;
    in(root[i],c);
}
inline void in(){
    x=read();c=read();
    x^=lla;c^=lla;
    l=;
    for (i=;i!=-;i=ne[i]){
        l+=s[i];
        if (l>=x||ne[i]==-) break;
    }
    x-=l-s[i]+;
    for (j=s[i];j>x;j--) a[i][j]=a[i][j-];
    s[i]++;a[i][x]=c;
    in(root[i],c);
    if (s[i]==*b){
        s[i]=s[num]=b;
        root[num]=;
        for (j=;j<b;j++) a[num][j]=a[i][j+b];
        for (j=;j<b;j++) del(root[i],a[num][j]),in(root[num],a[num][j]);
        ne[num]=ne[i];ne[i]=num;
        num++;
    }
}
inline int max(int a,int b){return a>b?a:b;}
int main(){
    /*freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);*/
    n=read();
    b=;
    num=(n+b-)/b;
    for (int i=;i<n;i++) a[i/b][i%b]=read(),in(root[i/b],a[i/b][i%b]);
    for (int i=;i<num-;i++) s[i]=b,ne[i]=i+;s[num-]=n-b*(num-);
    ne[num-]=-;
    m=read();
    while(m--){
        scanf("%s",ch);
        if (ch[]=='Q') printf("%d\n",la=ask());else
        if (ch[]=='M') change();else
        in();
    }
}