链接： http://acm.hdu.edu.cn/showproblem.php?pid=3727
题意：
对一段序列进行四种操作：
Insert x ：在序列尾部插入一个x；
Query_1 s t k : 求区间[s,t]中第k小的数
Query_2 x: 求x在序列中的排名
Query_3 k:求序列中第k小的数
思路;
第2，4个操作明显就是很裸的主席树求第k小。第3个操作我们可以单独用个树状数组维护，第一个操作因为会对序列造成影响，我们可以对所有操作进行离线处理，
分析完后可以发现这应该是一道比较简单的题。
主席树写搓了。。找了半天的错。。自闭
#include<bits/stdc++.h> using namespace std; #define ll long long #define mid int m = (l + r) >> 1 #pragma comment(linker, "/STACK:102400000,102400000") const int M = 2e5 + 10; int c[M],ls[M*10],rs[M*10],sum[M*10],a[M],root[M],num; ll ans1,ans2,ans3; int n,len,cnt,idx; void add(int x){ while(x <= len){ c[x] += 1; x += (x&-x); } } int getsum(int x){ int ans = 0; while(x){ ans += c[x]; x -= (x&-x); } return ans; } void update(int &now,int l,int r,int p){ int old = now; now = ++idx; ls[now] = ls[old]; rs[now] = rs[old]; sum[now] = sum[old] + 1; if(l == r) return ; mid; if(p <= m) update(ls[now],l,m,p); else update(rs[now],m+1,r,p); } int query_1(int old,int now,int l,int r,int k){ if(l == r) return l; mid; int ret = sum[ls[now]] - sum[ls[old]]; //cout<<sum[ls[now]]<<" "<<sum[ls[old]]<<endl; if(ret >= k) return query_1(ls[old],ls[now],l,m,k); else return query_1(rs[old],rs[now],m+1,r,k-ret); } int query_3(int &now,int l,int r,int k){ if(l == r) return l; mid; int ret = sum[ls[now]]; if(ret >= k) return query_3(ls[now],l,m,k); else return query_3(rs[now],m+1,r,k - ret); } int find(int x){ return lower_bound(a+1,a+1+len,x) - a; } void init(){ cnt = 0; idx = 0; len = 0,num = 1; ans1 = 0; ans2 = 0;ans3 = 0; memset(c,0,sizeof(c)); memset(ls,0,sizeof(ls)); memset(rs,0,sizeof(rs)); memset(sum,0,sizeof(sum)); memset(root,0,sizeof(root)); } struct node{ int x,s,t,k; }q[M]; char op[M][8]; int main() { int cas = 1; while(scanf("%d",&n)!=EOF){ init(); for(int i = 1;i <= n;i ++){ scanf("%s",op[i]); if(op[i][0] == 'I'){ scanf("%d",&q[i].x); a[++cnt] = q[i].x; } else{ if(op[i][6] == '1') scanf("%d%d%d",&q[i].s,&q[i].t,&q[i].k); else if(op[i][6] == '2') scanf("%d",&q[i].x),a[++cnt] = q[i].x; else if(op[i][6] == '3') scanf("%d",&q[i].k); } } sort(a+1,a+1+cnt); len = unique(a+1,a+1+cnt) - a-1; for(int i = 1;i <= n;i ++){ if(op[i][0] == 'I'){ int fx = find(q[i].x); root[num] = root[num-1]; update(root[num],1,len,fx); num++; add(fx); } else{ if(op[i][6] == '1') ans1 += a[query_1(root[q[i].s-1],root[q[i].t],1,len,q[i].k)]; else if(op[i][6] == '2'){ int fx = find(q[i].x); ans2 += getsum(fx-1) + 1; } else if(op[i][6] == '3') ans3 += a[query_3(root[num-1],1,len,q[i].k)]; //cout<<ans1<<" "<<ans2<<" "<<ans3<<" "<<endl; } } printf("Case %d: ",cas++); printf("%lld %lld %lld ",ans1,ans2,ans3); } return 0; } /* 3 0 1 0 3 1 2 1 */