本机和已经A了的主席树对拍。
跑极限数据，跑值很接近的数据都能过，但是一交就WA...
好不开心...蒟蒻求解。
不知道哪里出现了问题...

整体二分是从这题升级版那儿想到的，所以楼下神犇说不定可以用第6种方法AC了...求帮助...虽然我知道我的代码不好看= =

【附代码】
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn=100010;
const int INF=2*1e9;

struct Query{
	int x,y,k,id,cur;
	bool tp;
}q[maxn<<1],q1[maxn<<1],q2[maxn<<1];

int n,m,tot;
int ans[maxn],a[maxn],b[maxn],tmp[maxn<<1];

void add(int x,int d){
	for(;x<=n;x+=x&-x) b[x]+=d;
}

int ask(int x){
	int sum=0;
	for(int i=x;i;i-=i&-i) sum+=b[i];
	return sum;
}

void div(int H,int T,int l,int r){
	if(H>T) return ;
	if(l==r){
		for(int i=H;i<=T;i++)
			if(!q[i].tp) ans[q[i].id]=l;
		return ;
	}
	int mid=(l+r)>>1;
	for(int i=H;i<=T;i++){
		if(q[i].tp && q[i].y<=mid) add(q[i].x,1);
		else if(!q[i].tp) 
			tmp[i]=ask(q[i].y)-ask(q[i].x-1);
	}
	for(int i=H;i<=T;i++)
		if(q[i].tp && q[i].y<=mid) add(q[i].x,-1);
	int l1=0,l2=0;
	for(int i=H;i<=T;i++){
		if(q[i].tp){
			if(q[i].y<=mid) q1[++l1]=q[i];
			else q2[++l2]=q[i];
		}
		else{
			if(q[i].cur+tmp[i]>=q[i].k) q1[++l1]=q[i];
			else
				q[i].cur+=tmp[i],q2[++l2]=q[i];
		}
	}
	for(int i=1;i<=l1;i++) q[H+i-1]=q1[i];
	for(int i=1;i<=l2;i++) q[H+l1+i-1]=q2[i];
	div(H,H+l1-1,l,mid);
	div(H+l1,T,mid+1,r);
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("2104.in","r",stdin);
	freopen("2104.out","w",stdout);
#endif
	
	int l,r,k;

	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		q[++tot].tp=1;q[tot].x=i;q[tot].y=a[i];
	}
	for(int i=1;i<=m;i++){
		tot++;
		scanf("%d%d%d",&q[tot].x,&q[tot].y,&q[tot].k);
		q[tot].id=i;
	}
	div(1,tot,0,INF);
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);

	return 0;
}

• Re:整体二分真的不知道怎么WA了 (75) Robert_Yuan 2016-03-30 19:14:44
  • Re:整体二分真的不知道怎么WA了 (24) GlassesQ 2016-06-21 09:53:22
    • Re:整体二分真的不知道怎么WA了 (40) C20180101 2019-03-08 09:48:39