fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define maxn 200010
  6. #define gc getchar_unlocked
  7. #define ll long long
  8. //fast I/O
  9. void scanint(int &x)
  10. {
  11.     register int c = gc();
  12.     x = 0;
  13.     bool neg=false;
  14.     if(c=='-')
  15.         neg=true;
  16.     for(;(c<48 || c>57);c = gc());
  17.     for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
  18.     if(neg)
  19.         x=-x;
  20. }
  21.  
  22. struct node{
  23.     int cnt;
  24.     node *left;
  25.     node *right;
  26.     node(){
  27.         this->cnt=0;
  28.         this->left=this;
  29.         this->right=this;
  30.     }
  31.     node(int cnt, node *left, node *right):cnt(cnt), left(left), right(right){}
  32.     node *insert(int L, int R, int val);
  33.     //cnt stores no. of elements, left points to left child and right points to right child
  34. };
  35.  
  36. node *null; //Base node
  37. node *tree[maxn]; //persistent segment tree
  38.  
  39. node *node::insert(int L, int R, int val)
  40. {
  41.     if(L==R)
  42.         return new node(this->cnt+1, null, null); //insert no. in node
  43.     else{
  44.         int mid = (L+R)>>1;
  45.         if(val<=mid) //val lies in left child, update left
  46.             return new node(this->cnt+1, this->left->insert(L, mid, val), this->right);
  47.         else // val lies in right child, update right
  48.             return new node(this->cnt+1, this->left, this->right->insert(mid+1, R, val));
  49.     }
  50. }
  51.  
  52. int query(node *low, node *high, int L, int R, int val) // returns all numbers in given segment that are less than or equal to val
  53. {
  54.     if(L==R)
  55.         return (high->cnt - low->cnt); //can't divide further, return all elements in segment
  56.     int mid = (L+R)>>1;
  57.     int lsum = high->left->cnt - low->left->cnt; // total elements in the left child of segment
  58.     if(val<=mid)
  59.         return query(low->left, high->left, L, mid, val); //val lies in left half, call query on left
  60.     else
  61.         return lsum+query(low->right, high->right, mid+1, R, val); //val lies in right half, add all elements in left half and call query on right half
  62. }
  63.  
  64. int main()
  65. {
  66.     int n, m, i, j, l, r, k;
  67.     ll curinv, ans, w, x, y, z, q1, q2;
  68.     scanint(n);//no. of elements
  69.     map<int, int> m1;//for coordinate compression
  70.     int arr[n+10], sor[n+10];//arr[] stores values, sor[] stores sorted order of values
  71.     tree[0] = new node();
  72.     for(i=0; i<n; i++){
  73.         scanint(arr[i]);
  74.         m1[arr[i]];
  75.     }
  76.     map<int, int>::iterator it;
  77.     int ind=1;
  78.     for(it=m1.begin(); it!=m1.end(); ++it){
  79.         m1[it->first] = ind;                // coordinate compression and sorting
  80.         sor[ind] = it->first;
  81.         ind++;
  82.     }
  83.     /*for(i=1; i<=n; i++)
  84.         cout << sor[i] << " ";
  85.     cout << endl;
  86.     for(i=0; i<n; i++)
  87.         cout << m1[arr[i]] << " ";
  88.     cout << endl;*/
  89.     for(i=1; i<=n; i++)
  90.         tree[i] = tree[i-1]->insert(0, ind, m1[arr[i-1]]); // inserting val in tree node
  91.     scanint(m); // no. of queries
  92.     while(m--){
  93.         scanint(l); // left index of query
  94.         scanint(r); // right index
  95.         scanint(k); //
  96.        /* if(l>r){
  97.             int temp = l;
  98.             l = r;
  99.             r = temp;
  100.         }*/
  101.         int pos = upper_bound(sor, sor+n+1, k)-(sor); // deciding rank of k in current arr[], kind of doing coordinate compression on k
  102.         //cout << pos << endl;
  103.         k = m1[sor[pos-1]]; // new k after compression
  104.        // cout << k << endl;
  105.        // cout << query(tree[l-1], tree[r], 0, ind, k) << endl;
  106.         ans=(r-l+1-query(tree[l-1], tree[r], 0, ind, k)); //no. of elements greater = total elemnts-no. of elements less than or equal to k
  107.         printf("%d\n", ans);
  108.     }
  109.     return 0;
  110. }
  111.  
Success #stdin #stdout 0s 4060KB
comments (?)
stdin
copy 
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2
stdout
copy 
2
0
3
https://ideone.com/RblEgl
language:
C++ (gcc 8.3)
created:
9 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!