fork download
copy 
  1. /*
  2. Author : Chandan Agrawal
  3. College : Poornima College of Engg. jaipur, Raj
  4. Mail : chandanagrawal23@gmail.com
  5.  
  6. " when you are not practicing someone else is ,
  7.  and the day u meet them u will lose "
  8.  
  9. */
  10. #include<bits/stdc++.h>
  11. #include<stdio.h>
  12. using namespace std;
  13.  
  14. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  15. #define MAX 500050
  16.  
  17. #define ll long long
  18. #define ld long double
  19. #define lli long long int
  20.  
  21. #define pb push_back
  22. #define INF 1000000000000
  23. #define mod 1000000007
  24.  
  25. // trignometric function always give value in Radians only
  26. #define PI acos(-1) //3.1415926535897932384626433832795028
  27. #define dsin(degree) sin(degree*(PI/180.0))
  28. #define dcos(degree) cos(degree*(PI/180.0))
  29. #define dtan(degree) tan(degree*(PI/180.0))
  30.  
  31. #define rsin(radian) sin(radian)
  32. #define rcos(radian) cos(radian)
  33. #define rtan(radian) tan(radian)
  34.  
  35. #define mem0(a) memset(a,0,sizeof(a))
  36. #define mem1(a) memset(a,-1,sizeof(a))
  37. #define memf(a) memset(a,false,sizeof(a))
  38.  
  39. #define loop(i,n)  for (lli i = 0; i < n; i++)
  40. #define FOR(i,a,b) for (lli i = a; i < b; i++)
  41.  
  42. #define all(v) v.begin(),v.end()
  43. #define rall(v) v.rbegin(),v.rend()
  44. #define makeuniq(v) v.resize(unique(all(v)) - v.begin()); //only uniq element in vector after this
  45. #define sz(x) int(x.size())
  46. #define F first
  47. #define S second
  48.  
  49. #define mii map<lli,lli>
  50.  
  51. #define pii pair<lli,lli>
  52.  
  53. #define vi vector<lli>
  54. #define vvi vector<vi>
  55. #define vpi vector<pii>
  56. #define vbool vector<bool>
  57.  
  58. #define seti set<lli>
  59.  
  60. #define gcd(a,b) __gcd((a),(b))
  61. #define lcm(a,b) (a/gcd(a,b))*b
  62. #define abs(x) ((x < 0)?-(x):x)
  63.  
  64. #define endl '\n'
  65.  
  66. template <typename Head>
  67. void print(Head&& head)
  68. {
  69.     cout<<head<<endl;
  70. }
  71. template <typename Head, typename... Tail>
  72. void print(Head&& head, Tail... tail)
  73. {
  74.     cout<<head<<" ";
  75.     print(tail...);
  76. }
  77.  
  78. #define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
  79. #define scanvec(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}
  80.  
  81. #define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
  82. #define printvec(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";
  83.  
  84. #define FD(N) fixed<<setprecision(N)
  85.  
  86. #define deb(x) cout<<#x<<" "<<x<<endl;
  87.  
  88. /*
  89. 1D vector -  vi dp(n,value);
  90. 2D vector -  vvi dp(n,vi(n,value));
  91. */
  92.  
  93. // chandan1,2
  94. void chandan1(){int y=1;return;}
  95. void chandan2(){
  96.         loop(i,10){
  97.         lli x=1;
  98.     }
  99.     return(chandan1());
  100. }
  101.  
  102. //---------------------------------------------------SQRT_DECOMPO-------------------------------------------------------
  103.  
  104. lli n , a[MAX];
  105. vi block[800];
  106. lli blk_sz;
  107.  
  108. // clear all data
  109. void clear()
  110. {
  111.     mem0(a);
  112.     loop(i,800)
  113.         block[i].clear();
  114. }
  115.  
  116. // preprocess array to sqrt decomposition
  117. void preprocess(lli n)
  118. {
  119.     blk_sz = sqrt(n);
  120.  
  121.     lli blk_ind = -1;
  122.  
  123.     loop(i,n)
  124.     {
  125.         if(i % blk_sz == 0)
  126.             blk_ind++;
  127.  
  128.         block[blk_ind].pb(a[i]); //push elements of sqrt size each 
  129.     }
  130.  
  131.     loop(i,blk_sz+1)
  132.     {
  133.         sort(all(block[i]));
  134.     }
  135. }
  136.  
  137.  
  138. lli binsearch(vi &a , lli k)
  139. {
  140.  
  141.  
  142.     lli l = 0;
  143.     lli r = sz(a)-1;
  144.     lli ind = sz(a);
  145.  
  146.     while(l <= r)
  147.     {
  148.         lli mid = (l+r)/2;
  149.         if(a[mid] > k)
  150.         {
  151.             ind = mid;
  152.             r = mid-1;
  153.         }
  154.         else
  155.             l=mid+1;
  156.     }
  157.  
  158.     return (sz(a)-ind);
  159. }
  160.  
  161.  
  162. // query to count total values from l to r which have greater value then or equal to  K
  163. lli query(lli l , lli r , lli k)
  164. {
  165.     lli left_block = l/blk_sz;
  166.  
  167.     lli right_block = r/blk_sz;
  168.  
  169.     lli cnt=0;
  170.  
  171.     if(left_block == right_block)
  172.     {
  173.         for(lli i=l;i<=r;i++)
  174.             cnt +=  (a[i]>k);
  175.     }
  176.     else
  177.     {
  178.         for(lli i=l;i<blk_sz*(left_block+1);i++) // traversing first block in range 
  179.             cnt +=  (a[i]>k);
  180.  
  181.  
  182.         for(lli i=left_block+1;i<right_block;i++) // traversing completely overlapped blocks in range 
  183.         {
  184.             cnt += block[i].end() - upper_bound(all(block[i]) , k); //count how many elements in array which are greter then K
  185.  
  186.         }
  187.  
  188.         for(lli i=blk_sz*right_block;i<=r;i++) // traversing last block in range 
  189.             cnt +=  (a[i]>k);
  190.     }
  191.  
  192.     return cnt;
  193. }
  194.  
  195. void update(lli ind , lli val)
  196. {
  197.     lli block_number = ind / blk_sz; 
  198.  
  199.     block[block_number].clear();
  200.  
  201.     lli start = block_number*blk_sz;
  202.  
  203.     lli endi = (block_number+1)*blk_sz;
  204.  
  205.     a[ind] = val; 
  206.  
  207.     for(lli i=start;i<endi;i++)
  208.         block[block_number].pb(a[i]);
  209.  
  210.     sort(all(block[block_number]));
  211.  
  212. }
  213.  
  214. //---------------------------------------------------SQRT_DECOMPO-------------------------------------------------------
  215.  
  216. // find count how many values greater than k in L to R  :https://w...content-available-to-author-only...j.com/problems/KQUERY2/
  217.  
  218.  
  219. int main(){
  220. fastio
  221. chandan2();
  222. lli t=1;
  223. //cin>>t;
  224. while(t--)
  225. {
  226.     lli q;
  227.     cin>>n;
  228.     loop(i,n)
  229.         cin>>a[i];
  230.  
  231.     preprocess(n);
  232.     cin>>q;
  233.     while(q--)
  234.     {
  235.         lli type;
  236.         cin>>type;
  237.         if(type == 1)
  238.         {
  239.             lli l,r,k;
  240.             cin>>l>>r>>k;
  241.             l--;
  242.             r--;
  243.             print(query(l,r,k));
  244.         }
  245.         else
  246.         {
  247.             lli ind,val;
  248.             cin>>ind>>val;
  249.             ind--;
  250.             update(ind,val);
  251.         }
  252.     }
  253.  
  254.     clear();
  255.  
  256. }
  257.  
  258. return 0;
  259. }
Success #stdin #stdout 0s 7604KB
comments (?)
stdin
copy 
5
5 1 2 3 4
6
1 2 4 1
0 4 10
1 4 4 4
0 3 1
0 1 2
1 1 5 2
stdout
copy 
2
1
2
https://ideone.com/7cPsag
language:
C++14 (gcc 8.3)
created:
3 years 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!