HDU 4217 Data Structure?

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<stdlib.h>

 4 #define N 1000000

 5 __int64 temp;

 6 struct node

 7 {

 8     __int64 l,r;

 9     __int64 sum;

10 }xtree[4*N];

11 void pushup(int rn)

12 {

13     xtree[rn].sum=xtree[rn<<1].sum+xtree[rn<<1|1].sum;

14 }

15 void build(__int64 l,__int64 r,__int64 rn)

16 {

17     xtree[rn].l=l;

18     xtree[rn].r=r;

19     if(l==r)

20     {

21         xtree[rn].sum=1;

22         return ;

23     }

24     __int64 mid=(l+r)>>1;

25     build(l,mid,rn<<1);

26     build(mid+1,r,rn<<1|1);

27     pushup(rn);

28 }

29 void update(__int64 val,__int64 l,__int64 r,int rn)

30 {

31     if(l==r)

32     {

33         temp+=l;

34         xtree[rn].sum=0;

35         return ;

36     }

37     int mid=(l+r)>>1;

38     if(val<=xtree[rn<<1].sum)

39     {

40         update(val,l,mid,rn<<1);

41     }

42     else

43     {

44         update(val-xtree[rn<<1].sum,mid+1,r,rn<<1|1);

45     }

46     pushup(rn);

47 }

48 int main()

49 {

50     __int64 n,m,a,t,c=1;

51     scanf("%I64d",&n);

52     while(n--)

53     {

54         temp=0;

55         scanf("%I64d",&m);

56         build(1,m,1);

57         scanf("%I64d",&t);

58         while(t--)

59         {

60             scanf("%I64d",&a);

61             update(a,1,m,1);

62         }

63         printf("Case %I64d: ",c);

64         printf("%I64d
",temp);

65         c++;

66     }

67     return 0;

68 }