fork download
  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
stdin
Standard input is empty
stdout
0
0