Lightoj 1087 Diablo (Seg tree)

http://lightoj.com/volume_showproblem.php?problem=1087

  //it can be done using segment tree, sqrt decomposition and vector

  // Segment tree version

1. #include <bits/stdc++.h>
2. using namespace std;
4. #define pi 2*acos(0.0)
5. #define all(v) v.begin(),v.end()
6. #define coff ios_base::sync_with_stdio(0);
8. #define ff first
9. #define se second
10. #define pb push_back
11. #define sz(a) ((int)a.size())
12. #define ST(v) sort(all(v))
13. #define gcd(a,b) __gcd(a,b)
14. #define lcm(a,b) (a*(b/gcd(a,b)))
15. #define max3(a,b,c) max(a,max(b,c))
16. #define min3(a,b,c) min(a,min(b,c))
17. #define cover(a,d) memset(a,d,sizeof(a))
18. #define popcount(i) __builtin_popcount(i)      //count one. in long long use __builtin_popcountll(i)
19. #define parity(i)   __builtin_parity(i)       //evenparity 0 and odd parity 1
20. #define btz(a)   __builtin_ctz(a)            //count binary trailling zero
21. #define un(v) ST(v), (v).erase(unique(all(v)),v.end())
22. #define common(a,b) ST(a), ST(b), a.erase(set_intersection(all(a),all(b),a.begin()),a.end())
23. #define uncommon(a,b) ST(a), ST(b), a.erase(set_symmetric_difference(all(a),all(b),a.begin()),a.end())
25. typedef  long long ll;
26. typedef  unsigned long long ull;
28. template <typename T>string toString( T Number ){stringstream st;st << Number;return st.str();}
29. int stringconvert(string s){int p; istringstream st(s); st>>p ; return p;}
31. //upper bound and lower bound
32. #define LB(a,value) (lower_bound(all(a),value)-a.begin())
33. #define UB(a,value) (upper_bound(all(a),value)-a.begin())
35. //Debug
36. #define dbg(x) cout<<#x<<'='<<x<<endl;
37. #define dbgarr(i,a) cout<<#a<<"["<<i<<"] = "<<a[i]<<" "<<endl;
38. #define nl puts("")
40. //File input/output
41. #define input freopen("in.txt","r",stdin)
42. #define output freopen("out.txt","w",stdout)
44. ll bigmod(ll a,ll b, ll m) { ll res = 1; while(b) { if(b & 1) { res = ( (res % m) * (a % m) ) %m ; } a= ((a%m) * (a%m)) %m; b >>= 1; }return res; }
45. ll modInverse(ll a, ll m){return bigmod(a,m-2,m);}
47. ////============ CONSTANT ===============////
48. #define inf   1<<30                                           //infinity value
49. #define eps   1e-9
50. #define mx    100009
51. #define mod   1000000007
52. ////=====================================////
54. struct info //for combine single update segment tree and range update segment tree
55. {
56.     int sum,value,pos;
57.     info() : sum(0),value(0),pos(0){}
58. }tree[6*mx];
60. int limit;
62. void update_node(int node, int i, int val,int visibility)
63. {
64.     tree[node].pos = i;
65.     tree[node].value = val;
66.     tree[node].sum = visibility;
67. }
69. void marge(int node, int left, int right)
70. {
71.     tree[node].sum= tree[left].sum + tree[right].sum;
72. }
74. void update(int node, int s, int e, int i, int val, int status)
75. {
77.    if(s==e)
78.    {
79.        update_node(node,i,val,status);
80.        return;
81.    }
83.    int left=node<<1;
84.    int mid=(s+e)>>1;
86.    if(i<=mid)
87.    {
88.         update(left,s,mid,i,val,status);
89.    }
90.    else
91.    {
92.        update(left+1,mid+1,e,i,val,status);
93.    }
94.    marge(node,left,left+1);
95. }
97. int query(int node, int s, int e, int k)
98. {
99.     if(k>tree[node].sum)
100.     {
101.         return -1;
102.     }
103.     if(s==e)
104.     {
105.         if(k!=tree[node].sum)
106.             return -1;
107.         else
108.         {
109.             tree[node].sum=0;
110.             update(1,1,limit,tree[node].pos,tree[node].value,0);
111.             return tree[node].value;
112.         }
113.     }
115.     int left=node<<1;
116.     int mid=(s+e)>>1;
118.     if(k<=tree[left].sum)
119.     {
120.         return query(left,s,mid,k);
121.     }
122.     else
123.     {
124.         return query(left+1,mid+1,e,k-tree[left].sum);
125.     }
126. }
128. int main()
129. {
130.     int t,no=0;
131.     scanf("%d",&t);
133.     while(t--)
134.     {
135.         int n,q,a;
136.         scanf("%d %d",&n,&q);
138.         cover(tree,0);
139.         limit=n+q; // because of initialize segment tree node may not equal after query updating but this is highest limit of each input.
141.         for(int i=0;i<n;i++)
142.         {
143.             scanf("%d",&a);
144.             update(1,1,limit,i+1,a,1);
145.         }
147.         printf("Case %d:n",++no);
148.         while(q--)
149.         {
150.             char ch[3];
151.             scanf("%s %d",&ch,&a);
153.             if(ch[0]=='a')
154.             {
155.                 n++;
156.                 update(1,1,limit,n,a,1);
157.             }
158.             else
159.             {
160.                 int res = query(1,1,limit,a);
161.                 if(res==-1)
162.                 {
163.                     printf("nonen");
164.                 }
165.                 else
166.                 {
167.                     printf("%dn",res);
168.                 }
169.             }
170.         }
171.     }
173.     return 0;
174. }