Problem Description Give you a sequence and ask you the kth big number of a inteval.
【题目分析】 很容易想到建一棵线段树，每一个点都带一个有序的数列，查询的时候，只需要截取那一部分，而且每一层最多访问两个节点，然后就是归并排序，然后用vector写了一个程序，发现有趣的T掉了。然后想到了不用STL，用数组会不会更快，然后改成了数组。发现还是T，两个晚上过去了。数组真**难写。然后不得不看了题解，不难证明，我的复杂度大约是nlogn的，但是题解中全是二分+线段树，是nlognlogn的，看来常数和复杂度是一个玄学的问题。
【代码】
一、vector #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> using namespace std; int data[100001]; struct node{ int l,r; vector <int> v; }t[400001]; inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void build(int k,int l,int r) { t[k].l=l;t[k].r=r;t[k].v.clear(); if (l==r) { t[k].v.push_back(data[l]); return; } build(k*2,l,(l+r)/2); build(k*2+1,(l+r)/2+1,r); vector<int> ::iterator k1=t[k*2].v.begin(); vector<int> ::iterator k2=t[k*2+1].v.begin(); int flag1=0,flag2=0; for (int i=l;i<=r;++i) { flag1=(k1==t[k*2].v.end());flag2=(k2==t[k*2+1].v.end()); if (flag1) t[k].v.push_back(*k2),k2++; else if (flag2) t[k].v.push_back(*k1),k1++; else if (*k2<*k1) t[k].v.push_back(*k2),k2++; else t[k].v.push_back(*k1),k1++; } } inline node query(int k,int l,int r) { if (t[k].l>=l&&t[k].r<=r) return t[k]; int mid=(t[k].l+t[k].r)/2; if (r<=mid) return query(k*2,l,r); if (l>mid) return query(k*2+1,l,r); node nowl=query(k*2,l,r),nowr=query(k*2+1,l,r); node now; now.l=nowl.l;now.r=nowr.r; vector<int> ::iterator k1=nowl.v.begin(); vector<int> ::iterator k2=nowr.v.begin(); int flag1=0,flag2=0; while (flag1*flag2==0) { flag1=(k1==nowl.v.end());flag2=(k2==nowr.v.end()); if (flag1) now.v.push_back(*k2),k2++; else if (flag2) now.v.push_back(*k1),k1++; else if (*k2<*k1) now.v.push_back(*k2),k2++; else now.v.push_back(*k1),k1++; flag1=(k1==nowl.v.end());flag2=(k2==nowr.v.end()); } return now; } int main() { int tt; scanf("%d",&tt); while (tt--) { int n,m; n=read();m=read(); for (int i=1;i<=n;++i) scanf("%d",&data[i]); build(1,1,n); while (m--) { int a,b,c; a=read(); b=read(); c=read(); node ans=query(1,a,b); vector<int>::iterator iter; for (iter=ans.v.begin();iter!=ans.v.end();iter++) { c--; if (c==0) {printf("%d\n",*iter); break;} } } } } 二、数组 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> using namespace std; int data[100001]; struct node{ int l,r; }t[400001]; int n,m; int v[19][100001]; int ans[100001]; int a[100001]; inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void build(int k,int l,int r,int dep) { t[k].l=l;t[k].r=r; if (l==r) { v[dep][l]=data[l]; return; } build(k*2,l,(l+r)/2,dep+1); build(k*2+1,(l+r)/2+1,r,dep+1); int k1=t[k*2].l,k2=t[k*2+1].l; int flag1=0,flag2=0; for (int i=l;i<=r;++i) { flag1=(k1>t[k*2].r);flag2=(k2>t[k*2+1].r); if (flag1) v[dep][i]=v[dep+1][k2++]; else if (flag2) v[dep][i]=v[dep+1][k1++]; else if (v[dep+1][k2]<v[dep+1][k1]) v[dep][i]=v[dep+1][k2],k2++; else v[dep][i]=v[dep+1][k1],k1++; } } inline node query(int k,int l,int r,int dep) { if (t[k].l>=l&&t[k].r<=r) { for (int i=t[k].l;i<=t[k].r;i++) ans[i]=v[dep][i]; return t[k]; } int mid=(t[k].l+t[k].r)/2; if (r<=mid) return query(k*2,l,r,dep+1); if (l>mid) return query(k*2+1,l,r,dep+1); node nowl=query(k*2,l,r,dep+1),nowr=query(k*2+1,l,r,dep+1); node now; now.l=nowl.l;now.r=nowr.r; for (int i=now.l;i<=now.r;++i) a[i]=ans[i]; int k1=nowl.l,k2=nowr.l; int flag1=0,flag2=0; for (int i=now.l;i<=now.r;++i) { flag1=(k1>nowl.r);flag2=(k2>nowr.r); if (flag1) ans[i]=a[k2++]; else if (flag2) ans[i]=a[k1++]; else if (a[k2]<a[k1]) ans[i]=a[k2],k2++; else ans[i]=a[k1],k1++; } return now; } int main() { int tt; scanf("%d",&tt); while (tt--) { n=read();m=read(); for (int i=1;i<=n;++i) scanf("%d",&data[i]); build(1,1,n,1); while (m--) { int a,b,c; a=read(); b=read(); c=read(); query(1,a,b,1); printf("%d\n",ans[b-c+1]); } } } 三、AC代码 #include <stdio.h> #include <string.h> #include <algorithm> #include <vector> #define maxn 100005 #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 using namespace std; vector<int> T[maxn << 2]; int N, Q; void build(int l, int r, int rt) { if(l == r) { int val; scanf("%d", &val); T[rt].clear(); T[rt].push_back(val); return; } int mid = (l + r) >> 1; build(lson); build(rson); T[rt].resize(r - l + 1); // Attention merge(T[rt<<1].begin(), T[rt<<1].end(), T[rt<<1|1].begin(), T[rt<<1|1].end(), T[rt].begin()); } int query(int L, int R, int val, int l, int r, int rt) { if(L == l && R == r) { return upper_bound(T[rt].begin(), T[rt].end(), val) - T[rt].begin(); } int mid = (l + r) >> 1; if(R <= mid) return query(L, R, val, lson); else if(L > mid) return query(L, R, val, rson); return query(L, mid, val, lson) + query(mid + 1, R, val, rson); } int main() { int a, b, c, k, left, right, mid, t; scanf("%d", &t); while(t--) { scanf("%d%d", &N, &Q); build(1, N, 1); while(Q--) { scanf("%d%d%d", &a, &b, &k); left = -1; right = N - 1; while(right - left > 1) { // binary search mid = (left + right) >> 1; c = query(a, b, T[1][mid], 1, N, 1); if(c >= k) right = mid; else left = mid; } printf("%d\n", T[1][right]); } } return 0; }