fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <stdio.h>
  4. using namespace std;
  5. typedef vector<int> vi;
  6. class segTree{
  7. public:
  8.     segTree(vi &main,int sz){markers.assign(4*sz+4,0); lazy.assign(4*sz+4,0); st.assign(4*sz+4,0); A=main; buildTree(1,0,sz-1);}
  9.         vi st,A,lazy;
  10.         vector<bool> markers;
  11.         int buildTree(int,int,int);
  12.         int query(int,int,int,int,int);
  13.         int update(int,int,int,int,int,int);
  14.         int left(int p){return (p<<1);}
  15.         int right(int p){ return (p<<1)+1;}
  16.  
  17. };
  18. int main()
  19. {
  20.  
  21.  
  22.  
  23.         int t;
  24.         scanf("%d",&t);
  25.         for(int test=1;test<=t;++test)
  26.         {       
  27.                 int m;
  28.                 scanf("%d",&m);
  29.                 vi temp(1024001,0);
  30.                 int n = 0;
  31.                 while(m--)
  32.                 {
  33.                         int T;
  34.                         scanf("%d",&T);
  35.                         char s[65];
  36.                         scanf("%s",s);
  37.                         while(T--)
  38.                         {
  39.                            for(int i=0;s[i];++i)
  40.     						temp[n++] = s[i]-48;
  41.                         }
  42.                }
  43.                 segTree st(temp,n);
  44.  
  45.                 int q;
  46.                 scanf("%d",&q);
  47.                 cout<<q;
  48.                 int asks = 1;
  49.                 printf("Case %d:\n",test);
  50.                 while(q--)
  51.                 {
  52.                         char c[4];
  53.                         int i,j;
  54.                         scanf("%s%d%d",c,&i,&j);
  55.  
  56.                        switch(c[0]){
  57. 							case 'F':st.update(1,0,n-1,i,j,1); break;
  58. 							case 'E':st.update(1,0,n-1,i,j,0); break;
  59.                             case 'I':st.update(1,0,n-1,i,j,-1); break;
  60. 							case 'S':printf("Q%d: %d\n",asks++,st.query(1,0,n-1,i,j));
  61. 							}
  62.  
  63.  
  64.                 }
  65.  
  66.  
  67.  
  68.  
  69.  
  70.  
  71.  
  72.         }       
  73.  
  74.  
  75. }
  76.  
  77.  
  78.  
  79. int segTree::buildTree(int p,int L,int R)
  80. {
  81.         if(L==R)
  82.         {       
  83.                 st[p] = A[L]; 
  84.                 return st[p]; 
  85.         }
  86.  
  87.         int a = buildTree(left(p),L,(L+R)/2) , b = buildTree(right(p),(L+R)/2+1,R);
  88.         st[p] = a+b;
  89.         return st[p];
  90.  
  91. }
  92.  
  93. int segTree::query(int p,int L,int R,int i,int j)
  94. {
  95.  
  96.         if(j<L||i>R) return -1;
  97.         if(markers[p])
  98.         {
  99.                 if(lazy[p] == 1)
  100.                 {
  101.                         st[p] = R - L + 1;
  102.                         if(L!=R){
  103.                         lazy[left(p)] = 1;
  104.                         lazy[right(p)] = 1;
  105.                         markers[left(p)] = 1;
  106.                         markers[right(p)] = 1;
  107.                 }
  108.                 }
  109.                 else if(lazy[p] == 0)
  110.                 {
  111.                         st[p] = 0;
  112.                 if(L!=R)
  113.                 {
  114.                         lazy[left(p)] = 0;
  115.                         lazy[right(p)] = 0;
  116.                         markers[left(p)] = 1;
  117.                         markers[right(p)] = 1;
  118.                 }
  119.                 }
  120.                 else if(lazy[p] == -1)
  121.                 {
  122.                         st[p] = (R-L+1) - st[p];
  123.                         if(L!=R)
  124.                         {
  125.                                 if(!markers[left(p)])
  126.                                 {
  127.                                         lazy[left(p)] = -1;
  128.                                         markers[left(p)] = 1;
  129.                                 }
  130.                                 else
  131.                                 {
  132.                                         if(lazy[left(p)] == 1)
  133.                                                 lazy[left(p)] = 0;
  134.                                         else if(lazy[left(p)]== 0)
  135.                                                 lazy[left(p)] = 1;
  136.                                         else if(lazy[left(p)] == -1)
  137.                                                 markers[left(p)] = 0; 
  138.  
  139.                                 }
  140.                                 if(!markers[right(p)])
  141.                                 {
  142.                                         lazy[right(p)] = -1;
  143.                                         markers[right(p)] = 1;
  144.                                 }
  145.                                 else
  146.                                 {
  147.                                         if(lazy[right(p)] == 1)
  148.                                                 lazy[right(p)] = 0;
  149.                                         else if(lazy[right(p)]== 0)
  150.                                                 lazy[right(p)] = 1;
  151.                                         else if(lazy[right(p)] == -1)
  152.                                                 markers[right(p)] = 0; 
  153.  
  154.                                 }
  155.  
  156.                         }       
  157.  
  158.  
  159.                 }
  160.  
  161.  
  162.         }
  163.         markers[p] = 0;
  164.         if(j<L||i>R) return -1;
  165.         if(L >= i && R <= j)
  166.         {       
  167.                 return st[p]; 
  168.         }
  169.         int a = query(left(p),L,(L+R)/2,i,j);
  170.         int b = query(right(p),(L+R)/2+1,R,i,j);
  171.         if(a==-1)
  172.                 return b;
  173.         if(b==-1)
  174.                 return a;       
  175.  
  176.         return a+b;
  177.  
  178. }
  179.  
  180.  
  181. int segTree::update(int p,int L,int R,int i,int j,int v)
  182. {
  183.         if(markers[p])
  184.         {
  185.                 if(lazy[p] == 1)
  186.                 {
  187.                         st[p] = R - L + 1;
  188.                         if(L!=R){
  189.                         lazy[left(p)] = 1;
  190.                         lazy[right(p)] = 1;
  191.                         markers[left(p)] = 1;
  192.                         markers[right(p)] = 1;
  193.                 }
  194.                 }
  195.                 else if(lazy[p] == 0)
  196.                 {
  197.                         st[p] = 0;
  198.                 if(L!=R)
  199.                 {
  200.                         lazy[left(p)] = 0;
  201.                         lazy[right(p)] = 0;
  202.                         markers[left(p)] = 1;
  203.                         markers[right(p)] = 1;
  204.                 }
  205.                 }
  206.                 else if(lazy[p] == -1)
  207.                 {
  208.                         st[p] = (R-L+1) - st[p];
  209.                         if(L!=R)
  210.                         {
  211.                                 if(!markers[left(p)])
  212.                                 {
  213.                                         lazy[left(p)] = -1;
  214.                                         markers[left(p)] = 1;
  215.                                 }
  216.                                 else
  217.                                 {
  218.                                         if(lazy[left(p)] == 1)
  219.                                                 lazy[left(p)] = 0;
  220.                                         else if(lazy[left(p)]== 0)
  221.                                                 lazy[left(p)] = 1;
  222.                                         else if(lazy[left(p)] == -1)
  223.                                                 markers[left(p)] = 0; 
  224.  
  225.                                 }
  226.                                 if(!markers[right(p)])
  227.                                 {
  228.                                         lazy[right(p)] = -1;
  229.                                         markers[right(p)] = 1;
  230.                                 }
  231.                                 else
  232.                                 {
  233.                                         if(lazy[right(p)] == 1)
  234.                                                 lazy[right(p)] = 0;
  235.                                         else if(lazy[right(p)]== 0)
  236.                                                 lazy[right(p)] = 1;
  237.                                         else if(lazy[right(p)] == -1)
  238.                                                 markers[right(p)] = 0; 
  239.  
  240.                                 }
  241.  
  242.                         }       
  243.  
  244.  
  245.                 }
  246.  
  247.  
  248.         }
  249.         markers[p] = 0;
  250.         if(L >= i && R <= j)
  251.         {
  252.                 if(v==1)
  253.                 {
  254.                         st[p] = R-L+1;
  255.                 if(L!=R){
  256.                         lazy[left(p)] = 1;
  257.                         lazy[right(p)] = 1;
  258.                         markers[left(p)] = 1;
  259.                         markers[right(p)] = 1;
  260.                 }
  261.                 }
  262.                 else if(v == 0)
  263.                 {
  264.                         st[p] = 0;
  265.                 if(L!=R){
  266.                         lazy[left(p)] = 0;
  267.                         lazy[right(p)] = 0;
  268.                         markers[left(p)] = 1;
  269.                         markers[right(p)] = 1;
  270.                 }
  271.                 }
  272.                 else if(v == -1)
  273.                 {
  274.                         st[p] = (R - L + 1) - st[p];
  275.                         if(L!=R)
  276.                         {
  277.                                 if(!markers[left(p)])
  278.                                 {
  279.                                         lazy[left(p)] = -1;
  280.                                         markers[left(p)] = 1;
  281.                                 }
  282.                                 else
  283.                                 {
  284.                                         if(lazy[left(p)] == 1)
  285.                                                 lazy[left(p)] = 0;
  286.                                         else if(lazy[left(p)]== 0)
  287.                                                 lazy[left(p)] = 1;
  288.                                         else if(lazy[left(p)] == -1)
  289.                                                 markers[left(p)] = 0; 
  290.  
  291.                                 }
  292.                                 if(!markers[right(p)])
  293.                                 {
  294.                                         lazy[right(p)] = -1;
  295.                                         markers[right(p)] = 1;
  296.                                 }
  297.                                 else
  298.                                 {
  299.                                         if(lazy[right(p)] == 1)
  300.                                                 lazy[right(p)] = 0;
  301.                                         else if(lazy[right(p)]== 0)
  302.                                                 lazy[right(p)] = 1;
  303.                                         else if(lazy[right(p)] == -1)
  304.                                                 markers[right(p)] = 0; 
  305.  
  306.                                 }
  307.  
  308.                         }
  309.  
  310.                 }
  311.  
  312.                 return st[p];
  313.         }
  314.         if(L==R)
  315.                 return st[p];
  316.         int a = update(left(p),L,(L+R)/2,i,j,v);
  317.         int b = update(right(p),(L+R)/2+1,R,i,j,v);
  318.         st[p] = a+b;
  319.         return a+b;
  320. }
  321.  
Success #stdin #stdout 0s 3304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WDK1eu
language:
C++ (gcc 8.3)
created:
10 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!