Findstrなのです

树状数组套主席树做法，动态建树卡空间过了。

速度还行。

/**************************************************************
    Problem: 3196
    User: Shimakaze
    Language: C++
    Result: Accepted
    Time:2092 ms
    Memory:119584 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
#include<cstring>
#define PROC "1"
using namespace std;
const int maxn=50010;
struct yjq{
    int l,r,k;
    char type;
};
yjq opt[maxn];
int hash[maxn*2], a[maxn], hn, n, m;
 
struct seg{
    int sum, L, R;
};
seg tree[maxn*200];
int nn, root[maxn];
 
void update(int num)
{
    tree[num].sum=tree[tree[num].L].sum+tree[tree[num].R].sum;
}
 
void modify(int &num, int L, int R, int pos, int v)
{
    if (!num)
        num=++nn;
    if (L==R)
    {
        tree[num].sum+=v;
        return;
    }
    int mid=(L+R)>>1;
    if (pos<=mid)
        modify(tree[num].L,L,mid,pos,v);
    else
        modify(tree[num].R,mid+1,R,pos,v);
    update(num);
}
#define lowbit(x) ((x)&(-(x)))
void modify(int pos, int val, int v)
{
    for (int i=pos; i<=n; i+=lowbit(i))
        modify(root[i],1,hn,val,v);
}
 
void build()
{
    for (int i=1; i<=n; i++)
        modify(i,a[i],1);
}
 
int left[100], right[100], ln, rn;
 
void init(int l, int r)
{
    ln=rn=0;
    for (int i=l-1; i; i-=lowbit(i))
        left[++ln]=root[i];
    for (int i=r; i; i-=lowbit(i))
        right[++rn]=root[i];
}
 
void walkleft()
{
    for (int i=1; i<=ln; i++)
        left[i]=tree[left[i]].L;
    for (int i=1; i<=rn; i++)
        right[i]=tree[right[i]].L;
}
 
void walkright()
{
    for (int i=1; i<=ln; i++)
        left[i]=tree[left[i]].R;
    for (int i=1; i<=rn; i++)
        right[i]=tree[right[i]].R;
}
 
int getsum()
{
    int sum=0;
    for (int i=1; i<=ln; i++)
        sum-=tree[left[i]].sum;
    for (int i=1; i<=rn; i++)
        sum+=tree[right[i]].sum;
    return sum;
}
 
int getlsum()
{
    int sum=0;
    for (int i=1; i<=ln; i++)
        sum-=tree[tree[left[i]].L].sum;
    for (int i=1; i<=rn; i++)
        sum+=tree[tree[right[i]].L].sum;
    return sum;
}
 
int getrsum()
{
    int sum=0;
    for (int i=1; i<=ln; i++)
        sum-=tree[tree[left[i]].R].sum;
    for (int i=1; i<=rn; i++)
        sum+=tree[tree[right[i]].R].sum;
    return sum;
}
 
int querysum(int L, int R, int r)
{
    if (r==R)
        return getsum();
    int mid=(L+R)>>1;
    if (r<=mid)
    {
        walkleft();
        return querysum(L,mid,r);
    }
    else
    {
        int nowsum=getlsum();
        walkright();
        return nowsum+querysum(mid+1,R,r);
    }
}
 
int querynum(int L, int R, int rank)
{
    if (L==R)
        return L;
    int mid=(L+R)>>1;
    int lsum=getlsum();
    if (lsum>=rank)
    {
        walkleft();
        return querynum(L,mid,rank);
    }
    else
    {
        rank-=lsum;
        walkright();
        return querynum(mid+1,R,rank);
    }
}
 
int Queryrank(int l, int r, int v)
{
    init(l,r);
    return querysum(1,hn,v-1)+1;
}
 
int Querynum(int l, int r, int rank)
{
    init(l,r);
    return querynum(1,hn,rank);
}
 
int Querypre(int l, int r, int num)
{
    return Querynum(l,r,Queryrank(l,r,num)-1);
}
 
int Querynext(int l, int r, int num)
{
    return Querynum(l,r,Queryrank(l,r,num+1));
}
 
void readInfo()
{
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        hash[++hn]=a[i];
    }
    int type, l, r, k;
    for (int i=1; i<=m; i++)
    {
        scanf("%d",&type);
        opt[i].type=type;
        if (type==3)
        {
            scanf("%d%d",&l,&k);
            opt[i].l=l;
            opt[i].k=k;
            hash[++hn]=k;
            continue;
        }
        scanf("%d%d%d",&l,&r,&k);
        opt[i].l=l;
        opt[i].r=r;
        opt[i].k=k;
        if (type!=2)
            hash[++hn]=k;
    }
    sort(hash+1,hash+1+hn);
    hn=unique(hash+1,hash+1+hn)-hash-1;
    for (int i=1; i<=n; i++)
        a[i]=lower_bound(hash+1,hash+1+hn,a[i])-hash;
    for (int i=1; i<=m; i++)
        if (opt[i].type!=2)
            opt[i].k=lower_bound(hash+1,hash+1+hn,opt[i].k)-hash;
}
 
int main()
{
#ifdef YJQ_LOCAL
    freopen(PROC".in","r",stdin);
#endif
    readInfo();
    build();
    for (int i=1; i<=m; i++)
    {
//      printf("now %d %d %d %d\n",opt[i].type,opt[i].l,opt[i].r,opt[i].k); 
        if (opt[i].type==1)
            printf("%d\n",Queryrank(opt[i].l,opt[i].r,opt[i].k));
        if (opt[i].type==2)
            printf("%d\n",hash[Querynum(opt[i].l,opt[i].r,opt[i].k)]);
        if (opt[i].type==3)
        {
            int pos=opt[i].l;
            modify(pos,a[pos],-1);
            a[pos]=opt[i].k;
            modify(pos,a[pos],1);
        }
        if (opt[i].type==4)
            printf("%d\n",hash[Querypre(opt[i].l,opt[i].r,opt[i].k)]);
        if (opt[i].type==5)
            printf("%d\n",hash[Querynext(opt[i].l,opt[i].r,opt[i].k)]);
    }
    fclose(stdout);
    return 0;
}