fork download
copy 
  1. #include<bits/stdc++.h>
  2. //#pragma GCC optimize "trapv"
  3. //#include<ext/pb_ds/assoc_container.hpp>
  4. //#include<ext/pb_ds/tree_policy.hpp>
  5. #define fast_az_fuk      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  6. #define ll               long long
  7. #define lll              __int128
  8. #define ull              unsigned ll
  9. #define ld               long double 
  10. #define pb               push_back 
  11. #define pf               push_front
  12. #define dll              deque<ll> 
  13. #define vll              vector<ll>
  14. #define vvll             vector<vll> 
  15. #define pll              pair<ll,ll> 
  16. #define vpll             vector<pll>
  17. #define dpll             deque<pll>
  18. #define mapll            map<ll,ll>
  19. #define umapll           umap<ll,ll>
  20. // #define endl             "\n" 
  21. #define all(v)           v.begin(),v.end() 
  22. #define ms(a,x)          memset(a,x,sizeof(a))
  23. #define random(l,r,T)    uniform_int_distribution<T>(l,r)(rng)
  24.  
  25.  
  26. //#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
  27.  
  28. using namespace std;
  29.  
  30.  
  31. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  32. //using namespace __gnu_pbds;
  33.  
  34. template<typename T> istream& operator >>(istream &in,vector<T> &v){ for(auto &x:v) in>>x; return in;}
  35. template<typename T> ostream& operator <<(ostream &out,const vector<T> &v){ for(auto &x:v) out<<x<<' '; return out;}
  36. template<typename T1,typename T2> istream& operator >>(istream &in,pair<T1,T2> &p){ in>>p.first>>p.second; return in;}
  37. template<typename T1,typename T2> ostream& operator <<(ostream &out,const pair<T1,T2> &p){ out<<p.first<<' '<<p.second; return out;}
  38. ll sumn,sumq;
  39. const bool tests = 1;
  40. void solve_case(){
  41.     ll n; cin>>n; vll a(n); cin>>a; assert(n >= 1 && n <= 1e5);
  42.     sumn+=n;
  43.     for(ll x : a){
  44.         assert(x>=0 && x<=1e9);
  45.     }
  46.     int bt = 0; while((1<<bt) < n) ++bt;
  47.     vvll dp((1<<bt),vll(bt+1));
  48.     for(int i=0;i<(1<<bt);i++){
  49.         dp[i][0] = (i<n?a[i]:0);
  50.     }
  51.     for(int j=1;j<=bt;j++){
  52.         for(int i=0;i<(1<<bt);i++){
  53.             dp[i][j] += dp[i][j-1];
  54.             if(i & (1<<(j-1))){
  55.                 dp[i][j] += dp[i^(1<<(j-1))][j];
  56.             }
  57.         }
  58.     }
  59.     auto solve = [&](ll l,ll x){
  60.         if(x <= l){
  61.             return dp[x][bt];
  62.         }
  63.         ll ans = 0;
  64.         for(int i=bt-1;i>=0;i--){
  65.             if((x&(1<<i))){
  66.                 if((l&(1<<i)) == 0) {
  67.                     x ^= (1<<i);
  68.                 }
  69.                 else{
  70.                     ans += dp[x^(1<<i)][i];
  71.                 }
  72.             }
  73.             if(x <= l) {
  74.                 ans += dp[x][i]; break;
  75.             }
  76.         }
  77.         return ans;
  78.     };
  79.     ll q; cin>>q; ll ans = 0; assert(q>0 && q<=1e5);
  80.     sumq += q;
  81.     while(q--){
  82.         ll l,r,x; cin>>l>>r>>x;
  83.         assert(r >= l);
  84.         assert(l>=0&&l<n && r>=0 && r<n && x>=0 && x<=1e9);
  85.         x = (x + ans) % (1<<bt);
  86.         ans = solve(r,x) - (l>0?solve(l-1,x):0);
  87.         cout<<ans<<endl;
  88.     }
  89. }
  90.  
  91. int32_t main()
  92. {
  93.     #ifdef LOCAL
  94.         freopen("error.txt", "w", stderr);
  95.         clock_t clk = clock();
  96.     #endif
  97.     fast_az_fuk
  98.     sumn = sumq = 0;
  99.     ll testcase=1; if(tests) cin>>testcase;
  100.     cout<<fixed<<setprecision(10);
  101.     for(ll test=1;test<=testcase;test++)
  102.     {//cout<<"Case #"<<test<<": ";
  103.         solve_case();
  104.     }
  105.     assert(sumn >= 1 && sumn <= 1e5);
  106.     assert(sumq >= 1 && sumq <= 1e5);
  107.     #ifdef LOCAL
  108.         cerr << '\n'<<"Time (in s): " << double(clock() - clk) * 1.0 / CLOCKS_PER_SEC << '\n';
  109.     #endif
  110.     return 0;
  111. }
Runtime error #stdin #stdout #stderr 0.01s 5344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:41: void solve_case(): Assertion `n >= 1 && n <= 1e5' failed.
https://ideone.com/2z98Gc
language:
C++ (gcc 8.3)
created:
2 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!