fork download
copy 
  1. /*
  2. ███████  ██████  ███    ██ ██  ██████ ██   ██ ██   ██ ██   ██
  3. ██      ██    ██ ████   ██ ██ ██      ██   ██ ██   ██ ██   ██
  4. ███████ ██    ██ ██ ██  ██ ██ ██      ███████ ███████ ███████
  5.      ██ ██    ██ ██  ██ ██ ██ ██           ██      ██      ██
  6. ███████  ██████  ██   ████ ██  ██████      ██      ██      ██
  7. */
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11. #define sonic ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  12. #define endl  "\n"
  13. #define ll long long
  14. #define gcd  __gcd
  15. #define all(v) v.begin(),v.end()
  16. #define allr(v) v.rbegin(),v.rend()
  17. #define acc(x) accumulate(all(x),0LL)
  18. #define fixed(n) fixed << setprecision(n)
  19. #define all(v) v.begin(),v.end()
  20. #define mod 1000000007
  21. #define mx(v) *max_element(all(v))
  22. #define mn(v) *min_element(all(v))
  23. #define mxi(v) max_element(all(v))-v.begin()
  24. #define mni(v) min_element(all(v))-v.begin()
  25. #define cin(vec) for(auto &i : vec) cin >> i
  26. #define cout(vec) for(auto& i : vec) cout << i << " "; cout << '\n';
  27.  
  28. ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
  29.  
  30. class Sqrtdeco {
  31.  
  32.     ll n, ign = 0, SQ = 450;// 318 for 1e5, 450 for 2e5
  33.     vector<ll> arr, block, sum;
  34.     vector<vector<ll>>blks;
  35. public:
  36.     Sqrtdeco(vector<ll> &v) {
  37.         arr = v;
  38.         sum = vector<ll>(SQ, 0);
  39.         block = vector<ll>(SQ, ign);
  40.         vector<ll> q;
  41.         for (int i = 0; i < v.size(); ++i) {
  42.             if (i != 0 && i % SQ == 0) {
  43.                 blks.emplace_back(q);
  44.                 q.clear();
  45.                 q.emplace_back(arr[i]);
  46.             } else q.emplace_back(arr[i]);
  47.         }
  48.         if (q.size())blks.emplace_back(q);
  49.     }
  50.  
  51.  
  52.     void set(ll i, ll v) {
  53.         ll l = i - i % SQ, r = l + SQ - 1;
  54.         arr[i] = v;
  55.         vector<ll> w;
  56.         for (int j = l; j < min<ll>(r,arr.size()); ++j) {
  57.             w.emplace_back(arr[j]);
  58.         }
  59.         sort(all(w));
  60.         blks[i / SQ] = w;
  61.  
  62.  
  63.     }
  64.  
  65.     ll qry(ll le, ll rr, ll v) {
  66.         //   ll l = i - i % SQ, r = l + SQ - 1;
  67.          ll res=0;
  68.         while (le <= rr) {
  69.             if (le % SQ == 0 && le + SQ - 1 <= rr) {
  70.                 vector<ll> vv = blks[le / SQ];
  71.                 res += vv.size() - (lower_bound(all(vv), v) - vv.begin());
  72.                 le += SQ;
  73.             } else {
  74.                 if (arr[le] >= v)res++;
  75.                 le++;
  76.             }
  77.         }
  78.         return res;
  79.     }
  80.  
  81.  
  82. };
  83.  
  84.  
  85. void sonic444() {
  86.  
  87.   ll n;cin>>n;
  88.   vector<ll>v(n);
  89.     cin(v);
  90.     ll q; cin>>q;
  91.     Sqrtdeco sq(v);
  92.     for (int i = 0; i < q; ++i) {
  93.         ll a;cin>>a;
  94.         if(a==0){
  95.             ll l,r,c;cin>>l>>r>>c;
  96.             l--,r--;
  97.             cout<<sq.qry(l,r,c)<<endl;
  98.         }
  99.         else{
  100.            ll i,c;cin>>i>>c;
  101.            i--;
  102.           sq.set(i,c);
  103.         }
  104.     }
  105.  
  106.  
  107.  
  108. }
  109.  
  110. int main() {
  111.     //    freopen("input.txt", "r", stdin);
  112.     //    freopen("output.txt", "w", stdout);
  113.     sonic
  114.     //////////////////////////////////////////////
  115.     int t = 1;
  116.     // cin>>t;
  117.  
  118.     while (t--) {
  119.  
  120.         sonic444();
  121.  
  122.     }
  123.     return 0;
  124. }
  125.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TsB1OC
language:
C++ (gcc 8.3)
created:
4 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!