Guest User

flipcoinerror

a guest
Jan 27th, 2015
180
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. #include<string.h>
  5. #include<stdlib.h>
  6. #include<math.h>
  7. #include<stdio.h>
  8. #include<cmath>
  9. #define MAX (1<<17+5)
  10. long long int tree[6*1000000];
  11. long long int lazy[6*1000000];
  12.  
  13. void update_tree(long long int node,long long   int a,long long  int b,long long  int i,long long  int j) {
  14.  
  15.     if(lazy[node] == 1) { // This node needs to be updated
  16.       tree[node] = abs( (b-a+1) - tree[node]); // Update it // ***** absolute is vimp
  17.  
  18.         if(a != b) {
  19.             lazy[node*2] = 1-lazy[node*2]; // Mark child as lazy
  20.             lazy[node*2+1] = 1-lazy[node*2+1]; // Mark child as lazy
  21.         }
  22.  
  23.         lazy[node] = 0; // Reset it
  24.     }
  25.  
  26.     if(a > b || a > j || b < i) // Current segment is not within range [i, j]
  27.         return;
  28.  
  29.     if(a >= i && b <= j) { // Segment is fully within range
  30.              tree[node] = abs((b-a+1) - tree[node]); // Update it // ***** absolute is vimp
  31.  
  32.         if(a != b) { // Not leaf node
  33.             lazy[node*2] = 1;
  34.             lazy[node*2+1] = 1;
  35.         }
  36.  
  37.             return;
  38.     }
  39.  
  40.     update_tree(node*2, a, (a+b)/2, i, j); // Updating left child
  41.     update_tree(1+node*2, 1+(a+b)/2, b, i, j); // Updating right child
  42.  
  43.     tree[node] = tree[node*2] + tree[node*2+1]; // Updating root with max value
  44. }
  45.  
  46. long long int query_tree(long long  int node,long long  int a,long long  int b,long long  int i,long long  int j) {
  47.  
  48.     if(lazy[node] == 1) { // This node needs to be updated
  49.  
  50.         tree[node] = abs((b-a+1) - tree[node]); // Update it
  51.  
  52.         if(a != b) {
  53.             lazy[node*2] = 1-lazy[node*2]; // Mark child as lazy
  54.             lazy[node*2+1] = 1-lazy[node*2+1]; // Mark child as lazy
  55.         }
  56.  
  57.         lazy[node] = 0; // Reset it
  58.     }
  59.  
  60.     if(a > b || a > j || b < i) return 0; // Out of range
  61.     if(a >= i && b <= j) // Current segment is totally within range [i, j]
  62.         return tree[node];
  63.  
  64.     long long int q1= 0 ;
  65.     q1 = query_tree(node*2, a, (a+b)/2, i, j); // Query left child
  66.     long long int q2 =0 ;
  67.     q2 = query_tree(1+node*2, 1+(a+b)/2, b, i, j); // Query right child
  68.  
  69.     long long int res = q1 + q2; // Return final result
  70.  
  71.     return res;
  72. }
  73.  
  74. int main() {
  75.   long long  int N,Q ;
  76.   long long  int a,b,c ;
  77.  
  78.  
  79.   //for(int i = 0; i < N; i++) arr[i] = 0;
  80.  
  81.   memset(tree,0,sizeof(tree));
  82.   memset(lazy,0,sizeof(lazy));
  83.  
  84.   scanf("%lld %lld",&N, &Q) ;
  85.  
  86.   for (long long int i=0; i < Q; i++) {
  87.     scanf("%lld %lld %lld",&a,&b,&c);
  88.  
  89.     if (a==1)
  90.       {
  91.         printf("%lld\n",query_tree(1, 0, N-1, b, c)) ;
  92.       }
  93.     else if (a==0)
  94.       {
  95.         update_tree(1, 0, N-1, b, c);
  96.       }
  97.   }
  98.   return 0;
  99. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×