bzoj 3065: 带插入区间K小值

.

题意：带插入、修改的区间k小值
题解：大力分块
代码：

#include<bits/stdc++.h>
using namespace std;
int n,q;
int blocksize,lastans=0,u[70010];
list<vector<int> >a,b;
list<vector<int> >::iterator ita,itb,itax,itay,itbx,itby;
int posx,posy;
void splita(list<vector<int> >::iterator ita)
{
    vector<int>hh;
    for(int i=blocksize;i<(blocksize<<1);i++)
    hh.push_back((*ita)[i]);
    for(int i=blocksize;i<(blocksize<<1);i++)
    ita->pop_back();
    a.insert(++ita,hh);
}
void split(list<vector<int> >::iterator ita,list<vector<int> >::iterator itb)
{
    splita(ita);
    ita++;
    static int tf[70010];
    memset(tf,0,sizeof(tf));
    for(int i=0;i<blocksize;i++)
    tf[(*ita)[i]]++;
    int hh=0,mx=*itb->rbegin();
    while(!tf[hh])
    hh++;
    for(int i=0;i<(blocksize<<1)&&hh<=mx;i++)
    {
        if((*itb)[i]==hh)
        {
            itb->erase(itb->begin()+i);
            i--;
            tf[hh]--;
            while(!tf[hh]&&hh<=mx)
            hh++;
        }
    }
    b.insert(++itb,*ita);
    itb--;
    sort(itb->begin(),itb->end());
}
int getpos(int x)
{
    int s=0;
    for(ita=a.begin(),itb=b.begin();ita!=a.end();ita++,itb++)
    {
        s+=ita->size();
        if(s>=x)
        break;
    }
    if(s>=x)
    {
        s-=ita->size();
        return x-s-1;
    }
    else
    {
        return 0;
    }
}
int get(int x)
{
    int szx=itax->size(),ans=0;
    for(int i=posx;i<szx;i++)
    if((*itax)[i]<x)
    ans++;
    for(int i=0;i<=posy;i++)
    if((*itay)[i]<x)
    ans++;
    for(list<vector<int> >::iterator it=++itbx;it!=itby;it++)
    ans+=int(lower_bound(it->begin(),it->end(),x)-it->begin());
    itbx--;
    // printf("%d %d\n",x,ans);
    return ans;
}
int chk(const int& x,const int& y)
{
    return get(x)<y;
}
int main()
{
    for(int i=0;i<=70001;i++)
    u[i]=i;
    scanf("%d",&n);
    // blocksize=sqrt(n);
    blocksize=610;
    // blocksize=10;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        if(a.empty())
        {
            vector<int>hh;
            a.push_back(hh);
        }
        a.back().push_back(x);
        if(a.back().size()>=2*blocksize)
        splita(--a.end());
    }
    b=a;
    for(itb=b.begin();itb!=b.end();itb++)
    {
        sort(itb->begin(),itb->end());
    }
    scanf("%d",&q);
    int kk=0;
    while(q--)
    {
        char op[3];
        int x,y,k;
        scanf("%s",op);
        switch(op[0])
        {
            int pos;
            case 'M':
                scanf("%d%d",&x,&k);
                x^=lastans;
                k^=lastans;
                pos=getpos(x);
                *lower_bound(itb->begin(),itb->end(),(*ita)[pos])=k;
                sort(itb->begin(),itb->end());
                (*ita)[pos]=k;
                break;
            case 'I':
                scanf("%d%d",&x,&k);
                x^=lastans;
                k^=lastans;
                pos=getpos(x);
                if(ita==a.end())
                {
                    ita--;
                    itb--;
                    pos=ita->size();
                }
                ita->insert(ita->begin()+pos,k);
                itb->push_back(k);
                sort(itb->begin(),itb->end());
                if(ita->size()>=(blocksize<<1))
                split(ita,itb);
                break;
            case 'Q':
                scanf("%d%d%d",&x,&y,&k);
                x^=lastans;
                y^=lastans;
                k^=lastans;
                if(x>y)
                swap(x,y);
                posx=getpos(x);
                itax=ita,itbx=itb;
                posy=getpos(y);
                itay=ita,itby=itb;
                if(itax==itay)
                {/*
                    set<int>s;
                    for(int i=posx;i<=posy;i++)
                    s.insert((*ita)[i]);
                    set<int>::iterator it=s.begin();
                    k--;
                    for(;it!=s.end()&&k;it++,k--);
                    printf("%d\n",lastans=*it);*/
                    vector<int>s;
                    for(int i=posx;i<=posy;i++)
                    s.push_back((*ita)[i]);
                    sort(s.begin(),s.end());
                    printf("%d\n",lastans=s[k-1]);
                }
                else
                printf("%d\n",lastans=*lower_bound(u,u+70001,k,chk)-1);
                break;
        }/*
        printf("i:%d\n",++kk);
        puts("a");
        for_each(a.begin(),a.end(),[](vector<int>x){printf("size:%d\n",x.size());for(auto i:x) printf("%d ",i);puts("");});
        puts("b");
        for_each(b.begin(),b.end(),[](vector<int>x){printf("size:%d\n",x.size());for(auto i:x) printf("%d ",i);puts("");});*/
    }
}