题目链接：
hdu 3727
题目大意：
给出n个操作，插入一个数，或者查询： – 查询区间第k大 – 查询某个数的排名 – 查询整体第k大 最后问三种查询的结果之和。
题目分析：首先对数进行离散化然后对数字建立主席树，第k大的做法详见我的主席树学习第一弹查询某个数的排名，树状数组直接做就好了，记录每个点是否出现过，然后找到sum(x)就是前缀一共有多少个数，也就是当前数的排名。 AC代码：using namespace std;typedef long long LL;int root[MAX],cnt_trees,n,len,h[MAX],hcnt;LL ans1,ans2,ans3;struct Query{int f,s,t,k;void init ( int a , int b ,int c , int d ){f=a,s=b,t=c,k=d;}}q[MAX<<1];struct Tree{int l,r;int sum;}tree[4000007];void build ( int& u , int l , int r ){u = cnt_trees++;tree[u].sum = 0;if ( l == r ) return;int mid = l+r>>1;build ( tree[u].l , l , mid );build ( tree[u].r , mid+1 , r );}void update ( int p , int& u , int l , int r , int x ){u = cnt_trees++;tree[u] = tree[p];tree[u].sum++;if ( l == r ) return;int mid = l+r>>1;if ( x > mid )update ( tree[p].r , tree[u].r , mid+1 , r , x );elseupdate ( tree[p].l , tree[u].l , l , mid , x );}int query ( int p , int u , int l , int r , int k ){int sum = tree[tree[u].l].sum – tree[tree[p].l].sum;if ( l == r ) return l;int mid = l+r>>1;if ( sum >= k ) return query ( tree[p].l , tree[u].l , l , mid , k );else return query ( tree[p].r , tree[u].r , mid+1 , r , k-sum );}int c[MAX<<1];int lowbit ( int x ){return x&-x;}void add ( int x ){while ( x < hcnt ){c[x]++;x += lowbit ( x );}}int sum ( int x ){int ret = 0;while ( x ){ret += c[x];x -= lowbit ( x );}return ret;}char s[30];int main ( ){int cc = 1;while ( ~scanf ( “%d” , &n ) ){cnt_trees = 0;len = hcnt = 1;memset ( c , 0 , sizeof ( c ) );for ( int i = 1 ; i <= n ; i++ ){int x,y,z;scanf ( “%s” , s );if ( s[0] == ‘I’ ){q[i].f = 0;scanf ( “%d” , &q[i].k );h[hcnt++] = q[i].k;}else{int id = s[6]-48;if ( id == 1 )scanf ( ” , &x , &y , &z );elsescanf ( “%d” , &z );q[i].init ( id , x , y , z );}}sort ( h+1 , h+hcnt );build ( root[0] , 1 , hcnt-1 );ans1 = ans2 = ans3 = 0;for ( int i = 1 ; i <= n ; i++ ){if ( q[i].f == 0 ){int x = lower_bound ( h , h+hcnt , q[i].k )-h;update ( root[len-1] , root[len] , 1 , hcnt-1 , x );add ( x );len++;}else if ( q[i].f == 1 )ans1 += h[query ( root[q[i].s-1] , root[q[i].t] , 1 , hcnt-1 , q[i].k )];else if ( q[i].f == 2 ){int x = lower_bound ( h , h+hcnt , q[i].k )-h;ans2 += sum(x);}else if ( q[i].f == 3 )ans3 += h[query ( root[0] , root[len-1] , 1 , hcnt-1 , q[i].k )];}printf ( “Case %d:\n” , cc++ );printf ( “%I64d\n%I64d\n%I64d\n” , ans1 , ans2 , ans3 );} }
，会得到最大的满足，因为它填补了你的空虚。
