正文
【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;
}
