K-th Number
Time Limit: 20000MS | Memory Limit: 65536K | |
Total Submissions: 76200 | Accepted: 27393 | |
Case Time Limit: 2000MS |
- Description
- You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
- That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i...j] segment, if this segment was sorted?"
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.
- Input
- The first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000).
- The second line contains n different integer numbers not exceeding 109 by their absolute values --- the array for which the answers should be given.
- The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).
- Output
- For each question output the answer to it --- the k-th number in sorted a[i...j] segment.
- Sample Input
- 7 3
- 1 5 2 6 3 7 4
- 2 5 3
- 4 4 1
- 1 7 3
- Sample Output
- 5 6 3
- Hint
- This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.
- Source
- Northeastern Europe 2004, Northern Subregion
题目大意: 给你 n 个数和 m 个询问, 每个询问都是关于区间第 k 小的数是多少.
思路: 这个题目的方法很多.
1. 分块
2. 整体二分
3. 主席数 (可持久化线段树)
4. 区间线段树套平衡树
5. 权值线段树套平衡树
6. 线段树套线段树
7. 替罪羊树套权值线段树.
附整体二分代码:
- #include<iostream>
- #include<cstring>
- #include<cmath>
- #include<vector>
- #include<cstdio>
- #include<algorithm>
- #include<vector>
- #include<map>
- #include<set>
- #include<ctime>
- using namespace std;
- #define re(i,n) for(int i=0;i<n;i++)
- #define RE(i,n) for(int i=n-1;i;i--)
- #define REP(i,n) for(int i=n;i;i--)
- #define rep(i,n) for(int i=1;i<=n;i++)
- #define repx(i,a,b) for(int i=a;i<=b;i++)
- #define repy(i,a,b) for(int i=a;i>=b;i--)
- #define ms(i,a) memset(a,i,sizeof(a))
- #define sz(x) (x.size())
- #define pb push_back
- #define sqr(x) ((x)*(x))
- #define vi vector<int>
- #define LL long long
- #define pi pair<int,int>
- #define mp make_pair
- #define lch (o<<1)
- #define rch (o<<1|1)
- #define mid (l+r)/2
- inline void read(int &x){
- int w=0; char ch=0; x=0;
- while(ch<'0' || ch>'9') {w|=ch=='-';ch=getchar();}
- while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
- if (w) x=-x;
- }
- inline void write(int x){
- if(x<0) putchar('-'),x=-x;
- if(x>9) write(x/10);
- putchar(x%10+'0');
- }
- int const maxn=100003;
- int const inf=1e9;
- struct node{
- int x,num;
- bool operator <( const node &rhs) const{
- return x<rhs.x;
- }
- }a[maxn];
- struct query{
- int x,y,id,cnt,k;
- }q[maxn],tmp[maxn];
- int n,m,ans[maxn],t[maxn];
- void calc(int l,int r,int al,int Mid){
- int L=1, R=n+1;
- while (L<R){
- int M=(L+R)/2;
- if (a[M].x>=al) R=M;
- else L=M+1;
- }
- for(int i=R;i<=n && a[i].x<=Mid;i++)
- for(int j=a[i].num;j<=n; j+= (j&-j) ) t[j]++;
- for(int i=l;i<=r;i++){
- q[i].cnt=0;
- for(int j=q[i].y; j; j-=(j&-j)) q[i].cnt+=t[j];
- for(int j=q[i].x-1;j;j-=(j&-j)) q[i].cnt-=t[j];
- }
- for(int i=R;i<=n && a[i].x<=Mid;i++)
- for(int j=a[i].num;j<=n;j+=(j&-j)) t[j]--;
- }
- void solve(int l,int r,LL al,LL ar){
- if(al==ar){
- repx(i,l,r) ans[q[i].id]=al; return;
- }
- int Mid=al+(ar-al)/2;
- calc(l,r,al,Mid);
- int p1=l,p2=r;
- for(int i=l;i<=r;i++)
- if (q[i].cnt>=q[i].k) tmp[p1++]=q[i];
- else q[i].k-=q[i].cnt,tmp[p2--]=q[i];
- for(int i=l;i<=r;i++) q[i]=tmp[i];
- if(l<=p1-1) solve(l,p1-1,al,Mid);
- if(p2+1<=r) solve(p2+1,r,Mid+1,ar);
- }
- int main(){
- scanf("%d%d",&n,&m);
- rep(i,n){
- scanf("%d",&a[i].x);
- a[i].num=i;
- }
- a[n+1].x=2*inf;
- sort(a+1,a+n+1);
- rep(i,m){
- scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].k);
- q[i].id=i;
- }
- solve(1,m,-inf,inf);
- rep(i,m) printf("%d\n",ans[i]);
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3161293.html