纠结了好久的一道题，以前是用线段树套平衡树二分做的，感觉时间复杂度和分块差不多了。。。
终于用BIT套函数式线段树了过了，120ms就是快，此题主要是卡内存。
假设离散后有ns个不同的值，递归层数是log2(ns)左右，nlog(ns)，主席树是前缀区间，BIT保存修改的值是mlog2(ns)log2(ns)。
虽然这个算出来还是会爆，但是实际上会有一些结点复用，具体设置多少请相信玄学。（2e6左右）
ZOJ的Node*计算内存似乎有问题，必须用int
/********************************************************** ------------------ ** author AbyssFish ***********************************************************/#include#include #include #include #include #include using namespace std;//#pragma pack(4)const int MAX_N = 5e4+3;const int MAX_M = 1e4+3;const int MAX_NM = MAX_N+MAX_M;const int MAX_D = 16;const int MAX_ND = 0xac*MAX_M+0x42fed;//MAX_D*MAX_N+MAX_M*MAX_D*MAX_D;int b[MAX_NM];int mp_a[MAX_NM];int ns, n_;int N, M;struct Cmd{ int i, j, k;}qus[MAX_M];struct Node{ int lc, rc; int s;}p[MAX_ND];int root[MAX_N];int cnt;#define lsn p[o].lc,l,md#define rsn p[o].rc,md+1,rvoid build(int x,int &o,int l = 1, int r = ns){ p[++cnt] = p[o]; o = cnt; p[o].s++; if(r > l){ int md = (l+r)>>1; if(x <= md) build(x,lsn); else build(x,rsn); }}int BIT[MAX_N];void inst(int x, int d, int &o, int l = 1, int r = ns){ if(o == 0){ p[++cnt] = p[o]; o = cnt; } p[o].s += d; if(l < r){ int md = (l+r)>>1; if(x<=md) inst(x,d,lsn); else inst(x,d,rsn); }}#define lowbit(x) ((x)&(-x))void modify_bit(int pos, int x, int d){ while(pos <= N){ inst(x,d,BIT[pos]); pos += lowbit(pos); }}typedef vector Prefix;void prefix_bit(int pos, Prefix &res){ res.clear(); while(pos > 0){ res.push_back(BIT[pos]); pos -= lowbit(pos); }}inline int cal_lft(Prefix &pfx){ int re = 0; for(int i = pfx.size()-1; i >= 0; i--){ re += p[p[pfx[i]].lc].s; } return re;}#define dump(pfx,ch)\for(i = pfx.size()-1; i >= 0; i--){\ pfx[i] = p[pfx[i]].ch;\}Prefix X, Y;int qkth(int k,int l = 1, int r = ns){ if(l == r) return mp_a[l]; else { int l_cnt = cal_lft(Y)-cal_lft(X); int md = (l+r)>>1, i; if(k <= l_cnt){ dump(X,lc) dump(Y,lc) return qkth(k,l,md); } else { dump(X,rc) dump(Y,rc) return qkth(k-l_cnt,md+1,r); } }}void solve(){ cnt = 0; memset(BIT+1,0,sizeof(int)*N); int i; for(i = 1; i <= N; i++){ root[i] = root[i-1]; build(b[i], root[i]); } for(i = 0; i < M; i++){ if(qus[i].j < 0){ int pos = qus[i].i; modify_bit(pos,b[pos],-1); modify_bit(pos,b[pos] = b[qus[i].k],1); } else { int L = qus[i].i-1, R = qus[i].j; prefix_bit(L,X); prefix_bit(R,Y); X.push_back(root[L]); Y.push_back(root[R]); printf("%d\n",qkth(qus[i].k)); } }}int * const a = (int *)(p+2);int * const r = a + MAX_NM;void init(){ scanf("%d%d",&N,&M); for(int i = 1; i <= N; i++){ scanf("%d",a+i); r[i] = i; } n_ = N; char ch[3]; for(int i = 0; i < M; i++){ scanf("%s",ch); if(*ch == 'Q') { scanf("%d%d%d",&qus[i].i,&qus[i].j,&qus[i].k); } else { qus[i].k = ++n_; r[n_] = n_; scanf("%d%d",&qus[i].i,a+n_); qus[i].j = -1; } } sort(r+1,r+n_+1,[](int i,int j){ return a[i]