fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. void io()
  5. {
  6. #ifndef ONLINE_JUDGE
  7.   freopen("input.txt", "r", stdin);
  8. #endif
  9. }
  10. int c2(int n) { return (n * (n - 1) / 2); }            /* nC2 */
  11. int c3(int n) { return (n * (n - 1) * (n - 2)) / 6; }; /* nC3*/
  12.  
  13. int k;
  14. struct node
  15. {
  16.   vector<int> freq;
  17.   node()
  18.   {
  19.     freq.resize(k, 0);
  20.   }
  21.   node(int val)
  22.   {
  23.     freq.resize(k, 0);
  24.     freq[(val % k + k) % k] = 1;
  25.   }
  26. };
  27. struct segtree
  28. {
  29.   vector<node> tree; /*each node holds freq of size k */
  30.   int size = 1;
  31.   void init(int n)
  32.   {
  33.     while (size < n)
  34.       size <<= 1;
  35.     tree.resize(2 * size);
  36.     for (int i = 0; i < 2 * size; i++)
  37.     {
  38.       tree[i] = node();
  39.     }
  40.   }
  41.   node combine(node &a, node &b) /* O(K) combine the freq */
  42.   {
  43.     node res;
  44.     for (int i = 0; i < k; i++)
  45.     {
  46.       res.freq[i] = a.freq[i] + b.freq[i];
  47.     }
  48.     return res;
  49.   }
  50.   void build(vector<int> &a, int x, int lx, int rx) /* O(n*k) */
  51.   {
  52.     if (rx - lx == 1)
  53.     {
  54.       if (lx < a.size())
  55.         tree[x] = node(a[lx]);
  56.       return;
  57.     }
  58.     int m = (rx + lx) >> 1;
  59.     build(a, 2 * x + 1, lx, m);
  60.     build(a, 2 * x + 2, m, rx);
  61.     tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
  62.   }
  63.   void build(vector<int> &a)
  64.   {
  65.     build(a, 0, 0, size);
  66.   }
  67.   void update(int i, int v, int x, int lx, int rx) /* O(log(n) * k) */
  68.   {
  69.     if (rx - lx == 1)
  70.     {
  71.       tree[x] = node(v);
  72.       return;
  73.     }
  74.     int m = (rx + lx) >> 1;
  75.     if (i < m)
  76.       update(i, v, 2 * x + 1, lx, m);
  77.     else
  78.       update(i, v, 2 * x + 2, m, rx);
  79.     tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
  80.   }
  81.   void update(int i, int v)
  82.   {
  83.     update(i, v, 0, 0, size);
  84.   }
  85.   node query(int l, int r, int x, int lx, int rx) /* O(log(n) * k) */
  86.   {
  87.     if (lx >= r || rx <= l)
  88.       return node();
  89.     if (lx >= l && rx <= r)
  90.       return tree[x];
  91.     int m = (rx + lx) >> 1;
  92.     node left = query(l, r, 2 * x + 1, lx, m), right = query(l, r, 2 * x + 2, m, rx);
  93.     return combine(left, right);
  94.   }
  95.   node query(int l, int r)
  96.   {
  97.     return query(l, r, 0, 0, size);
  98.   }
  99. };
  100. int cnttriples(vector<int> &freq) // O(k^2)
  101. {
  102.   int res = 0;
  103.   for (int i = 0; i < k; i++)
  104.   {
  105.     for (int j = i; j < k; j++)
  106.     {
  107.       int m = (k - (i + j) % k) % k;
  108.       if (m < j)
  109.         continue; // avoid duplicates
  110.  
  111.       if (i == j && j == m)
  112.       {
  113.         // all in
  114.         res += c3(freq[i]);
  115.       }
  116.       else if (i == j)
  117.       {
  118.         // two equal one unique
  119.         res += c2(freq[i]) * freq[m];
  120.       }
  121.       else if (j == m)
  122.       {
  123.         // two equal one unique
  124.         res += freq[i] * c2(freq[j]);
  125.       }
  126.       else
  127.       {
  128.         // all out
  129.         res += freq[i] * freq[j] * freq[m];
  130.       }
  131.     }
  132.   }
  133.   return res;
  134. }
  135.  
  136. signed main()
  137. {
  138.   io();
  139.   int n;
  140.   cin >> n >> k;
  141.   vector<int> a(n);
  142.   for (auto &i : a)
  143.     cin >> i;
  144.   segtree st; /* the segment is zero based exclusive right bound */
  145.   st.init(n);
  146.   st.build(a);
  147.   int q;
  148.   cin >> q;
  149.  
  150.   while (q--) // for type one O(log n * k ) / for type 2 O(k ^ 2  + log n * k )
  151.   // Worst case: O(q * max(log n * k, k^2))
  152.   {
  153.     int type;
  154.     cin >> type;
  155.     if (type == 1)
  156.     {
  157.       int i, v;
  158.       cin >> i >> v;
  159.       i--;
  160.       st.update(i, v);
  161.     }
  162.     else
  163.     {
  164.       int l, r;
  165.       cin >> l >> r;
  166.       l--;
  167.       node res = st.query(l, r);
  168.       cout << cnttriples(res.freq) << '\n';
  169.     }
  170.   }
  171.   return 0;
  172. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
6 5
-3 7 -2 4 -8 6
6
2 1 6
2 2 5
1 4 -1
2 1 6
1 2 0
2 1 6
stdout
copy 
3
0
3
4
https://ideone.com/KZY6EX
language:
C++14 (gcc 8.3)
created:
12 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!