hdu4217Data Structure?

http://acm.hdu.edu.cn/showproblem.php?pid=4217

开一个数组标记这个数是否被拿走 s[w]为区间和当求第K小的数的时候让他与s[w]的左右子树比较看在哪个区间中依次找下去总会找到一个s[]与他相等所对应的区间就是那个应该被拿走的值

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 #define MAX 262144
 5 using namespace std;
 6 int to[4*MAX];
 7 __int64 s[4*MAX],sum;
 8 void push(int w)
 9 {
10     s[w] = s[2*w]+s[2*w+1];
11 }
12 void ctree(int l, int r, int w)
13 {
14     if(l==r)
15     {
16         s[w]=1;
17         return ;
18     }
19     int m = (l+r)/2;
20     ctree(l,m,2*w);
21     ctree(m+1,r,2*w+1);
22     push(w);//更新和
23 }
24 void add(int p,int l,int r,int w)
25 {
26     if(l==r)
27     {
28         s[w] = 0;
29         sum+=l;
30         return ;
31     }
32     int m = (l+r)/2;
33     if(p<=s[2*w])//在左右区间的哪个
34     add(p,l,m,2*w);
35     else
36     {
37         p-=s[2*w];//右区间剪掉左区间的和
38         add(p,m+1,r,2*w+1);
39     }
40     push(w);//更新
41 }
42 int main()
43 {
44     int i,j,k,n,m,t,a,x = 0;
45     scanf("%d",&t);
46     while(t--)
47     {
48         ctree(1,MAX,1);
49         x++;
50         sum = 0;
51         scanf("%d%d",&n,&k);
52         while(k--)
53         {
54             scanf("%d",&a);
55             add(a,1,MAX,1);
56         }
57         printf("Case %d: ",x);
58         printf("%I64d\n",sum);
59     }
60     return 0;
61 }