fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. //#include <ext/pb_ds/assoc_container.hpp> // Common file
  4. //#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  5. //using namespace __gnu_pbds; //  order of key(keys strictly less than)  // find_by_order
  6. //typedef tree<long long,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
  7. //typedef tree<long long, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
  8. //IF WA CHECK FOR : -
  9. // 1 > EDGE CASES LIKE N=1 , N=0
  10. // 2 > SIGNED INTEGER OVERFLOW IN MOD
  11. // 3 > CHECK THE CODE FOR LOGICAL ERRORS AND SEG FAULTS
  12. // 4 > READ THE PS ONCE AGAIN , if having double diff less than 1e-8 is same.
  13. // 5 > You Have got AC .
  14. #define ll long long
  15. #define NUM (ll)1000000007
  16. #define inf (long long)(1e12)
  17. #define ff first
  18. #define ss second
  19. #define f(i,a,b) for(ll i=a;(i)<long(b);(i)++)
  20. #define fr(i,a,b) for(ll i=a;(i)>=(long long)(b);(i)--)
  21. #define it(b)  for(auto &it:(b))
  22. #define ff first
  23. #define ss second
  24. #define pb push_back
  25. #define mp make_pair
  26. typedef vector<ll> vll;
  27. typedef pair<ll,ll> pll;
  28. ll binpow( ll base , ll ex,ll mod=NUM) {
  29.     ll ans = 1;base = base % mod;
  30.     if(base==0){
  31.         return 0;
  32.     }
  33.     while (ex > 0) {
  34.         if (ex % 2 == 1) {
  35.             ans = (ans * base) % mod;
  36.         }
  37.         base = (base * base) % mod;
  38.         ex = ex / 2;
  39.     }
  40.     return ans;
  41. }
  42. void read(vll &arr,ll n) {
  43.     if (arr.size() != n) { arr.assign(n, 0); }for (int i = 0; i < n; i++)cin >> arr[i];
  44. }
  45. inline ll min(ll a,ll b){
  46.     if(a>b)return b;return a;
  47. }
  48. inline ll max(ll a, ll b){
  49.     if(a>b)return a;return b;
  50. }
  51. inline ll dif(ll a,ll b) {
  52.     if (a > b)return a - b;return b - a;
  53. }
  54. long long gcd(long long a,long long b) {
  55.     if (b == 0)return a;return gcd(b, a % b);
  56. }
  57. long long lcm(long long a,long long b) {
  58.     long long k = gcd(a, b);
  59.     return (a * b) / k;
  60. }
  61. vll fun(ll z){
  62.     vll res;f(i,0,21){
  63.         res.pb(z%2);z/=2;
  64.     }
  65.     reverse(res.begin(),res.end());
  66.     return res;
  67. }
  68. ll fun2(vector<vector<ll>>&dp,ll l,ll x)
  69. {
  70.     if(l<0){
  71.         return 0;
  72.     }
  73.     //from 0 to l and i|x;
  74.     if(x<=l) {
  75.         return dp[x][20];
  76.     }
  77.     else{
  78.         // string of x and l+1
  79.         vll a = fun(x);vll b = fun(l+1);
  80.         ll res=0;
  81.         ll p = 1<<20;
  82.         ll pref=x;
  83.         for(int i=0;i<=20;i++){
  84.             if(b[i]!=a[i]){
  85.                 if(b[i]==1){
  86.                     res+=dp[pref][20-i];
  87.                     break;
  88.                 }
  89.                 pref^=(1<<(20-i));a[i]=0;
  90.             }
  91.             if(a[i]){
  92.                 // that means we can set it to 0.
  93.                 res+=dp[pref^(1<<(20-i))][20-i];
  94.             }
  95.             p/=2;
  96.         }
  97.         return res;
  98.     }
  99. }
  100. void solve() {
  101.     int n;cin>>n;
  102.     ll z = 1;
  103.     while(z<n){
  104.         z*=2;
  105.     }
  106.     vector<ll>arr;read(arr,n);
  107.     // l to r sum of elements which have i|x = x
  108.     vector<vector<ll>>dp(n,vector<ll>(21));
  109.     for(int i=0;i<n;i++){
  110.         dp[i][0]=arr[i];
  111.         for(int k=1;k<=20;k++){
  112.             ll p = (1<<(k-1));
  113.             if((i^p)<i){
  114.                 // it's here dude .
  115.                 dp[i][k]=dp[i^p][k-1]+dp[i][k-1];
  116.             }
  117.             else{
  118.                 dp[i][k]=dp[i][k-1];
  119.             }
  120.         }
  121.     }
  122.     int q;cin>>q;
  123.     ll prev=0;
  124.     while(q--){
  125.         ll l,x,r;cin>>l>>r>>x;
  126.         x += prev;x%=z;
  127.         //from 0 to l and i|x;
  128.         ll k = fun2(dp,r,x)-fun2(dp,l-1,x);
  129.         cout<<k<<endl;prev=k;
  130.     }
  131. }
  132. int main() {
  133.     ios_base::sync_with_stdio(false);
  134.     cin.tie(NULL);cout.tie(NULL);
  135.     cout << fixed << showpoint;
  136.     cout << setprecision(12);
  137.     long long test_m = 1;
  138.     cin >> test_m;
  139.     //I WILL WIN .
  140.     while (test_m--) {
  141.         solve();
  142.     }
  143. }
Success #stdin #stdout 0.01s 5440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/e1oU1m
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!