Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2546 Accepted Submission(s): 1174
5 0 5 1 2 0 6 2 3 2 2 8 1 7 0 2 0 2 0 4 2 1 1 2 1 2 2 1 3 2 1 4
No Elment! 6 Not Find! 2 2 4 Not Find!
三種操作,0 代表添加一個數x,1代表刪除一個數x,2代表 找比a大的第k個數,使用線段樹求解,線段樹統計在一個區間內出現的數的個數,對於找比a大的第k個數,從a開始向後查找,如果在某段中累加的和大於k,就讓它跳入這段中,直到深入到一個葉子節點時,剛好ans >= k。
對線段樹的更新不解釋,主要是查詢的時候
1.如果當前區間[l,r]中 r<=a那麼這一段的數都不用統計。
2.如果r >a,代表該段中存在比a大的數就要向下深入。
3.如果l > a,那麼該段中所有的點都會大於a,開始判斷,如果該段全部加入後仍然小於k,那麼就可以全部加入,如果加進去以後大於等於k,那麼就要向下深入,一直深入到葉子節點,滿足條件的,最左的葉子節點就是我們要求的值。(線段樹,從左向右查找,一定可以找到第一個)
#include#include #include using namespace std; #define maxn 110000 #define lmin 1 #define rmax n #define lson l,(l+r)/2,rt<<1 #define rson (l+r)/2+1,r,rt<<1|1 #define root lmin,rmax,1 #define now l,r,rt #define int_now int l,int r,int rt int cl[maxn<<2] , k1[maxn] , k2[maxn<<2] , top ; void push_up(int_now) { cl[rt] = cl[rt<<1] + cl[rt<<1|1] ; } void creat(int_now) { cl[rt] = 0 ; if(l != r) { creat(lson); creat(rson); push_up(now); } else { cl[rt] = 0 ; k2[rt] = ++top ; } } void update(int x,int d,int_now) { if( l > x || r < x ) return ; if( l == r && l == x ) { cl[rt] += d ; return ; } update(x,d,lson); update(x,d,rson); push_up(now); } int query(int ll,int ans,int num,int_now) { if( r <= ll ) return 0; if( ll < l ) { if( ans + cl[rt] < num ) return ans + cl[rt] ; if(ans < num && ans + cl[rt] >= num && l == r ) { printf("%d\n", k2[rt] ); return ans + cl[rt] ; } if(ans < num && ans + cl[rt] >= num ) { if( ans + cl[rt<<1] >= num ) ans = query(ll,ans,num,lson); else ans = query(ll,ans+cl[rt<<1],num,rson); return ans ; } } else { if( ans < num ) ans = query(ll,ans,num,lson); if(ans < num) ans = query(ll,ans,num,rson); return ans; } } int main() { int m , i , n , l , r , x , temp , num ; while(scanf("%d", &m) != EOF) { top = 0 ; n = maxn ; creat(root); memset(k1,0,sizeof(k1)); while(m--) { scanf("%d", &temp); if( temp == 0 ) { scanf("%d", &x); k1[x]++ ; update(x,1,root); } else if( temp == 1 ) { scanf("%d", &x); if( k1[x] == 0 ) printf("No Elment!\n"); else { k1[x]-- ; update(x,-1,root); } } else { scanf("%d %d", &l, &num); x = query(l,0,num,root); if(x < num) printf("Not Find!\n"); } } } }