【CF160E】Buses and People

题目大意：给定 N 个三元组 (a,b,c)，现有 M 个询问，每个询问给定一个三元组 (a',b',c')，求满足 a<a', b'<b, c'<c 的最小 c 对应的元组编号。

题解：这可以算是一道经典的三维偏序问题。

首先，离线处理所有询问，将这 N+M 个元组按照 a 从小到达进行排序，若有相同的 a，则给定元组应该排在询问元组之前。排序后即可保证对于任意一个询问元组，答案一定出现在该元组以前的给定元组中。因为要求的是最小的满足条件的 C，应该在 C 上建立线段树。对 C 进行离散化操作，在 (b,c) 上建立线段树，以 C 为下标，B 为权值。线段树中维护 B 的最大值，询问时在线段树上二分即可。时间复杂度为 \(O(nlogn)\)。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=2e5+10;

int n,m,ans[maxn>>1];

int d[maxn],tot;

struct rec{

	int st,ed,t,id;

	bool operator<(const rec &rhs)const{

		return st==rhs.st?id<rhs.id:st<rhs.st;

	}

}a[maxn];

int f[maxn<<2],id[maxn<<2];

void insert(int o,int l,int r,int pos,int val,int ID){

	if(l==r){f[o]=val,id[o]=ID;return;}

	int mid=l+r>>1;

	if(pos<=mid)insert(o<<1,l,mid,pos,val,ID);

	else insert(o<<1|1,mid+1,r,pos,val,ID);

	f[o]=max(f[o<<1],f[o<<1|1]);

}

int query(int o,int l,int r,int x,int y,int val){

	if(l==r)return id[o];

	int mid=l+r>>1;

	int ret=-1;

	if(y<=mid){

		if(f[o<<1]>=val)ret=query(o<<1,l,mid,x,y,val);

	}else if(x>mid){

		if(f[o<<1|1]>=val)ret=query(o<<1|1,mid+1,r,x,y,val);

	}else{

		if(f[o<<1]>=val)ret=query(o<<1,l,mid,x,mid,val);

		if(ret==-1&&f[o<<1|1]>=val)ret=query(o<<1|1,mid+1,r,mid+1,y,val);

	}

	return ret;

}

void read_and_parse(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n+m;i++){

		scanf("%d%d%d",&a[i].st,&a[i].ed,&a[i].t);

		a[i].id=i;

		d[++tot]=a[i].t;

	}

	sort(d+1,d+tot+1);

	tot=unique(d+1,d+tot+1)-d-1;

	sort(a+1,a+n+m+1);

	for(int i=1;i<=n+m;i++)a[i].t=lower_bound(d+1,d+tot+1,a[i].t)-d;

}

void solve(){

	for(int i=1;i<=n+m;i++){

		if(a[i].id<=n)insert(1,1,tot,a[i].t,a[i].ed,a[i].id);

		else ans[a[i].id-n]=query(1,1,tot,a[i].t,tot,a[i].ed);

	}

	for(int i=1;i<=m;i++)printf("%d ",ans[i]);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}

巴特西

【CF160E】Buses and People

最新文章

热门文章