链接:poj2104
题解
- emmmm 裸的主席树可A,新学了整体二分,想看主席树的可以在我博客搜一下这个题号,有写主席树做法
- 每次二分一个mid，如果当前区间内大于mid的数x小于k，那么显然答案应该比mid大，k-=x后放到右区间，否则放到左区间。我们可以发现二分mid是logS的，求当前区间内大于mid个数可以用树状数组简单维护,，注意树状数组清空的时候不能直接清零，要原样减回去，不然会T QAQ，Q次询问，所以是。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using namespace std;
const int N=1e5+7;
const int inf=0x3f3f3f3f;
int n,m,ans[N],tr[N];
struct node{
int x,num;
}a[N];
struct node2{
int l,r,k,cnt,num;
}q[N],b[N];
inline int cmp(const node &x,const node &y){return x.x<y.x;}
void init(){
scanf("%d%d",&n,&m);
rep(i,1,n){scanf("%d",&a[i].x);a[i].num=i;}
rep(i,1,m){scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);q[i].num=i;}
sort(a+1,a+n+1,cmp);
}
inline void add(int x,int y){for(int i=x;i<=n;i+=lowbit(i))tr[i]+=y;}
inline int query(int x){ll res=0;for(int i=x;i;i-=lowbit(i))res+=tr[i];return res;}
void cal(int L,int R,int LL,int mid){
int l=1,r=n;
while(l<r){
int mid=l+r>>1;
if(a[mid].x>=LL)r=mid;
else l=mid+1;
}
for(int i=l;i<=n&&a[i].x<=mid;++i)add(a[i].num,1);
rep(i,L,R)q[i].cnt=query(q[i].r)-query(q[i].l-1);
for(int i=l;i<=n&&a[i].x<=mid;++i)add(a[i].num,-1);
}
void solve(int l,int r,int L,int R){
if(L==R){rep(i,l,r)ans[q[i].num]=L;return ;}
int mid=L+R>>1,now1=l,now2=r;
cal(l,r,L,mid);
rep(i,l,r)if(q[i].cnt>=q[i].k)b[now1++]=q[i];else q[i].k-=q[i].cnt,b[now2--]=q[i];
rep(i,l,r)q[i]=b[i];
if(now1!=l)solve(l,now1-1,L,mid);
if(now2!=r)solve(now2+1,r,mid+1,R);
}
int main(){
init();
solve(1,m,-inf,inf);
rep(i,1,m)printf("%d\n",ans[i]);
return 0;
}