fork download
copy 
  1. #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
  2. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  3.  
  4. #include<bits/stdc++.h>
  5. #include<iostream>
  6. #include<cstdio>
  7. #include<algorithm>
  8. #include<cstring>
  9. #include<string>
  10.  
  11. #include<ext/pb_ds/assoc_container.hpp>
  12. #include<ext/pb_ds/tree_policy.hpp>
  13.  
  14. using namespace std;
  15.  
  16. using namespace __gnu_pbds;
  17.  
  18.  
  19.  
  20. const int MAX_N = int(1e6) + 10;
  21. const long long int MOD=1e9+7;
  22. const long long int INF=1e18;
  23.  
  24.  
  25. typedef long long int ll;
  26. typedef unsigned long long int llu;
  27.  
  28.  
  29.  
  30.  
  31.  
  32. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  33.  
  34. int arr[100005];
  35.  
  36. map<int,pbds>mp[25];
  37.  
  38. int count2=0;
  39.  
  40. void add(int y,int z){
  41.   int val=arr[y];
  42.   int mask=0;
  43.   for(int j=0;j<23;j++){
  44.     mask=(mask<<1)+(((val>>j))&1);
  45.     mp[j][mask].erase(y);
  46.   }
  47.   arr[y]=z;
  48.   mask=0;
  49.   for(int j=0;j<23;j++){
  50.     mask=(mask<<1)+(((z>>j))&1);
  51.     mp[j][mask].insert(y);
  52.   }
  53. }
  54. ll l_r(int y,int z,int v){
  55.    ll ans=0;
  56.    int mask=(v&1);
  57.    count2=mp[0][mask].order_of_key(z+1)-mp[0][mask].order_of_key(y);
  58.    for(int j=1;j<=23;j++){
  59.     mask=(mask<<1)+(((v>>j))&1);
  60.     int count=mp[j][mask].order_of_key(z+1)-mp[j][mask].order_of_key(y);
  61.     ans+=(count2-count)*j;
  62.     count2=count;
  63.    }
  64.  
  65.    return ans;
  66. }
  67. int main()
  68. {
  69.   ios_base::sync_with_stdio(false);
  70.   cin.tie(NULL);
  71.  
  72.   // #ifndef ONLINE_JUDGE
  73.   // freopen("f.in","r",stdin);
  74.   // #endif
  75.  
  76.   int n,q;
  77.   cin>>n>>q;
  78.  
  79.   for(int i=1;i<=n;i++){
  80.     cin>>arr[i];
  81.     int mask=0;
  82.     for(int j=0;j<23;j++){
  83.         mask=(mask<<1)+((arr[i]>>j)&1);
  84.         //cout<<mask<<endl;
  85.      //   cout<<mp[mask].size()<<endl;
  86.         mp[j][mask].insert(i);
  87.     }
  88.   }
  89.  
  90.   for(int i=1;i<=q;i++){
  91.     int x,y,z;
  92.     cin>>x>>y>>z;
  93.     if(x==1){
  94.       add(y,z);
  95.     }else{
  96.       int v;
  97.       cin>>v;
  98.       cout<<l_r(y,z,v)<<endl;
  99.     }
  100.   }
  101.  
  102.   return 0;
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109. }
Success #stdin #stdout 0s 4308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
0
https://ideone.com/uiD2e5
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!