牛客OI周赛4-提高组-C-战争[并查集]

题意

一个长度为 \(n\) 的序列，每个权值互不相同，给出形如 \(l,r,p\) 的信息表示 \([l,r]\) 区间中最小的数是 \(p\) ，问第几个信息开始出现矛盾。

\(n\leq 5 \times 10^5\) .

分析

二分答案再判前 \(mid\) 个信息是否合法。
相同 \(p\) 的区间的 \(p\) 一定出现在这些区间的交中。
分析出现矛盾的两种情况：
- 相同权值的区间没有交集
- 相同权值的区间有交集，但是这些位置一定要填 \(>p\) 的数
考虑将区间按照权值从大到小排序，每次处理一种权值 \(p\) ，计算出交之后观察能不能在交区间中找到一个位置来放置 \(p\) 。
接着再将并区间打上标记表示不能有 \(< p\) 的数出现在这个区间中。
总时间复杂度为 \(O(n log^2n)\)。

代码

#include<bits/stdc++.h>

using namespace std;

#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].last,v=e[i].to)

#define rep(i,a,b) for(int i=a;i<=b;++i)

#define pb push_back

#define Ls o<<1

#define Rs o<<1|1

typedef long long LL;

inline int gi(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch))	{if(ch=='-') f=-1;ch=getchar();}

	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}

	return x*f;

}

template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}

template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;}

const int N=5e5 + 7,inf=0x3f3f3f3f;

int n,q;

int par[N];

int getpar(int a){return par[a]==a?a:par[a]=getpar(par[a]);}

struct data{

	int l,r,v;

	data(){}data(int l,int r,int v):l(l),r(r),v(v){}

	bool operator <(const data &rhs)const{

		return v>rhs.v;

	}

}t[N],d[N];

bool check(int mid){

	rep(i,1,mid) t[i]=d[i];

	sort(t+1,t+1+mid);

	rep(i,1,n) par[i]=i;

	for(int i=1,j=1;i<=mid;i=j+1,j=i){

		int l=t[i].l,r=t[i].r,L=t[i].l,R=t[i].r;

		while(j+1<=mid&&t[j+1].v==t[j].v){

			++j;

			Max(l,t[j].l);Min(r,t[j].r);

			Min(L,t[j].l);Max(R,t[j].r);

		}

		if(l>getpar(r)) return 0;

		while(L<=R){

			if(getpar(R)==R) par[R]=getpar(L-1),--R;

			else R=getpar(R);

		}

	}

	return 1;

}

int main(){

	n=gi(),q=gi();

	rep(i,1,q) d[i].l=gi(),d[i].r=gi(),d[i].v=gi();

	int l=1,r=q;

	while(l<r){

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

		if(check(mid)) l=mid;

		else r=mid-1;

	}

	printf("%d\n",l+1);

	return 0;

}

巴特西

牛客OI周赛4-提高组-C-战争[并查集]

题意

分析

代码

最新文章

热门文章