fork download
copy 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "icebear"
  33.  
  34. const int MOD = 1e9 + 7;
  35. const int inf = 1e9 + 27092008;
  36. const ll INF = 1e18 + 27092008;
  37. const int N = 1e5 + 5;
  38. const int BLOCK_SIZE = 300;
  39. int n, q, k, a[N];
  40. vector<int> masks[15];
  41. struct Query {
  42.     int l, r, id;
  43.     bool operator < (const Query &other) const {
  44.         if (l / BLOCK_SIZE != other.l / BLOCK_SIZE) return l < other.l;
  45.         return r < other.r;
  46.     }
  47. } Q[N];
  48.  
  49. struct Segment {
  50.     int l, r, id, sign;
  51.     Segment(int _l = 0, int _r = 0, int _id = 0, int _sign = 0):
  52.         l(_l), r(_r), id(_id), sign(_sign) {}
  53. };
  54. vector<Segment> segments[N];
  55. ll pref[N], ans[N];
  56. int cnt[N];
  57.  
  58. void init(void) {
  59.     cin >> n >> q >> k;
  60.     FOR(i, 1, n) cin >> a[i];
  61.     FOR(i, 1, q) cin >> Q[i].l >> Q[i].r, Q[i].id = i;
  62.     REP(i, MASK(14)) masks[__builtin_popcount(i)].pb(i);
  63.     sort(Q + 1, Q + q + 1);
  64. }
  65.  
  66. void process(void) {
  67.     // f(l, r, p) : answer while adding a[p]
  68.     // F(r, p) = f(1, r, p)
  69.  
  70.     int L = 1, R = 0;
  71.     FOR(i, 1, q) {
  72.         int l = Q[i].l, r = Q[i].r;
  73.         // f(l, r + 1, r + 1) - f(l, r, r) = F(r + 1, r + 1) - F(l - 1, r + 1)
  74.         if (R < r) segments[L - 1].emplace_back(R + 1, r, Q[i].id, -1), R = r;
  75.         // f(l - 1, r, l - 1) - f(l, r, l) = F(r, l - 1) - F(l - 1, l - 1)
  76.         if (L > l) segments[R].emplace_back(l, L - 1, Q[i].id, +1), L = l;
  77.         // f(l, r, r) - f(l, r - 1, r - 1) = -F(r, r) + F(l - 1, r)
  78.         if (R > r) segments[L - 1].emplace_back(r + 1, R, Q[i].id, +1), R = r;
  79.         // f(l, r, l) - f(l + 1, r, l + 1) = -F(r, l) + F(l, l)
  80.         if (L < l) segments[R].emplace_back(L, l - 1, Q[i].id, -1), L = l;
  81.     }
  82.  
  83.     FOR(i, 1, n) {
  84.         for(int x : masks[k]) cnt[a[i] ^ x]++;
  85.         pref[i] = pref[i - 1] + cnt[a[i]];
  86.  
  87.         for(auto event : segments[i]) {
  88.             ll sum = 0;
  89.             FOR(i, event.l, event.r) sum += cnt[a[i]];
  90.             ans[event.id] += sum * event.sign;
  91.         }
  92.     }
  93.  
  94.     L = 1, R = 0;
  95.     FOR(i, 1, q) {
  96.         int l = Q[i].l, r = Q[i].r;
  97.         if (R < r) ans[Q[i].id] += pref[r] - pref[R], R = r;
  98.         if (R > r) ans[Q[i].id] -= pref[R] - pref[r], R = r;
  99.         if (L > l) ans[Q[i].id] -= pref[L - 1] - pref[l - 1], L = l;
  100.         if (L < l) ans[Q[i].id] += pref[l - 1] - pref[L - 1], L = l;
  101.         ans[Q[i].id] += ans[Q[i - 1].id]; // changes + before
  102.     }
  103.  
  104.     FOR(i, 1, q) cout << ans[i] << '\n';
  105. }
  106.  
  107. int main() {
  108.     ios_base::sync_with_stdio(0);
  109.     cin.tie(0); cout.tie(0);
  110.     if (fopen(task".inp", "r")) {
  111.         freopen(task".inp", "r", stdin);
  112.         freopen(task".out", "w", stdout);
  113.     }
  114.     int tc = 1;
  115. //    cin >> tc;
  116.     while(tc--) {
  117.         init();
  118.         process();
  119.     }
  120.     return 0;
  121. }
Success #stdin #stdout 0.01s 7688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0eDFQa
language:
C++14 (gcc 8.3)
created:
5 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!