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 10050
  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. //---------------------------------------------------BIT----------------------------------------------------------------------
  103.  
  104. lli BIT[300][MAX], a[30005], n;
  105. lli blk_sz;
  106.  
  107. // update in BIT
  108. void update(lli blk_num , lli x , lli val)
  109. {
  110.     while(x<MAX)
  111.     {
  112.         BIT[blk_num][x] += val;
  113.         x += (x&-x);
  114.     }
  115. }
  116.  
  117. // find how many elements less than equal to X
  118. lli query(lli blk_num , lli x)
  119. {
  120.      lli sum = 0;
  121.      while(x>0)
  122.      {
  123.         sum += BIT[blk_num][x];
  124.         x -= (x&-x);
  125.      }
  126.  
  127.      return sum;
  128. }
  129.  
  130. //--------------------------------------------------BIT------------------------------------------------------------------------
  131.  
  132.  
  133. //--------------------------------------------------------SQRT------------------------------------------------------------
  134.  
  135.  
  136. // preprocess array to sqrt decomposition
  137. void preprocess(lli n)
  138. {
  139.     blk_sz = sqrt(n);
  140.  
  141.     lli blk_ind = -1;
  142.  
  143.     loop(i,n)
  144.     {
  145.         if(i % blk_sz == 0)
  146.             blk_ind++;
  147.  
  148.         update(blk_ind , a[i] , 1); //update in BIT
  149.     }
  150. }
  151.  
  152.  
  153. // query to count total values from l to r which have greater value then   K
  154. lli process_query(lli l , lli r , lli k)
  155. {
  156.     lli left_block = l/blk_sz;
  157.  
  158.     lli right_block = r/blk_sz;
  159.  
  160.     lli cnt=0;
  161.  
  162.     if(left_block == right_block)
  163.     {
  164.         for(lli i=l;i<=r;i++)
  165.             cnt += (a[i]>k);
  166.     }
  167.     else
  168.     {
  169.         for(lli i=l;i<blk_sz*(left_block+1);i++) // traversing first block in range 
  170.             cnt += (a[i]>k);
  171.  
  172.         for(lli i=left_block+1;i<right_block;i++) // traversing completely overlapped blocks in range 
  173.         {
  174.  
  175.             cnt += query(i,MAX)-query(i,k);       //count how many elements in BIT whose block number is i which are greater than K
  176.         }
  177.  
  178.         for(lli i=blk_sz*right_block;i<=r;i++) // traversing last block in range 
  179.             cnt += (a[i]>k);
  180.     }
  181.  
  182.     return cnt;
  183. }
  184.  
  185. //--------------------------------------------------------SQRT------------------------------------------------------------
  186.  
  187.  
  188. int main(){
  189. fastio
  190. lli t=1;
  191. //cin>>t;
  192. chandan2();
  193. while(t--) {
  194.     lli q;
  195.     cin>>n;
  196.     loop(i,n)
  197.         cin>>a[i];
  198.     preprocess(n);
  199.  
  200.     cin>>q;
  201.     while(q--)
  202.     {
  203.         lli type;
  204.         cin>>type;
  205.         if(type == 1)
  206.         {
  207.             lli l,r,k;
  208.             cin>>l>>r>>k;
  209.             l--;
  210.             r--;
  211.             print(process_query(l,r,k));
  212.         }
  213.         else
  214.         {
  215.             lli ind,val;
  216.  
  217.             cin>>ind>>val;
  218.             ind--;
  219.  
  220.             lli blk_num = ind/blk_sz;
  221.  
  222.             update(blk_num , a[ind] , -1);
  223.  
  224.             a[ind]=val;
  225.  
  226.             update(blk_num,a[ind] , 1);
  227.         }
  228.     }
  229.   }
  230. return 0;
  231. }
  232.  
  233. // BIT + SQRT 
  234.  
Success #stdin #stdout 0s 4496KB
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/VzmT50
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!