KQUERYO - K-Query Online
no tags
Given a sequence of n numbers a1, a2, ..., an and a number of k- queries. A k-query is a triple (i, j, k) (1 ≤ i ≤ j ≤ n). For each k-query (i, j, k), you have to return the number of elements greater than k in the subsequence ai, ai+1, ..., aj.
Input
- Line 1: n (1 ≤ n ≤ 30000).
- Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 109).
- Line 3: q (1 ≤ q ≤ 200000), the number of k- queries.
- In the next q lines, each line contains 3 numbers a, b, c representing a k-query. You should do the following:
- i = a xor last_ans
- j = b xor last_ans
- k = c xor last_ans
- After that 1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 109 holds.
Where last_ans = the answer to the last query (for the first query it's 0).
Output
- For each k-query (i, j, k), print the number of elements greater than k in the subsequence ai, ai+1, ..., aj in a single line.
Example
Input:
66 8 9 3 5 1 9 5 2 3 5 3 3 7 0 0 11 0 0 2 3 7 4
3 3 26 8 9 3 5 1 9 5 2 3 5 3 3 7 0 0 11 0 0 2 3 7 40 5Output:1 1 0 0 2--------------------------------------editorial---------------------------------------------------void build(int id = 1,int l = 0,int r = n){ if(r - l < 2){ v[id].push_back(a[l]); return ; } int mid = (l+r)/2; build(2 * id, l, mid); build(2*id+1, mid, r); merge(v[2 * id].begin(), v[2 * id].end(), v[2 * id + 1].begin(), v[2 * id + 1].end(), back_inserter(v[id])); // read more about back_inserter in http://www.cplusplus.com/reference/iterator/back_inserter/ }And function for solving queries :int cnt(int x,int y,int k,int id = 1,int l = 0,int r = n){// solve the query (x,y-1,k) if(x >= r or l >= y) return 0; if(x <= l && r <= n) return v[id].size() - (upper_bound(v[id].begin(), v[id].end(), k) - v[id].begin()); int mid = (l+r)/2; return cnt(x, y, k, 2 * id, l, mid) + cnt(x, y, k, 2*id+1, mid, r) ; }--------------------------------code----------------------------------------------#include<iostream> using namespace std; #include<bits/stdc++.h> struct node { vector<int> v; } seg[300000]; int arr[300000]; int val,qs,qe; void build(int index,int start,int end) { //cout<<start<<" "<<end<<endl; if(start==end) { seg[index].v.push_back(arr[start]); return ; } else if(start>end) return; int mid=(start+end)/2; build(2*index,start,mid); build(2*index+1,mid+1,end); int len1=seg[2*index].v.size(); int len2=seg[2*index+1].v.size(); int p=0,q=0; while(p!=len1 && q!=len2) { if(seg[2*index].v[p]<=seg[2*index+1].v[q]) { seg[index].v.push_back(seg[2*index].v[p]); p++; } else { seg[index].v.push_back(seg[2*index+1].v[q]); q++; } } while(p<len1) { seg[index].v.push_back(seg[2*index].v[p]); p++; } while(q<len2) { seg[index].v.push_back(seg[2*index+1].v[q]); q++; } // cout<<"vector of index "<<index<<endl; // for(int i=0;i<seg[index].v.size();i++) { // cout<<seg[index].v[i]<<" ";; } // cout<<endl; } int query(int index,int start,int end) { if(start>end || start>qe || end<qs) return 0; if(qs<=start && qe>=end) { int re=0; if(lower_bound(seg[index].v.begin(),seg[index].v.end(),val+1)!=seg[index].v.end()) { if(*lower_bound(seg[index].v.begin(),seg[index].v.end(),val+1)>val) re=lower_bound(seg[index].v.begin(),seg[index].v.end(),val+1)-seg[index].v.end(); } // cout<<" from index "<<index<<" return "<<-re<<" se "<<start<<" "<<end<<endl; return -re; } int mid=(start+end)/2; int p1=query(2*index,start,mid); int p2=query(2*index+1,mid+1,end); return p1+p2; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++) { cin>>arr[i]; } build(1,1,n); int q; int ans=0; cin>>q; while(q--) { cin>>qs>>qe>>val; //qs-=1; //qe-=1; qs ^=ans; qe ^= ans; val ^= ans; // cout<<qs<<" "<<qe<<" desdf "<<val<<endl; ans=query(1,1,n); cout<<ans<<endl; } }
and