求助只WA*1,第28个点
查看原帖
求助只WA*1,第28个点
252013
newbie666楼主2025/1/21 15:25

写的线段树二分,不知道哪里错了,WA on 28,AT现在下不了数据也,帮我调一下,谢谢

#include<bits/stdc++.h>
#define MAXN 1000005  
int gi(){
	char c;int x=0,f=0;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))x=(x*10)+(c^48),c=getchar();
	return f?-x:x;
}
std::mt19937 rnd(std::random_device{}());
#define pr std::pair<int,int>
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
template<class T>void cxk(T&a,T b){a=a>b?a:b;}
template<class T>void cnk(T&a,T b){a=a<b?a:b;}
int n,l[MAXN],r[MAXN],m,ans[MAXN];
struct Q{int x,id;}q[MAXN]; 
namespace segtree{
#define ls x<<1
#define rs x<<1|1
#define mid ((l+r)>>1) 
	int mx[MAXN<<2],tag[MAXN<<2],mn[MAXN<<2]; 
	void up(int x){mx[x]=std::max(mx[ls],mx[rs]);mn[x]=std::min(mn[ls],mn[rs]);}
	void addtag(int x,int w){mx[x]+=w,mn[x]+=w,tag[x]+=w;}
	void down(int x){
		if(!tag[x])return;
		addtag(ls,tag[x]),addtag(rs,tag[x]); 
		tag[x]=0;
	}
	void build(int x,int l,int r){
		if(l==r)return mx[x]=mn[x]=q[l].x,void(); 
		build(ls,l,mid),build(rs,mid+1,r); 
		up(x); 
	}
	int find(int x,int l,int r,int p){ //找到线段树中第一个大于等于p的
		if(l==r)return l;
		down(x);
		if(mx[ls]>=p)return find(ls,l,mid,p);
		else if(mx[rs]>=p)return find(rs,mid+1,r,p);
		return -1;
	}
	int find2(int x,int l,int r,int p){ //找到线段树中最后一个小于等于p的
		if(l==r)return l;
		down(x);
		if(mn[rs]<=p)return find2(rs,mid+1,r,p);
		else if(mn[ls]<=p)return find2(ls,l,mid,p);
		return -1; 
	}
	void upd(int x,int l,int r,int ql,int qr,int w){
		if(l>qr||r<ql)return;
		if(l>=ql&&r<=qr)return addtag(x,w); 
		down(x);
		if(ql<=mid)upd(ls,l,mid,ql,qr,w);
		if(mid<qr)upd(rs,mid+1,r,ql,qr,w);
		up(x); 
	}
	int query(int x,int l,int r,int p){
		if(l==r)return mx[x]; 
		down(x);
		return p<=mid?query(ls,l,mid,p):query(rs,mid+1,r,p); 
	}
#undef ls 
#undef rs 
#undef mid 
}
using namespace segtree; 
int main(){
	n=gi();
	for(int i=1;i<=n;i++)l[i]=gi(),r[i]=gi();
	m=gi(); 
	for(int i=1,x;i<=m;i++)x=gi(),q[i]=(Q){x,i}; 
	std::sort(q+1,q+m+1,[&](Q i,Q j){return i.x<j.x;});
	build(1,1,m);
	for(int i=1;i<=n;i++){
		int L=find(1,1,m,l[i]),R=find2(1,1,m,r[i]); 
		if(L<=R&&L>=1&&R>=1&&L<=m&&R<=m)upd(1,1,m,L,R,1);
	}
	for(int i=1;i<=m;i++)ans[q[i].id]=query(1,1,m,i);
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]); 
	return 0;
}

2025/1/21 15:25
加载中...