求助CF1080F
  • 板块灌水区
  • 楼主ZHUHK
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/10/9 13:20
  • 上次更新2023/10/27 08:06:35
查看原帖
求助CF1080F
304458
ZHUHK楼主2022/10/9 13:20
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct line
{
	int l,r,p;
	bool operator <(const line &b)const {return l<b.l;}
	bool operator >(const line &b)const {return l>b.l;}
}t[N];

//------------------President Tree
struct Segment
{
	int lc,rc;
	int data;
}tr[N<<8];
int root[N<<2],cnt=0;
void updata(int now){
	tr[now].data=max(tr[tr[now].lc].data,tr[tr[now].rc].data);
}
int build(int l,int r){
	int p=++cnt;
	if(l==r) {tr[p].data=0x3f3f3f3f;return p;}
	int mid=(l+r)>>1;
	tr[p].lc=build(l,mid);
	tr[p].rc=build(mid+1,r);
	updata(p);
	return p;
}
int insert(int now,int l,int r,int x,int val)
{
	int p=++cnt;
	tr[p]=tr[now];
	if(l==r) 
	{
		tr[p].data=min(tr[p].data,val);
		return p;
	}
	int mid=(l+r)>>1;
	if(x<=mid) tr[p].lc=insert(tr[now].lc,l,mid,x,val);
	else tr[p].rc=insert(tr[now].rc,mid+1,r,x,val);
	updata(p);
	return p;
}
int query(int now,int lt,int rt,int l,int r){
	if(l<=lt&&rt<=r) return tr[now].data;
	int mid=(lt+rt)>>1;
	int ans=0;
	if(l<=mid) ans=query(tr[now].lc,lt,mid,l,r);
	if(r>mid) ans=max(ans,query(tr[now].rc,mid+1,rt,l,r));
	return ans;
}
//----------------------

int n,m,k;
int D[N<<1],idx=0;
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=k;i++) 
	{
		scanf("%d%d%d",&t[i].l,&t[i].r,&t[i].p);
		D[++idx]=t[i].l;
	}
	sort(t+1,t+1+k);
	sort(D+1,D+1+idx);
	idx=unique(D+1,D+1+idx)-D-1;
	for(int i=1;i<=k;i++) t[i].l=lower_bound(D+1,D+1+idx,t[i].l)-D;
	
	for(int i=1;i<=k;i++){
		printf("%d %d %d\n",t[i].l,t[i].r,t[i].p);
	}
	int itt=k;
	root[idx+1]=build(1,n);
	
	for(int i=idx;i>=1;i--){
		int flag=false;
		while(t[itt].l==i&&itt>=1) {
			root[i]=insert(root[i+1],1,n,t[itt].p,t[itt].r);
			itt--;flag=true;
		}
		if(t[itt].l<i&&!flag) root[i]=root[i+1];
	}

	for(int i=1;i<=m;i++){
		int a,b,x,y;
		scanf("%d%d%d%d",&a,&b,&x,&y);
		x=lower_bound(D+1,D+1+idx,x)-D;
		int ans=query(root[x],1,n,a,b);
		cout<<ans<<endl;
		if(ans<=y) cout<<"yes"<<endl;
		else cout<<"no"<<endl;
		fflush(stdout);
	}
	return 0;
}
2022/10/9 13:20
加载中...