HDU-1166 敌兵布阵 ( 线段树 )

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 class node{
 6 public:
 7     int l, r, v;
 8     node *left, *right;
 9 };
10 
11 node *Creat( int z, int y ){
12     node *root = new node;
13     root->l = z;
14     root->r = y;
15     root->v = 0;
16     root->left = NULL;
17     root->right = NULL;
18 
19     if( z < y ){
20         int mid = ( z + y ) >> 1;
21         root->left = Creat( z ,mid );
22         root->right = Creat( mid+1, y);
23     }
24 
25     return root;
26 }
27 
28 void Insert( int n,int x, node *p ){
29     if( n == p->l && n == p->r ) p->v += x;
30 
31     else{
32         p->v += x;
33         int mid = ( p->l + p->r ) >>1;
34         if( n <= mid ) Insert( n, x, p->left );
35         else Insert( n, x, p->right );
36     }
37 }
38 
39 int Ask( int z, int y, node *p ){
40     int ans = 0;
41 
42     if( z < p->l ) z = p->l;
43     if( y > p->r ) y = p->r;
44 
45     if( z == p->l && y == p->r ) return p->v;
46 
47     int mid = ( p->l + p->r ) >> 1;
48 
49     if( z <= mid )
50         ans += Ask( z, y, p->left );
51 
52     if( y > mid )
53         ans += Ask( z, y, p->right );
54 
55     return ans;
56 }
57 
58 int main(){
59     ios::sync_with_stdio( false );
60 
61     int T;
62 
63     cin >> T;
64     for( int t = 1; t <= T; t++ ){
65         int n, temp;
66         cin >> n;
67         node *root = Creat( 1, n );
68 
69         for( int i = 1; i <= n; i++ ){
70             cin >> temp;
71             Insert( i, temp, root );
72         }
73 
74         cout << "Case " << t << ":\n";
75         string ask;
76 
77         while( cin >> ask, ask != "End" ){
78             if( ask == "Query" ){
79                 int z, y;
80                 cin >> z >> y;
81                 cout << Ask( z, y ,root ) << endl;
82             }
83 
84             if( ask == "Add" ){
85                 int x, y;
86                 cin >> x >> y;
87                 Insert( x, y, root ); 
88             }
89 
90             if( ask == "Sub"){
91                 int x, y;
92                 cin >> x >> y;
93                 Insert( x, -y, root );
94             }
95         }
96     }
97 
98     return 0;
99 }