离散化,求第$k$小
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
typedef long long ll;
using namespace std;
template <typename T>void in(T &x) {
x = 0; T f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {x = 10*x + ch - '0'; ch = getchar();}
x *= f;
}
template <typename T>void out(T x) {
if(x < 0) putchar('-'),x = -x;
if(x > 9) out(x/10);
putchar(x%10+'0');
}
//---------------------------------------------------------------
const int N = 2e5+7;
int n,m;
int a[N],_a[N],rev[N],Get[N];
struct value_segment_tree {
int sz[N<<2];
void A(int u,int l,int r,int pos) {
if(l == r) {++sz[u]; return;}
int mid = (l+r)>>1;
if(pos <= mid) A(u<<1,l,mid,pos);
else A(u<<1|1,mid+1,r,pos);
sz[u] = sz[u<<1]+sz[u<<1|1];
}
int Q(int u,int l,int r,int k) {
if(l == r) return l;
int mid = (l+r)>>1;
if(sz[u<<1] >= k) return Q(u<<1,l,mid,k);
else return Q(u<<1|1,mid+1,r,k-sz[u<<1]);
}
}seg;
int main() {
in(n); in(m);
for(int i = 1;i <= n; ++i) in(a[i]),_a[i] = a[i];
sort(_a+1,_a+n+1);
int cnt = unique(_a+1,_a+n+1)-_a-1;
for(int i = 1;i <= n; ++i) {
int k = lower_bound(_a+1,_a+cnt+1,a[i])-_a;
rev[k] = a[i]; a[i] = k;
}
for(int i = 1,t;i <= m; ++i) in(t),++Get[t];
for(int i = 1,p = 0;i <= n; ++i) {
seg.A(1,1,n,a[i]);
while(Get[i]--) out(rev[seg.Q(1,1,n,++p)]),putchar('\n');
}
return 0;
}
能树状数组为啥要线段树
这不来个平衡树?
能动态开点为什么要离散化
能跪为什么要站着 Orz