fork download
copy 
  1. ///Finding number of element s in a range which is greater than k
  2. #include<bits/stdc++.h>
  3. #define ll int
  4. #define ff first
  5. #define ss second
  6. #define inf 1000000000
  7. #include<ext/pb_ds/assoc_container.hpp>
  8. #include<ext/pb_ds/tree_policy.hpp>
  9. using namespace std;
  10. using namespace __gnu_pbds;
  11. typedef tree<pair<ll,ll>,null_type,less<pair<ll,ll>>,rb_tree_tag,tree_order_statistics_node_update> indexed_pairset;
  12. indexed_pairset vec[900000];
  13. ll arr[90000];
  14. ll k;
  15. ///log2(n)
  16. void build(ll ind,ll left,ll right)
  17. {
  18.     if(left==right)
  19.     {
  20.         ll c=0;
  21.         vec[ind].insert({arr[left],c});
  22.         return ;
  23.     }
  24.     ll mid=(left+right)/2;
  25.     build(2*ind,left,mid);
  26.     build(2*ind+1,mid+1,right);
  27.     ll c=0;
  28.     auto it1=vec[2*ind].begin();
  29.     auto it2=vec[2*ind+1].begin();
  30.     while(it1!=vec[2*ind].end()&&it2!=vec[2*ind+1].end())
  31.     {
  32.         if(it1->ff<=it2->ff)
  33.         {
  34.         vec[ind].insert({it1->ff,c});
  35.         c++;
  36.         it1++;
  37.        }
  38.        else
  39.        {
  40.            vec[ind].insert({it2->ff,c});
  41.            c++;
  42.            it2++;
  43.        }
  44.     }
  45.     while(it1!=vec[2*ind].end())
  46.     {
  47.         vec[ind].insert({it1->ff,c});
  48.         c++;
  49.         it1++;
  50.     }
  51.      while(it2!=vec[2*ind+1].end())
  52.     {
  53.         vec[ind].insert({it2->ff,c});
  54.         it2++;
  55.         c++;
  56.     }
  57. }
  58. ///log2(n)
  59. void update(ll ind,ll left,ll right,ll pos,ll val,ll old_val)
  60. {
  61.       auto it=vec[ind].lower_bound({arr[pos],-inf});
  62.       ll l1=it->ss;
  63.       vec[ind].erase(it);
  64.       vec[ind].insert({val,l1});
  65.       if(left!=right)
  66.     {
  67.       ll mid=(left+right)/2;
  68.       if(pos<=mid)
  69.       update(2*ind,left,mid,pos,val,old_val);
  70.       else
  71.       update(2*ind+1,mid+1,right,pos,val,old_val);
  72.     }
  73.       else
  74.       {
  75.         arr[pos]=val;
  76.       }
  77. }
  78. ///log2(n)
  79. ll query(ll ind,ll left,ll right,ll i,ll j)
  80. {
  81.     if(j<left||i>right)
  82.         return 0;
  83.     if(i<=left&&j>=right)
  84.     {
  85.         ll l1= vec[ind].size()-vec[ind].order_of_key({k+1,-inf});
  86.         return l1;
  87.     }
  88.     ll mid=(left+right)/2;
  89.     ll x=query(2*ind,left,mid,i,j);
  90.     ll y=query(2*ind+1,mid+1,right,i,j);
  91.     return x+y;
  92. }
  93. int main()
  94. {
  95.     ll i,j,n,q,l,r,type;
  96.     scanf("%d",&n);
  97.     for(i=0; i<n; i++)
  98.         scanf("%d",&arr[i]);
  99.     build(1,0,n-1);
  100.      scanf("%d",&q);
  101.     for(i=0; i<q; i++)
  102.     {
  103.        scanf("%d",&type);
  104.         if(type==0)
  105.         {
  106.             scanf("%d%d",&l,&r);
  107.             l--;
  108.             update(1,0,n-1,l,r,arr[l]);
  109.         }
  110.         else
  111.         {
  112.             scanf("%d%d%d",&l,&r,&k);
  113.             l--;
  114.             r--;
  115.             printf("%d\n",query(1,0,n-1,l,r));
  116.         }
  117.     }
  118.     return 0;
  119. }
  120.  
  121.  
  122.  
Success #stdin #stdout 0.05s 88040KB
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/T6hU4Q
language:
C++ (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!