fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define li pair<long long , int>
  10. #define db double
  11. #define onBit(mask , i) (mask | (1 << i))
  12. #define offBit(mask , i) (mask & (~(1 << i)))
  13.  
  14. const long long MOD = 1e9 + 7;
  15. const long long INF = 1e14;
  16. const int N = 1e5 + 7;
  17. int n , q;
  18. int t[29][4 * N] , nil[29];
  19. long long lazy[4 * N] , a[N] , pre[N];
  20.  
  21. void push(int id , int l , int mid , int r){
  22.     if (lazy[id]){
  23.         lazy[id << 1] ^= lazy[id];
  24.         lazy[id << 1 | 1] ^= lazy[id];
  25.         for (int i = 0 ; i <= 27 ; ++i){
  26.             if (Bit(lazy[id] , i)) t[i][id << 1] = (mid - l + 1) - t[i][id << 1];
  27.             if (Bit(lazy[id] , i)) t[i][id << 1 | 1] = (r - mid) - t[i][id << 1 | 1];
  28.         }
  29.         lazy[id] = 0;
  30.     }
  31. }
  32.  
  33. void build(int id , int l , int r){
  34.     if (l == r){
  35.         for (int i = 0 ; i <= 27 ; ++i){
  36.             t[i][id] = Bit(pre[l - 1] , i);
  37.         }
  38.         return;
  39.     }
  40.  
  41.     int mid = (l + r) >> 1;
  42.     build(id << 1 , l , mid);
  43.     build(id << 1 | 1 , mid + 1 , r);
  44.     for (int i = 0 ; i <= 27 ; ++i){
  45.         t[i][id] = t[i][id << 1] + t[i][id << 1 | 1];
  46.     }
  47. }
  48.  
  49. void get(int id , int l , int r , int u , int v){
  50.     if (l > v || r < u) return;
  51.     if (u <= l && r <= v){
  52.         for (int i = 0 ; i <= 27 ; ++i){
  53.             nil[i] += t[i][id];
  54.         }
  55.         return;
  56.     }
  57.  
  58.     int mid = (l + r) >> 1;
  59.     push(id , l , mid , r);
  60.     get(id << 1 , l , mid , u , v);
  61.     get(id << 1 | 1 , mid + 1 , r , u , v);
  62. }
  63.  
  64. void update(int id , int l , int r , int u , int v , long long val){
  65.     if (l > v || r < u) return;
  66.     if (u <= l && r <= v){
  67.         for (int i = 0 ; i <= 27 ; ++i) if (Bit(val , i)){
  68.             t[i][id] = (r - l + 1) - t[i][id];
  69.         }
  70.         lazy[id] ^= val;
  71.         return;
  72.     }
  73.  
  74.     int mid = (l + r) >> 1;
  75.     push(id , l , mid , r);
  76.     update(id << 1 , l , mid , u , v , val);
  77.     update(id << 1 | 1 , mid + 1 , r , u , v , val);
  78.     for (int i = 0 ; i <= 27 ; ++i){
  79.         t[i][id] = t[i][id << 1] + t[i][id << 1 | 1];
  80.     }
  81. }
  82.  
  83. void inp(){
  84.     cin >> n >> q;
  85.     for (int i = 1 ; i <= n ; ++i){
  86.         cin >> a[i];
  87.         pre[i] = pre[i - 1] ^ a[i];
  88.     }
  89.     build(1 , 1 , n + 1);
  90. }
  91.  
  92. void solve(){
  93.     while (q--){
  94.         int c;
  95.         cin >> c;
  96.         if (c == 1){
  97.             int pos;
  98.             long long val;
  99.             cin >> pos >> val;
  100.             a[pos] ^= val;
  101.             swap(a[pos] , val);
  102.             update(1 , 1 , n + 1 , pos + 1 , n + 1 , val);
  103.         }
  104.         if (c == 2){
  105.             memset(nil , 0 , sizeof nil);
  106.             int l , r;
  107.             cin >> l >> r;
  108.             ++r;
  109.             get(1 , 1 , n + 1 , l , r);
  110.             long long res = 0;
  111.             for (int i = 0 ; i <= 27 ; ++i){
  112.                 res += 1LL * (1LL << i) * nil[i] * (r - l + 1 - nil[i]);
  113.             }
  114.             cout << res << '\n';
  115.         }
  116.     }
  117. }
  118.  
  119. int main(){
  120. //	freopen("xhmax.inp" , "r" , stdin);
  121. //	freopen("xhmax.out" , "w" , stdout);
  122.     faster;
  123.     inp();
  124.     solve();
  125.     return 0;
  126. }
  127.  
Success #stdin #stdout 0.01s 48724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/j0MnED
language:
C++14 (gcc 8.3)
created:
3 days 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!