# o49_apr_light

Jan 8th, 2022 (edited)
390
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4. const int L = 2e9;
5. const int N = 1e5 + 1;
6. const int logN = 17;
7. struct Node{
8.     int all, blue;
9. };
10. Node tree[1 << (logN + 1)];
11. bool lazy[1 << (logN + 1)];
12. int ques[N + 1];
13. vector <int> pst;
14. int len[N + 1];
15. int l, sz;
16.
17. Node Combine(Node L, Node R){
18.     Node node;
19.     node.all = L.all + R.all;
20.     node.blue = L.blue + R.blue;
21.     return node;
22. }
23.
24. void Build(int idx, int l, int r){
25.     if(l == r){
26.         tree[idx].all = tree[idx].blue = len[l - 1];
27.         return ;
28.     }
29.     int mid = (l + r) / 2;
30.     Build(2 * idx, l, mid);
31.     Build(2 * idx + 1, mid + 1, r);
32.     tree[idx] = Combine(tree[2 * idx], tree[2 * idx + 1]);
33. }
34.
35. void Flip(int idx, int l, int r){
36.     if(l != r){
37.         lazy[2 * idx] = !lazy[2 * idx];
38.         lazy[2 * idx + 1] = !lazy[2 * idx + 1];
39.     }
40.     tree[idx].blue = tree[idx].all - tree[idx].blue;
41.     lazy[idx] = false;
42. }
43.
44. void Update(int idx, int l, int r, int s, int e){
45.     if(lazy[idx]) Flip(idx, l, r);
46.     if(r < s or e < l) return;
47.     if(s <= l and r <= e){
48.         Flip(idx, l, r);
49.         return;
50.     }
51.     int mid = (l + r) / 2;
52.     Update(2 * idx, l, mid, s, e);
53.     Update(2 * idx + 1, mid + 1, r, s, e);
54.     tree[idx] = Combine(tree[2 * idx], tree[2 * idx + 1]);
55. }
56.
57. int Index(int x, int l = 0, int r = sz - 1){
58.     while(l <= r){
59.         int mid = (l + r) / 2;
60.         if(pst[mid] == x) return mid;
61.         else if(pst[mid] < x) l = mid + 1;
62.         else r = mid - 1;
63.     }
64. }
65.
66. int main(){
67.
68.     int n;
69.     scanf("%d %d", &l, &n);
70.
71.     pst.push_back(1);
72.     for(int i=1;i<=n;i++){
73.         scanf("%d", &ques[i]);
74.         ques[i] ++;
75.         pst.push_back(ques[i]);
76.     }
77.
78.     sort(pst.begin(), pst.end());
79.     pst.resize( unique(pst.begin(), pst.end()) - pst.begin() );
80.     sz = pst.size();
81.
82.     for(int i=0;i<=sz-2;i++){
83.         len[i] = pst[i + 1] - pst[i];
84.     }
85.     len[sz - 1] = l - pst[sz - 1] + 1;
86.
87.     Build(1, 1, sz);
88.
89.     for(int i=1;i<=n;i++){
90.         int idx = Index(ques[i]) + 1;
91.         Update(1, 1, sz, idx, sz);
92.         printf("%d\n", tree[1].blue);
93.     }
94.
95.     return 0;
96. }
RAW Paste Data Copied