Buses and People CodeForces 160E 三维偏序+线段树

题意

给定 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 的最大值，询问时在线段树上二分即可。

代码实现(看代码很容易)

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

const int maxn=2e5+7;

struct node{

	int st, ed, t, id;

	bool friend operator < (node a, node b)

	{

		return a.st==b.st ? a.id < b.id : a.st < b.st;

	}

}a[maxn];

vector<int> v;

int tot;

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

int ans[maxn>>1];

int n, m;

void update(int rt, int l, int r, int pos, int val, int ID)

{

	if(l==r)

	{

		//if(maxx[rt] < val)

		{

			maxx[rt]=val;

			id[rt]=ID;

		}

		return ;

	}

	int mid=(l+r)>>1;

	if(pos<=mid)

		update(rt<<1, l, mid, pos, val, ID);

	else

		update(rt<<1|1, mid+1, r, pos, val, ID);

	maxx[rt]=max(maxx[rt<<1], maxx[rt<<1|1]);

}

int query(int rt, int l, int r, int x, int y, int val)

{

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

	int mid=(l+r)>>1;

	int ret=-1;

	if(y<=mid)

	{

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

	}

	else if(x > mid)

	{

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

	}

	else

	{

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

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

	}

	return ret;

}

int main()

{

	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;

		v.push_back(a[i].t);

	}

	sort(v.begin() , v.end());

	v.erase( unique(v.begin() , v.end() ), v.end() );

	tot=v.size() ;

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

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

	{

		a[i].t = lower_bound(v.begin() , v.end() , a[i].t) - v.begin() +1;

	}

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

	{

		if(a[i].id<=n)

			update(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]);

	}

	return 0;

}

巴特西

Buses and People CodeForces 160E 三维偏序+线段树

Buses and People CodeForces 160E 三维偏序+线段树

题意

解题思路

代码实现(看代码很容易)

最新文章

热门文章