Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cassert>
- #include <cctype>
- #include <climits>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <iostream>
- #include <sstream>
- #include <iomanip>
- #include <string>
- #include <vector>
- #include <list>
- #include <set>
- #include <map>
- #include <stack>
- #include <queue>
- #include <algorithm>
- #include <iterator>
- #include <utility>
- using namespace std;
- #define pb push_back
- #define maxSize 30010
- typedef long long ll;
- typedef vector<ll> vi;
- int arr[maxSize];
- vector< int > tree[maxSize * 4];
- vi::iterator it;
- int bst(int i, int l, int r, int v){
- int m = (l + r) / 2;
- if(l==r){
- if( tree[i][l] > v)
- return 1;
- else
- return 0;
- }
- if( tree[i][m+1] > v){
- return r - m + bst(i, l, m, v);
- }
- else
- return bst(i, m+1, r, v);
- }
- void init(int node, int b, int e){
- if(b==e){
- // tree[node] =arr[b];
- tree[node].pb(arr[b]);
- return;
- }
- init(node*2, b, (b+e)/2);
- init(node*2+1,(b+e)/2+1, e);
- for (int i = b; i <=e; ++i) {
- tree[node].push_back(arr[i]);
- }
- sort(tree[node].begin(), tree[node].end());
- }
- int query(int node, int b, int e, int i, int j, int v) {
- if (j < b || e < i)
- return 0;
- if (b >= i && e <= j) {
- return bst(node, 0, tree[node].size()-1, v);
- }
- return query(node*2, b, (b+e)/2, i, j, v ) + query(node*2+1, (b+e)/2+1, e, i, j, v );
- }
- int main()
- {
- int n,q;
- scanf("%d",&n);
- for (int i = 1; i <=n ; ++i) {
- scanf("%d",&arr[i]);
- }
- init(1, 1, n);
- cin>>q;
- for (int j = 0; j <q ; ++j) {
- int a,b,c;
- scanf("%d%d%d",&a,&b,&c);
- printf("%d\n",query(1, 1, n, a, b, c));
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement