Advertisement
SuitNdtie

iZone fenwick tree

May 27th, 2019
145
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.88 KB | None | 0 0
  1. #include<stdio.h>
  2. int n;
  3. int const N = 1000010;
  4. struct elem{
  5.     int R,G,B;
  6. };
  7.  
  8. elem fwtree[N];
  9.  
  10. elem addE(elem a,elem b){
  11.     return {a.R + b.R ,a.G + b.G , a.B + b.B};
  12. }
  13.  
  14. elem minusE(elem a,elem b){
  15.     return {a.R - b.R ,a.G - b.G , a.B - b.B};
  16. }
  17.  
  18. void add(int I,elem e){
  19.     for(int i = I ; i <= n ; i+=(i&-i)){
  20.         fwtree[i] = addE(fwtree[i],e);
  21.     }
  22. }
  23.  
  24. elem query(int I){
  25.     elem ans = {0,0,0};
  26.     for(int i = I ; i > 0 ; i-=(i&-i)){
  27.         ans = addE(ans,fwtree[i]);
  28.     }
  29.     return ans;
  30. }
  31.  
  32. void check(elem e){
  33.     if(e.R > e.B && e.R > e.G){
  34.         printf("R\n");
  35.     }
  36.     else if(e.G > e.R && e.G > e.B){
  37.         printf("G\n");
  38.     }
  39.     else if(e.B > e.G && e.B > e.R){
  40.         printf("B\n");
  41.     }
  42.     else{
  43.         printf("None\n");
  44.     }
  45. }
  46.  
  47. void testelem(elem an){
  48.     printf("Test %d %d %d\n",an.R ,an.G,an.B);
  49. }
  50.  
  51. int main()
  52. {
  53.     int m;
  54.     scanf("%d",&n);
  55.     scanf("%d",&m);
  56.     for(int i = 0 ; i <= n ; i ++)fwtree[i] = {0,0,0};
  57.    
  58.     elem data[n+1];
  59.     for(int i = 1 ; i <= n ; i ++){
  60.         if(i % 3 == 1){
  61.             data[i] = {1,0,0};
  62.             add(i,{1,0,0});
  63.         }
  64.         else if(i%3 == 2){
  65.             data[i] = {0,1,0};
  66.             add(i,{0,1,0});
  67.         }
  68.         else if(i%3 == 0){
  69.             data[i] = {0,0,1};
  70.             add(i,{0,0,1});
  71.         }else{
  72.             printf("Error %d\n",i);
  73.             return 0;
  74.         }
  75.     }
  76.     for(int q = 0 ; q < m ; q ++){
  77.         int A;
  78.         scanf("%d",&A);
  79.         if(A == 1){
  80.             int idx;
  81.             char c;
  82.             scanf("%d %c",&idx,&c);
  83.             elem te = {0,0,0};
  84.             te = minusE(te,data[idx]);
  85.             if(c == 'R'){
  86.                 te.R++;
  87.                 data[idx] = {1,0,0};
  88.             }else if(c == 'G'){
  89.                 te.G++;
  90.                 data[idx] = {0,1,0};
  91.             }else if(c == 'B'){
  92.                 te.B++;
  93.                 data[idx] = {0,0,1};
  94.             }else{
  95.                 printf("Error %c\n",c);
  96.                 return 0;
  97.             }
  98.         //  printf("update (%d,%c): ",idx,c);testelem(te);
  99.             add(idx,te);
  100.         }
  101.         else if(A == 2){
  102.             int L,R;
  103.             scanf("%d %d",&L,&R);
  104.             elem an = minusE(query(R),query(L-1));
  105.         //  printf("query (%d,%d): ",L,R);testelem(an);
  106.             check(an);
  107.         }
  108.     }
  109.     return 0;
  110.    
  111.    
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement