fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define pb push_back
  5. #define PI acos(-1.0)
  6. #define inf 0x7f7f7f7f
  7. #define mod 1000000007
  8. //////////////////////////////////////////////
  9. //////////////////////////////////////////////
  10. #define L n*2
  11. #define R n*2+1
  12. #define M (int)((b+e)/2)
  13. #define Node tree[n]
  14. #define Right tree[R]
  15. #define Left tree[L]
  16. ///////////////////////////////////////////////
  17. ///////////////////////////////////////////////
  18.  
  19. struct info{int s,p;} tree[4*1024006];
  20. string s;
  21.  
  22. void Build(int n, int b, int e)
  23. {
  24.     if(b==e){
  25.         Node.s = s[b]-'0';
  26.         Node.p = -1;
  27.         return;
  28.     }
  29.     Build(L,b,M);
  30.     Build(R,M+1,e);
  31.     Node.s = Left.s + Right.s;
  32. }
  33.  
  34. void Update(int n, int b, int e, int x, int y, int v)
  35. {
  36.     if(Node.p!=-1){
  37.         if(Node.p==2) Node.s = (e-b+1) - Node.s;
  38.         else Node.s = (e-b+1) * Node.p;
  39.         if(b!=e){
  40.             if(Node.p==2){
  41.                 if(Left.p==0) Left.p=1;
  42.                 if(Left.p==1) Left.p=0;
  43.                 if(Left.p==2) Left.p=-1;
  44.                 if(Left.p==-1) Left.p=2;
  45.  
  46.                 if(Right.p==0) Right.p=1;
  47.                 if(Right.p==1) Right.p=0;
  48.                 if(Right.p==2) Right.p=-1;
  49.                 if(Right.p==-1) Right.p=2;
  50.             }
  51.             else Left.p = Right.p = Node.p;
  52.         }
  53.         Node.p = -1;
  54.     }
  55.     if(b>y || e<x) return;
  56.     if(b>=x && e<=y){
  57.         if(v==2) Node.s = (e-b+1) - Node.s;
  58.         else Node.s = (e-b+1)*v;
  59.         if(v==2){
  60.             if(Left.p==0) Left.p=1;
  61.             if(Left.p==1) Left.p=0;
  62.             if(Left.p==2) Left.p=-1;
  63.             if(Left.p==-1) Left.p=2;
  64.  
  65.             if(Right.p==0) Right.p=1;
  66.             if(Right.p==1) Right.p=0;
  67.             if(Right.p==2) Right.p=-1;
  68.             if(Right.p==-1) Right.p=2;
  69.             return;
  70.         }
  71.         Left.p = Right.p = v;
  72.         return;
  73.     }
  74.     Update(L,b,M,x,y,v);
  75.     Update(R,M+1,e,x,y,v);
  76.     Node.s = Left.s + Right.s;
  77. }
  78.  
  79. int Find(int n, int b, int e, int x, int y)
  80. {
  81.     if(Node.p!=-1){
  82.         if(Node.p==2) Node.s = (e-b+1) - Node.s;
  83.         else Node.s = (e-b+1) * Node.p;
  84.         if(b!=e){
  85.             if(Node.p==2){
  86.                 if(Left.p==0) Left.p=1;
  87.                 if(Left.p==1) Left.p=0;
  88.                 if(Left.p==2) Left.p=-1;
  89.                 if(Left.p==-1) Left.p=2;
  90.  
  91.                 if(Right.p==0) Right.p=1;
  92.                 if(Right.p==1) Right.p=0;
  93.                 if(Right.p==2) Right.p=-1;
  94.                 if(Right.p==-1) Right.p=2;
  95.             }
  96.             else Left.p = Right.p = Node.p;
  97.         }
  98.         Node.p = -1;
  99.     }
  100.  
  101.     if(b>y || e<x) return 0;
  102.     if(b>=x && e<=y) return Node.s;
  103.     int f1 = Find(L,b,M,x,y);
  104.     int f2 = Find(R,M+1,e,x,y);
  105.     return f1+f2;
  106. }
  107.  
  108. int main()
  109. {
  110.     //freopen("Pin.txt","r",stdin);
  111.     //freopen("P.txt","w",stdout);
  112.     int test,cs=1;
  113.     int n,m,q,i,j;
  114.     scanf("%d",&test);
  115.     while(test--){
  116.         printf("Case %d:\n",cs++);
  117.         scanf("%d",&m);
  118.         s="0";
  119.         while(m--){
  120.             int t;
  121.             string str;
  122.             scanf("%d",&t);
  123.             cin>>str;
  124.             while(t--) s+=str;
  125.         }
  126.         n = s.size()-1;
  127.         //cout<<s<<endl;
  128.         //cout<<n<<endl;
  129.         for(i=0;i<=4*n;i++) tree[i].s=0 , tree[i].p = -1;
  130.         Build(1,1,n);
  131.         scanf("%d",&q);
  132.         int qs=1;
  133.         while(q--){
  134.             int x,y;
  135.             char ch;
  136.             getchar();
  137.             scanf("%c%d%d",&ch,&x,&y);
  138.             x++;
  139.             y++;
  140.             if(ch=='F') Update(1,1,n,x,y,1);
  141.             if(ch=='E') Update(1,1,n,x,y,0);
  142.             if(ch=='I') Update(1,1,n,x,y,2);
  143.             if(ch=='S') printf("Q%d: %d\n",qs++,Find(1,1,n,x,y));
  144.         }
  145.     }
  146.     return 0;
  147. }
  148.  
  149. /*
  150. 2
  151.  
  152. 2
  153. 5
  154. 10
  155. 2
  156. 1000
  157. 5
  158. F 0 17
  159. I 0 5
  160. S 1 10
  161. E 4 9
  162. S 2 10
  163.  
  164. 3
  165. 3
  166. 1
  167. 4
  168. 0
  169. 2
  170. 0
  171. 2
  172. I 0 2
  173. S 0 8
  174. */
  175.  
Success #stdin #stdout 0s 35480KB
comments (?)
stdin
copy 
2

2
5
10
2
1000
5
F 0 17
I 0 5
S 1 10
E 4 9
S 2 10

3
3
1
4
0
2
0
2
I 0 2
S 0 8
stdout
copy 
Case 1:
Q1: 5
Q2: 1
Case 2:
Q1: 0
https://ideone.com/WqfJUH
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!