fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <string.h>
  5. #include <stdbool.h>
  6. #include <math.h>
  7. #include <vector>
  8. #include <map>
  9. #include <stack>
  10. #include <queue>
  11. #include <set>
  12. #define pb push_back
  13. #define ll long long int
  14. #define ull unsigned long long int
  15. #define gcd(a,b)    __gcd(a,b)
  16. #define sz sizeof
  17. #define INF 1000000000000000000LL
  18. #define ms memset
  19. #define MAX
  20.  
  21. using namespace std;
  22.  
  23.  
  24. int a[100010],tree[4*100010],lazy[4*100010];
  25. void build(int node,int s,int d){
  26.     if(s==d){
  27.         //cout<<"node: "<<node<<" val: "<<a[s]<<endl;
  28.         tree[node] = a[s];
  29.         return;
  30.     }
  31.     int Left = node*2;
  32.     int Right = node*2 + 1;
  33.     int mid = (s+d)/2;
  34.     build(Left,s,mid);
  35.     build(Right,mid+1,d);
  36.  
  37.     //update tree
  38.     tree[node] = tree[Left] + tree[Right];
  39. }
  40. void update(int node,int s,int d,int i,int j){
  41.     if(lazy[node]!=0){
  42.         if(lazy[node]%2==0){
  43.             // do nothing
  44.         }else{
  45.             tree[node] = (d-s+1) - tree[node];
  46.         }
  47.  
  48.         if(s!=d){
  49.             lazy[node*2] += lazy[node];
  50.             lazy[node*2+1] += lazy[node];
  51.         }
  52.         lazy[node]=0;
  53.     }
  54.  
  55.     //no overlap
  56.     if(s>j || d<i) return;
  57.     //total overlap
  58.     if(s>=i && d<=j){
  59.         tree[node] = (d-s+1) - tree[node];
  60.  
  61.         if(s!=d){
  62.             lazy[node*2]++;
  63.             lazy[node*2+1]++;
  64.         }
  65.         return ;
  66.     }
  67.     //partial overlap
  68.     int Left = node*2;
  69.     int Right = node*2 + 1;
  70.     int mid = (s+d)/2;
  71.     update(Left,s,mid,i,j);
  72.     update(Right,mid+1,d,i,j);
  73.  
  74.     //update tree
  75.     tree[node] = tree[Left] + tree[Right];
  76. }
  77. int query(int node,int s,int d,int i,int j){
  78.     if(lazy[node]!=0){
  79.         if(lazy[node]%2==0){
  80.             // do nothing
  81.         }else{
  82.             tree[node] = (d-s+1) - tree[node];
  83.         }
  84.  
  85.         if(s!=d){
  86.             lazy[node*2] += lazy[node];
  87.             lazy[node*2+1] += lazy[node];
  88.         }
  89.         lazy[node]=0;
  90.     }
  91.  
  92.     //no overlap
  93.     if(s>j || d<i){
  94.         return 0;
  95.     }
  96.     //total overlap
  97.     if(s>=i && d<=j){
  98.         return tree[node];
  99.     }
  100.     //partial overlap
  101.     int Left = node*2;
  102.     int Right = node*2 + 1;
  103.     int mid = (s+d)/2;
  104.     int p1=0,p2=0;
  105.     p1 = query(Left,s,mid,i,j);
  106.     p2 = query(Right,mid+1,d,i,j);
  107.     return p1+p2;
  108. }
  109.  
  110. int main()
  111. {
  112.     //freopen("a.in","r",stdin);
  113.     //freopen("out.txt","w",stdout);
  114.     //std::ios_base::sync_with_stdio(false);
  115.     int n,t,i,j,cases=1,q,u,v;
  116.     scanf("%d",&t);
  117.     getchar();
  118.     while(t--){
  119.         ms(a,0,sz(a));
  120.         ms(tree,0,sz(tree));
  121.         ms(lazy,0,sz(lazy));
  122.         char s[100010];
  123.         scanf("%s",&s);
  124.         for(i=0;i<strlen(s);i++){
  125.             a[i+1] = s[i]-'0';
  126.         }
  127.         n = strlen(s);
  128.         build(1,1,n);
  129.         printf("Case %d:\n",cases);cases++;
  130.         scanf("%d",&q);
  131.         getchar();
  132.         char ch;
  133.         while(q--){
  134.             scanf("%c",&ch);
  135.             if(ch=='I'){
  136.                 scanf("%d %d",&u,&v);
  137.                 update(1,1,n,u,v);
  138.             }else{
  139.                 scanf("%d",&u);
  140.                 int bit = query(1,1,n,u,u);
  141.                 printf("%d\n",bit);
  142.             }
  143.             getchar();
  144.         }
  145.     }
  146.  
  147.  
  148.  
  149.     return 0;
  150. }
  151.  
Success #stdin #stdout 0s 6988KB
comments (?)
stdin
copy 
2
0011001100
6
I 1 10
I 2 7
Q 2
Q 1
Q 7
Q 5
1011110111
6
I 1 10
I 2 7
Q 2
Q 1
Q 7
Q 5
stdout
copy 
Case 1:
0
1
1
0
Case 2:
0
0
0
1
https://ideone.com/gPBp15
language:
C++14 (gcc 8.3)
created:
7 years 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!