fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Block {
  5.     int L, R;
  6.     vector<int> a;
  7.     vector<int> parent, cnt;
  8.     int maxVal;
  9.     Block() {}
  10.     Block(int l, int r, const vector<int>& src) {
  11.         L = l; R = r;
  12.         a.assign(src.begin()+l, src.begin()+r+1);
  13.         maxVal = *max_element(a.begin(), a.end());
  14.         parent.assign(maxVal+1, 0);
  15.         cnt.assign(maxVal+1, 0);
  16.         iota(parent.begin(), parent.end(), 0);
  17.         for (int v : a) cnt[v]++;
  18.     }
  19.     int find(int x) {
  20.         if (x > maxVal) return -1;
  21.         if (parent[x] == x) return x;
  22.         return parent[x] = find(parent[x]);
  23.     }
  24.     void mergeVal(int u, int v) {
  25.         u = find(u); v = find(v);
  26.         if (u == -1 || v == -1) return;
  27.         if (u == v) return;
  28.         parent[u] = v;
  29.         cnt[v] += cnt[u];
  30.         cnt[u] = 0;
  31.     }
  32.     void rebuild(const vector<int>& src) {
  33.         a.assign(src.begin()+L, src.begin()+R+1);
  34.         maxVal = *max_element(a.begin(), a.end());
  35.         parent.resize(maxVal+1);
  36.         cnt.assign(maxVal+1,0);
  37.         iota(parent.begin(), parent.end(), 0);
  38.         for (int v : a) cnt[v]++;
  39.     }
  40.     void updatePart(vector<int>& src, int l, int r, int x) {
  41.         for (int i=l;i<=r;i++) {
  42.             if (src[i] > x) src[i] -= x;
  43.         }
  44.         rebuild(src);
  45.     }
  46.     void updateFull(int x) {
  47.         for (int v=x+1; v<=maxVal; v++) {
  48.             int u = find(v);
  49.             if (u> x) mergeVal(u, u-x);
  50.         }
  51.         maxVal = x;
  52.     }
  53.     int queryPart(vector<int>& src, int l, int r, int x) {
  54.         int res=0;
  55.         for (int i=l;i<=r;i++) if (src[i]==x) res++;
  56.         return res;
  57.     }
  58.     int queryFull(int x) {
  59.         if (x>maxVal) return 0;
  60.         return cnt[find(x)];
  61.     }
  62. };
  63.  
  64. int main() {
  65.     ios::sync_with_stdio(false);
  66.     cin.tie(nullptr);
  67.     int n,m; cin>>n>>m;
  68.     vector<int> a(n);
  69.     for (int i=0;i<n;i++) cin>>a[i];
  70.     int B = sqrt(n)+1;
  71.     vector<Block> blocks;
  72.     for (int i=0;i<n;i+=B) {
  73.         int j=min(n-1,i+B-1);
  74.         blocks.emplace_back(i,j,a);
  75.     }
  76.     while (m--) {
  77.         int t,l,r,x; cin>>t>>l>>r>>x; l--; r--;
  78.         int bl=l/B, br=r/B;
  79.         if (t==1) {
  80.             if (bl==br) {
  81.                 blocks[bl].updatePart(a,l,r,x);
  82.             } else {
  83.                 blocks[bl].updatePart(a,l,blocks[bl].R,x);
  84.                 blocks[br].updatePart(a,blocks[br].L,r,x);
  85.                 for (int i=bl+1;i<br;i++) blocks[i].updateFull(x);
  86.             }
  87.         } else {
  88.             long long ans=0;
  89.             if (bl==br) {
  90.                 ans+=blocks[bl].queryPart(a,l,r,x);
  91.             } else {
  92.                 ans+=blocks[bl].queryPart(a,l,blocks[bl].R,x);
  93.                 ans+=blocks[br].queryPart(a,blocks[br].L,r,x);
  94.                 for (int i=bl+1;i<br;i++) ans+=blocks[i].queryFull(x);
  95.             }
  96.             cout<<ans<<"\n";
  97.         }
  98.     }
  99. }
  100.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5 6
1 5 5 5 8
2 2 5 5
1 2 4 3
2 2 5 2
2 2 5 5
1 3 5 1
2 1 5 1
stdout
copy 
3
3
0
3
https://ideone.com/mpd68C
language:
C++14 (clang 8.0)
created:
3 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!