fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. struct SegmentTree{
  5. #define L 2*node+1
  6. #define R 2*node+2
  7. #define mid (l+r>>1)
  8. private:
  9.     vector<int>seg;ll sz;
  10.     int merge(int &a,int b)
  11.     {
  12.         return a+b;
  13.     }
  14.     void build(int l,int r,int node,vector<ll>&arr)
  15.     {
  16.         if(l==r)
  17.         {
  18.             if(l<arr.size())
  19.             {
  20.                 seg[node]=arr[l];
  21.             }
  22.             return;
  23.         }
  24.         build(l,mid,L,arr);
  25.         build(mid+1,r,R,arr);
  26.         seg[node]=merge(seg[L],seg[R]);
  27.     }
  28.     void update(int l,int r,int node,int idx)
  29.     {
  30.         if(l==r)
  31.         {
  32.             seg[node]^=1;
  33.             return;
  34.         }
  35.         if(idx<=mid)
  36.         {
  37.             update(l,mid,L,idx);
  38.         }
  39.         else
  40.         {
  41.             update(mid+1,r,R,idx);
  42.         }
  43.         seg[node]=merge(seg[L],seg[R]);
  44.     }
  45.     int query(int l,int r,int node,int k)
  46.     {
  47.         if(l==r)
  48.         {
  49.             return l;
  50.         }
  51.         int lft=seg[L];
  52.         if(lft>=k)
  53.         {
  54.             return query(l,mid,L,k);
  55.         }
  56.         return query(mid+1,r,R,k-lft);
  57.     }
  58. public:
  59.     SegmentTree(vector<ll>&arr)
  60.     {
  61.         int n=arr.size();
  62.         sz=1;
  63.         while(sz<n)
  64.         {
  65.             sz<<=1;
  66.         }
  67.         seg=vector<int>(sz<<1,0);
  68.         build(0,sz-1,0,arr);
  69.     }
  70.     void update(int idx)
  71.     {
  72.         update(0,sz-1,0,idx);
  73.     }
  74.     ll query(int k)
  75.     {
  76.         return query(0,sz-1,0,k);
  77.     }
  78. #undef L
  79. #undef R
  80. #undef mid
  81. };
  82. signed main()
  83. {
  84.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  85.     int n,q;cin>>n>>q;
  86.     vector<ll>s(n);
  87.     for(int i=0;i<n;i++)
  88.     {
  89.         cin>>s[i];
  90.     }
  91.     SegmentTree tree(s);
  92.     while(q--)
  93.     {
  94.         int op;cin>>op;
  95.         if(op==1)
  96.         {
  97.             int idx;cin>>idx;
  98.             tree.update(idx);
  99.         }
  100.         else
  101.         {
  102.             int k;cin>>k;
  103.             cout<<tree.query(k+1)<<'\n';
  104.         }
  105.     }
  106.     return 0;
  107. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/9k76kS
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!