Description
You are given an array A consisting of N positive integers. You have to answer Q queries on it of following type:
- l r k : Let S denote the sorted (in increasing order) set of elements of array A with its indices between l and r. Note that set Scontains distinct elements (i.e. no duplicates).
You need to find kth number in it. If such a number does not exist, i.e. the S has less than k elements, output -1.
All the indices in the queries are 1-based.
Input
The first line of input contains two space separated integers N and Q denoting the number of elements in A, and the number of queries, respectively.
The second line of input contains N space separated integers denoting the array A.
Each of the next Q lines contains five integers ai, bi, ci, di, ki.
We will generate li, ri indices for this query as follows:
Let answer for i - 1th query equal ansi - 1. For 0th query ans0 = 0. Define li = (ai x max(ansi - 1, 0) + bi) mod N + 1, ri = (ci x max(ansi-1, 0) + di) mod N + 1. If li > ri, then swap li and ri.
Output
For each query, output the answer to the query in a single line. If such a number doesn't exist, output -1.
Constraints
- 1 ≤ N, Q ≤ 105
- 1 ≤ Ai ≤ 109
- 0 ≤ ai, bi, ci, di ≤ N
- 1 ≤ li ≤ ri ≤ N
- 1 ≤ ki ≤ N
Example
Input: 4 4 3 2 1 2 0 1 0 3 2 2 0 0 3 4 1 2 1 3 2 2 0 0 3 3 Output: 2 -1 2 3 Input: 10 10 9 10 6 3 8 4 9 6 4 10 0 2 0 9 3 1 9 1 3 3 1 8 1 0 3 1 2 1 7 2 1 6 1 2 3 1 4 1 3 1 1 6 1 6 1 1 4 1 8 1 1 9 1 3 3 1 9 1 2 1 Output: 6 9 10 4 6 3 10 4 6 4
Subtasks
- Subtask #1 (10 points) : Q x N ≤ 107
- Subtask #2 (20 points) : ki = 1
- Subtask #3 (30 points) : ai = 0, ci = 0
- Subtask #4 (40 points) : Original constraints
Explanation
Example #1:
Query 1. Sorted set of elements : {1, 2}. Second number in this is 2.
Query 2. Sorted set of elements : {1, 2, 3}. Fourth number doesn't exist, hence answer is -1.
Query 3. Sorted set of elements : {1, 2}. Second number in this set is 2.
Query 4. Sorted set of elements : {1, 2, 3}. Third number in this set is 3.
题意：
给定长度为N的序列A，其中每个元素都有正整数。
你需要回答Q个询问：
l,r,k:记s为序列 A下标在l到r之间的元素按照升序排列得到的序列(重复元素只留一个)。
你需要求出其第k个元素的值，如果包含小于k个元素，则输出-1.
下标从1开始编号
题解：
线段树，每个节点保存不含重复元素的动态数组
查询的时候二分就OK 复杂度O( q*logn*logn)
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<vector> using namespace std; const int N = 1e5+10, M = 2e2+11, inf = 2e9, mod = 1e9+7; typedef long long ll; int n, q; ll ar[N],num[N]; vector< ll > da[4 * N]; void merges(vector<ll> &a, vector<ll> &b, vector<ll> &c) { int lenb = 0 , lenc = 0; while(lenb < b.size() && lenc < c.size()) { if(b[lenb] == c[lenc]) { a.push_back(b[lenb]); lenb++, lenc++; }else { if(b[lenb] < c[lenc]) { a.push_back(b[lenb++]); } else a.push_back(c[lenc++]); } } while(lenb < b.size()) { a.push_back(b[lenb++]); } while(lenc < c.size()) { a.push_back(c[lenc++]); } } void build(int k,int l,int r) { if(r == l) { da[k].push_back(ar[l]); return ; } build(k<<1,l,(l+r)/2);build(k<<1|1,(r+l)/2+1,r); merges(da[k],da[k<<1],da[k<<1|1]); } ll query(int i,int j,ll x,int k,int l,int r) { if(i==l&&j==r) return upper_bound(da[k].begin(),da[k].end(),x) - da[k].begin(); else { int mid = (l+r)>>1; if(j<=mid) return query(i,j,x,k<<1,l,mid); else if(i>mid) return query(i,j,x,k<<1|1,mid+1,r); else return query(i,mid,x,k<<1,l,mid)+query(mid+1,j,x,k<<1|1,mid+1,r); } } ll solve(int l,int r,int k) { int lb = 1, rb = n, ans = 1; while(lb<=rb) { int mid = (lb+rb)>>1; if(query(l,r,num[mid],1,1,n)>=k) rb = mid-1, ans = mid; else lb = mid + 1; // cout<<1<<endl; } if(query(l,r,num[ans],1,1,n)<k) { return -1; } else return num[ans]; } int main() { scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%lld",&ar[i]), num[i] = ar[i]; sort(num+1,num+n+1); build(1,1,n); ll pre = 0; for(int i=1;i<=q;i++) { ll a,b,c,d,k; scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k); int l = (a*max(pre,0ll)+b) % n + 1; int r = (c*max(pre,0ll)+d) % n + 1; printf("%d ",pre = solve(l,r,k)); } }