萌新求助 线段树一直RE不知道哪错了
查看原帖
萌新求助 线段树一直RE不知道哪错了
127299
Young_Zn_Cu楼主2020/11/6 17:17
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9+7;
const int N=500005;
int y[N],b[N],rr[N];
int n,m;
inline int read(){
	int cnt=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
	while(isdigit(c)){cnt=(cnt<<1)+(cnt<<3)+(c^48);c=getchar();}
	return cnt*f;
}
struct SET{int l,r,num,maxn;}tr[N<<2];
inline void pushup(int p){
	tr[p].num=tr[p<<1].num+tr[p<<1|1].num;
	tr[p].maxn=max(tr[p<<1].maxn,tr[p<<1|1].maxn);
}
///*
void build(int p,int l,int r){
	tr[p].l=l;tr[p].r=r;
	if(l==r){tr[p].num=1,tr[p].maxn=rr[l];return;}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);build(p<<1|1,mid+1,r);
	pushup(p);
}
//*/
/*
void build(int p,int l,int r){
	tr[p].l=l;tr[p].r=r;
	if(l==r){tr[p].num=0,tr[p].maxn=0;return;}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);build(p<<1|1,mid+1,r);
	pushup(p);
}
*/
/*
void modify(int p,int x,int v){
	if(tr[p].l==tr[p].r) {tr[p].num=1,tr[p].maxn=v;}
	int mid=(tr[p].l+tr[p].r)>>1;
	if(x<=mid) modify(p<<1,x,v);
	else modify(p<<1|1,x,v);
	pushup(p);
}
*/
int querymaxx(int p,int l,int r){
	int maxxx=-INF;
	if(l<=tr[p].l&&r>=tr[p].r) return tr[p].maxn;
	int mid=(tr[p].l+tr[p].r)>>1;
	if(l<=mid) maxxx=max(maxxx,querymaxx(p<<1,l,r));
	if(r>mid) maxxx=max(maxxx,querymaxx(p<<1|1,l,r));
	return maxxx;
}
int querynum(int p,int l,int r){
	int res=0;
	if(l<=tr[p].l&&r>=tr[p].r) return tr[p].num;
	int mid=(l+r)>>1;
	if(tr[p].l<=mid) res+=querynum(p<<1,l,r);
	if(tr[p].r>mid) res+=querynum(p<<1|1,l,r);
	return res;
}
signed main(){
	freopen("1.in","r",stdin);
	n=read();
	for(int i=1;i<=n;++i) b[i]=y[i]=read(),rr[i]=read();
	int q=unique(y+1,y+1+n)-(y+1);
	for(int i=1;i<=n;++i) y[i]=lower_bound(y+1,y+q+1,y[i])-y;
	build(1,1,q);
	m=read();int yy,xx,num,maxx;
	for(int i=1;i<=m;++i){
		yy=read(),xx=read();
		yy=lower_bound(b+1,b+q+1,yy)-b;
		xx=lower_bound(b+1,b+q+1,xx)-b;
//		cerr<<i<<":"<<" "<<xx<<' '<<yy<<endl;
		if(rr[xx]>rr[yy]) {printf("false\n");continue;}
		++yy,--xx;
		maxx=querymaxx(1,yy,xx);
		cerr<<i<<":"<<" "<<xx<<' '<<yy<<' '<<maxx<<endl;
		if(maxx>rr[xx]) {printf("false\n");continue;}
		num=querynum(1,yy-1,xx+1);
		cerr<<i<<":"<<num<<endl;
		if(num==xx-yy+1) {printf("true\n");continue;}
		else {printf("maybe\n");continue;}
	}
	return 0;
}
2020/11/6 17:17
加载中...