YEZAELP

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