fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define endl '\n'
  4. #define all(v) v.begin(), v.end()
  5. #define rall(v) v.rbegin(), v.rend()
  6. #define input(v) for(auto &a:v)cin>>a;
  7. #define output(v) for(auto &a:v)cout<<a<<" ";
  8. #define outputel(v) for(auto &a:v)cout<<a<<" ";cout<<endl;
  9. #define mem(arr) memset(arr,0,sizeof(arr));
  10. #define LSone(x) (x & (-x))
  11. #define YNO(x) cout<<(x ? "YES" : "NO")<<endl;
  12. #define sz(x) (ll)x.size()
  13. #define multpush(s,x) for(auto &c:x)s.push_back(c);
  14. #define vc vector<char>
  15. #define y second
  16. #define x first
  17. #define int ll
  18. using namespace std;
  19.  
  20. void fastio() {
  21. #ifdef LOCAL
  22.     freopen("input.txt", "r",stdin);
  23. #else
  24.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  25. #endif
  26. }
  27.  
  28. const ll MOD = 1e9 + 7;
  29. const ll INF = 1e9 + 50;
  30. const int MXS = 1e5 + 5;
  31. const int NLOGN = 4e6 + 5;
  32.  
  33. struct SQRT
  34. {
  35.     int SQ;
  36.     vector<map<int,int>> blockAns;
  37.     vector<vector<int>> blocks;
  38.     vector<map<int,int>> lazy;
  39.  
  40.     SQRT(vector<int> &vec)
  41.     {
  42.         int n = vec.size();
  43.         SQ = sqrt(n) + 1;
  44.  
  45.         blockAns = vector<map<int,int>> (SQ);
  46.         blocks = vector<vector<int>>(SQ, vector<int>(SQ));
  47.         lazy = vector<map<int,int>>(SQ);
  48.         for(int i = 0; i < n; i++)
  49.         {
  50.             blocks[i/SQ][i - i/SQ * SQ] = vec[i];
  51.             blockAns[i/SQ][vec[i]]++;
  52.         }
  53.     }
  54.  
  55.  
  56.     void querySet(int l, int r, int x)
  57.     {
  58.         int i = l;
  59.         blockAns[i/SQ][blocks[i/SQ][i - i/SQ * SQ]]--;
  60.         blocks[i/SQ][i - i/SQ * SQ] = x;
  61.         blockAns[i/SQ][x]++;
  62.  
  63.     }
  64.  
  65.     int getsum(int l, int r,int x)
  66.     {
  67.         int ans = 0;
  68.  
  69.         // hna mashy inside block
  70.         for(int i = l; i < min(r+1, (l/SQ + 1) * SQ); i++)
  71.             ans += blocks[i/SQ][i - i/SQ * SQ] == x;
  72.  
  73.         if(l/SQ == r/SQ)
  74.             return ans;
  75.  
  76.         // ana hna mashy blocks
  77.         for(int i = l/SQ + 1; i < r/SQ; i++)
  78.             ans += blockAns[i][x];
  79.  
  80.         // hna mashy inside block
  81.         for(int i = r/SQ * SQ; i <= r; i++)
  82.             ans += blocks[i/SQ][i - i/SQ * SQ] == x;
  83.  
  84.         return ans;
  85.     }
  86. };
  87.  
  88. void solve() {
  89.     int n,q;cin>>n>>q;
  90.     vector<int> v(n);
  91.     input(v);
  92.     SQRT sq(v);
  93.     while (q--) {
  94.         int op;cin>>op;
  95.         if (op == 0) {
  96.             int l,x;cin>>l>>x;
  97.             sq.querySet(l,l,x);
  98.         }else {
  99.             int l,r,x;cin>>l>>r>>x;
  100.             if (r==l) {
  101.                 cout<<0<<endl;
  102.             }else cout<<sq.getsum(l,r-1,x)<<endl;
  103.         }
  104.     }
  105. }
  106.  
  107. signed main() {
  108.     fastio();
  109.     int i = 1;
  110.     // cin>>i;
  111.     while (i--)
  112.         solve();
  113. }
  114.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dQfw8u
language:
C++14 (gcc 8.3)
created:
1 hour 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!