【2020五校联考NOIP #7】伟大的卫国战争

题面传送门

题意：

数轴上有 \(n\) 个点，现在要在它们之间连 \(m\) 条边，第 \(i\) 条边连接 \(a_i,b_i\) 两个点。

现在你要钦定每条边连在数轴的上方还是下方，使得任意两条边要么不相交，要么只在线段顶点处相交；或者宣告无解。

注：两条边 \((l_1,r_1),(l_2,r_2)\) 的条件是 \(l_1<l_2<r_1,r_2>r_1\) 或 \(l_1<r_2<r_1,l_2<l_1\)。

\(n,m \in [1,10^5]\)。

话说这题出现了两次呢……

容易想到 \(m^2\) 的做法，你在任意两条相交的区间之间连一条无向边。然后对此图进行二分图染色。

那么，二分图染色是不是就没有前途了呢？

细心观察，我们连边形成的图中，点的个数并不多，总共只有 \(m\) 个点，瓶颈在于边的个数很多。

回忆起之前学习二分图染色时的一个性质：对于一个连通块，如果可以进行二分图染色，那么染色方案也就唯一确定下来了。

根据这个性质，我们可以想到一个做法：每个连通块，给出一个可能的染法，然后回过头来判断这个染法是否可行。

那么具体该怎样进行染色呢？

访问区间 \(i\) 的时候，用线段树求出所有与 \(i\) 相交的区间 \(j\)。将这些区间全部从线段树删除。并对它们进行 dfs。

由于 \(i\) 与 \(j\) 相交，\(j\) 与 \(i\) 一定不能染相同的颜色。

继续这样 dfs 下去就可以染好一整个连通块。

这个做法看似与之前没什么两样，不过注意到每个点最多只会被取出一次，访问一次，所以总复杂度只有 \(m \log m\)。

怎样用线段树维护这些区间呢？我们建两棵线段树，一棵以右端点为下标，另一棵以左端点为下标，分别维护上述两种情况。

这里以右端点为例。叶子节点 \(r\) 为右端点为 \(r\) 的区间。区间按左端点从小到大排序。

查找 \(l_1<r_2<r_1,l_2<l_1\) 的区间的时候，不断取出 \([l_1+1,r_1-1]\) 的最小区间并将其删除，直到最小区间的左端点 \(\geq r_1\)。

#include <bits/stdc++.h>

using namespace std;

#define fi			first

#define se			second

#define pb			push_back

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

#define fd(i,a,b)	for(int i=a;i>=b;i--)

#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)

#define all(a)		a.begin(),a.end()

#define fill0(a)	memset(a,0,sizeof(a))

#define fill1(a)	memset(a,-1,sizeof(a))

#define fillbig(a)	memset(a,0x3f,sizeof(a))

#define y1			y1010101010101

#define y0			y0101010101010

typedef pair<int,int> pii;

typedef long long ll;

const int SEGTREE_MIN=376;

const int SEGTREE_MAX=377;

const pii INF=make_pair(0x3f3f3f3f,0x3f3f3f3f);

const pii ZERO=make_pair(0,0);

int n,m,a[100005],b[100005];

struct segtree_pii{

	int op;

	struct node{

		int l,r;

		pii val;

	} s[100005<<2];

	multiset<pii> st[100005];

	inline void build(int k,int l,int r){

		if(op==SEGTREE_MIN) s[k].val=INF;else s[k].val=ZERO;

		s[k].l=l;s[k].r=r;if(l==r) return;

		int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);

	}

	inline pii query(int k,int l,int r){

		if(l>r){

			if(op==SEGTREE_MIN) return INF;

			else return ZERO;

		}

		if(l<=s[k].l&&s[k].r<=r) return s[k].val;

		int mid=(s[k].l+s[k].r)>>1;

		if(r<=mid) return query(k<<1,l,r);

		else if(l>mid) return query(k<<1|1,l,r);

		else{

			if(op==SEGTREE_MIN) return min(query(k<<1,l,mid),query(k<<1|1,mid+1,r));

			else return max(query(k<<1,l,mid),query(k<<1|1,mid+1,r));

		}

	}

	inline void push(int k,int ind,pii x){

		if(s[k].l==s[k].r){

			st[s[k].l].insert(x);

			if(op==SEGTREE_MIN) s[k].val=*st[s[k].l].begin();

			else s[k].val=*st[s[k].l].rbegin();

			return;

		}

		int mid=(s[k].l+s[k].r)>>1;

		if(ind<=mid) push(k<<1,ind,x);

		else push(k<<1|1,ind,x);

		if(op==SEGTREE_MIN) s[k].val=min(s[k<<1].val,s[k<<1|1].val);

		else s[k].val=max(s[k<<1].val,s[k<<1|1].val);

	}

	inline void pop(int k,int ind,pii v){

		if(s[k].l==s[k].r){

			st[s[k].l].erase(st[s[k].l].find(v));

			if(op==SEGTREE_MIN){

				if(!st[s[k].l].empty()) s[k].val=*st[s[k].l].begin();

				else s[k].val=INF;

			}

			else{

				if(!st[s[k].l].empty()) s[k].val=*st[s[k].l].rbegin();

				else s[k].val=ZERO;

			}

			return;

		}

		int mid=(s[k].l+s[k].r)>>1;

		if(ind<=mid) pop(k<<1,ind,v);

		else pop(k<<1|1,ind,v);

		if(op==SEGTREE_MIN) s[k].val=min(s[k<<1].val,s[k<<1|1].val);

		else s[k].val=max(s[k<<1].val,s[k<<1|1].val);

	}

} l,r;

map<pair<int,int>,int> id;

int col[100005];

inline void dfs(int x){

//	printf("%d\n",x);

	vector<int> todo;

	pii v=l.query(1,a[x]+1,b[x]-1);

	while(v.fi<a[x]){

//		printf("%d %d\n",v.fi,v.se);

		int j=id[make_pair(v.fi,v.se)];todo.pb(j);

		l.pop(1,v.se,make_pair(v.fi,v.se));

		r.pop(1,v.fi,make_pair(v.se,v.fi));

		v=l.query(1,a[x]+1,b[x]-1);

	}

	v=r.query(1,a[x]+1,b[x]-1);

	while(v.fi>b[x]){

//		printf("%d %d\n",v.fi,v.se);

		int j=id[make_pair(v.se,v.fi)];todo.pb(j);

		l.pop(1,v.fi,make_pair(v.se,v.fi));

		r.pop(1,v.se,make_pair(v.fi,v.se));

		v=r.query(1,a[x]+1,b[x]-1);

	}

	foreach(it,todo) col[*it]=col[x]^1;

	foreach(it,todo) dfs(*it);

}

struct segtree_minmax{

	int op;

	struct node{

		int l,r,val;

	} s[100005<<2];

	inline void build(int k,int l,int r){

		if(op==SEGTREE_MIN) s[k].val=0x3f3f3f3f;else s[k].val=0;

		s[k].l=l;s[k].r=r;if(l==r) return;

		int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);

	}

	inline int query(int k,int l,int r){

		if(l>r){

			if(op==SEGTREE_MIN) return 0x3f3f3f3f;

			else return 0;

		}

		if(l<=s[k].l&&s[k].r<=r) return s[k].val;

		int mid=(s[k].l+s[k].r)>>1;

		if(r<=mid) return query(k<<1,l,r);

		else if(l>mid) return query(k<<1|1,l,r);

		else{

			if(op==SEGTREE_MIN) return min(query(k<<1,l,mid),query(k<<1|1,mid+1,r));

			else return max(query(k<<1,l,mid),query(k<<1|1,mid+1,r));

		}

	}

	inline void modify(int k,int ind,int x){

		if(s[k].l==s[k].r){

			if(op==SEGTREE_MIN) s[k].val=min(s[k].val,x);

			else s[k].val=max(s[k].val,x);

			return;

		}

		int mid=(s[k].l+s[k].r)>>1;

		if(ind<=mid) modify(k<<1,ind,x);

		else modify(k<<1|1,ind,x);

		if(op) s[k].val=min(s[k<<1].val,s[k<<1|1].val);

		else s[k].val=max(s[k<<1].val,s[k<<1|1].val);

	}

} L1,R1,L2,R2;

inline bool check(){

	L1.op=SEGTREE_MIN;R1.op=SEGTREE_MAX;

	L2.op=SEGTREE_MIN;R2.op=SEGTREE_MAX;

	L1.build(1,1,n);R1.build(1,1,n);

	L2.build(1,1,n);R2.build(1,1,n);

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

		if(col[i]==1){

			if(L1.query(1,a[i]+1,b[i]-1)<a[i]) return 0;

			if(R1.query(1,a[i]+1,b[i]-1)>b[i]) return 0;

			L1.modify(1,b[i],a[i]);R1.modify(1,a[i],b[i]);

		}

		else{

			if(L2.query(1,a[i]+1,b[i]-1)<a[i]) return 0;

			if(R2.query(1,a[i]+1,b[i]-1)>b[i]) return 0;

			L2.modify(1,b[i],a[i]);R2.modify(1,a[i],b[i]);

		}

	}

	return 1;

}

int main(){

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

	for(int i=1;i<=m;i++) scanf("%d%d",&a[i],&b[i]);

	for(int i=1;i<=m;i++) id[make_pair(a[i],b[i])]=i;

	l.op=SEGTREE_MIN;r.op=SEGTREE_MAX;l.build(1,1,n);r.build(1,1,n);

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

		l.push(1,b[i],make_pair(a[i],b[i]));

		r.push(1,a[i],make_pair(b[i],a[i]));

	}

	fill1(col);

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

		if(!~col[i]){

			col[i]=1;

			l.pop(1,b[i],make_pair(a[i],b[i]));

			r.pop(1,a[i],make_pair(b[i],a[i]));

			dfs(i);

		}

	}

	if(check())

		for(int i=1;i<=m;i++) printf("%c\n",(col[i])?'S':'N');

	else puts("IMPOSSIBLE");

	return 0;

}

巴特西

【2020五校联考NOIP #7】伟大的卫国战争

最新文章

热门文章