题意：
给定 $N$ 个人，每个人可以选择加入黑暗 $Dark$ 或者光明 $Light$ 两种阵营，他们加入不同的阵营之后获得的力量值是不同的，即 $D_i$ 和 $L_i$ 。然后有些人之间有矛盾，是不能加入同一阵营的，矛盾的对数共有 $M$ 对，现在给出所有的矛盾和所有的 $L_i D_i$，问在所有可能存在的最终阵营分配情况中，力量值最大的人和力量值最小的人之间的差最小可能是多少？如果说不可能分配的话输出$IMPOSSIBLE$。其中 $1\le N\le 2*10^5$, $0\le M\le 2*10^5$, $1\le L_i D_i \le 10^9$ ,共20组test，时限4S
题解：
一个非常有意思的，看上去像是图论其实是数据结构的题目。。其实以前做过类似的？应该是今年西安邀请赛时候，区别在于那个题目应该是一种背包的性质，一个联通分量要么选，要么不选，而这个题是每个连通分量都得选，但是要从两套孪生方案中选择一种，每一种都会有一个最大值和一个最小值。
把两两不能在一起的人之家连一条无向边，那么一堆互相有关系的人就形成了一个连通分量，不在同一个分量里的人互相是完全没有影响的，无论这个人是选择D还是L都跟我的选择没关系。而在同一个联通分量里的情况的话，可以发现只要有一个人的状态确定了就可以用二分染色的方法确定连通分量里其他所有人的状态。因此我们首先用染色法对每个连通分量判定，如果能染色成功那么就说明有可行解存在，否则输出$IMPOSSIBLE$，另外，在dfs的过程中还要顺便把每个连通分量的两种方案的最大值最小值总共四个数分别求出来（这里我当时就写假了emmm）。之后考虑如何让差值最小化，一般让某个东西最小化很容易想到二分，但是这个题目的条件下，如果要二分就必须再 $O(n)$ 枚举一个下界，乘上 $O(n)$ 的check的话就n方了，显然无法接受。这时候观察这个题目，此时的每个元素(连通分量)正好有两个属性，发现我们可以用一个常用的套路来尝试，那就是按照其中一个属性排序然后对另一个属性套某种log的数据结构。。对这个题来说，回想我们刚才考虑的二分，他必须有一个操作就是枚举出一个下界or上界，那么如果我们就着这个操作进行下去会怎么样？如果我们能一边枚举一边很快的计算出来当当前枚举到的最小值是最小值的时候最大值最小是多少，那么这个问题就可以解决了。
为了简洁，这里只讨论枚举最大值的情况，用最小值做道理是一样的。首先按照最大值从小到大排序，然后按照这个顺寻遍历每个方案，同时记录已经出现过的连通分量个数，注意这里的方案数和联通分量数是不一样的，因为一个连通分量会有两种方案，而且这两种是必须二选一的。考虑没有遇到孪生的方案的时候（孪生指同一个连通分量产生出来的非此即彼的两个方案）的情况，这时候我们根据连通分量计数器判断一下，如果已经大于等于连通分量了，那说明现在的这个最大值是可以作为一个合法的最大值了。换句话说，如果现在遇到的可以比我当前这个最大值小的连通分量数没能包含住我整张图的所有连通分量的话，那么我枚举到的这个最大值根本就不可能成为真正的最大值，所以在这里做计算根本没有意义。如果已经遇到的数量足够了，这时候就可以用来计算更新答案了。假设我们有一种数据结构，每次可以查询出来我之前的所有元素的最小值最小的那一个是多少，那么我就可以在当前直接计算出来当前这个枚举到的最大值对答案的影响了。显然这个数据结构可以用线段树/前缀最值树状数组来实现。最后一个问题就是我们怎么让“当前最大值对应的最小值最大”这个问题了，因为我们知道每一个连通分量都是要选一种方案的，也就是说我无论如何都会有一个$max$和一个$min$产生，但是这两种哪个更好呢？对我们的做法来说显然是更大的$min$更好了，所以做的过程中再用一个pos数组记录下之前有没有出现过当前枚举到的元素的孪生方案出现，如果有的话就把之前那个位置在线段树里改成$max(curmax,postmax)$，这样就可以保证我们在合法的选择前提下结果最优了。
wa点：二染色写错了，然后是两个更新的先后逻辑写错了emmm，一定要考虑清楚每次去除什么，加入什么，查询什么。
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
//typedef long long ll;
const int maxn=4e5+5;
const int INF=0x3f3f3f3f;
struct node{
int id;
ll mn,mx;
node(){
id=0,mn=INF,mx=0;
}
node(int id,ll mn,ll mx):id(id),mn(mn),mx(mx){}
bool operator<(const struct node& rhs)const{
if(mx!=rhs.mx)
return mx<rhs.mx;
else
return mn<rhs.mn;
}
};
node ns[maxn*4];
int pos[maxn*2],pmn[maxn];
int trm[maxn*4];
void pushup(int o,int l,int r){
trm[o]=min(trm[o<<1],trm[o<<1|1]);
}
void build(int o,int l,int r){
if(l==r){
trm[o]=INF;
return ;
}
int mid=(l+r)>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
trm[o]=INF;
}
int px,pv;
void update(int o,int l,int r){
if(l==r){
trm[o]=pv;
return ;
}
int mid=(l+r)>>1;
if(px<=mid) update(o<<1,l,mid);
else update(o<<1|1,mid+1,r);
pushup(o,l,r);
}
int ql,qr;
int query(int o,int l,int r){
if(ql<=l&&r<=qr){
return trm[o];
}
int mid=(l+r)>>1,res=INF;
if(ql<=mid) res=min(res,query(o<<1,l,mid));
if(mid<qr) res=min(res,query(o<<1|1,mid+1,r));
return res;
}
int n,m,block,cnt,ans;
int dmx,dmn,lmx,lmn;
int ls[maxn],ds[maxn];
vector<int> G[maxn];
void addedge(int u,int v){
G[u].push_back(v);
G[v].push_back(u);
}
int vis[maxn];
bool dfs(int u,int p,int flag){
if(vis[u]!=-1) return flag==vis[u];//error1
vis[u]=flag;
if(flag){
dmx=max(dmx,ds[u]),dmn=min(dmn,ds[u]);
lmx=max(lmx,ls[u]),lmn=min(lmn,ls[u]);
}
else{
dmx=max(dmx,ls[u]),dmn=min(dmn,ls[u]);
lmx=max(lmx,ds[u]),lmn=min(lmn,ds[u]);
}
int len=G[u].size();
for(int i=0;i<len;i++){
if(G[u][i]==p) continue;
if(!dfs(G[u][i],u,1^flag)) return false;
}
return true;
}
void init(){
for(int i=0;i<=n;i++) G[i].clear(),vis[i]=-1,pos[i]=0,pmn[i]=INF;
block=0;cnt=0;ans=INF;
}
int main(){
int T,Case=0,u,v,flag;
scanf("%d",&T);
while(T--){
Case++;flag=1;
printf("Case %d: ",Case);
scanf("%d%d",&n,&m);
init();
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
addedge(u,v);
}
for(int i=1;i<=n;i++){
scanf("%d%d",&ls[i],&ds[i]);
}
for(int i=1;i<=n;i++){
if(vis[i]==-1){
block++;
dmx=lmx=0,dmn=lmn=INF;
if(!dfs(i,-1,0)){
flag=0;
break;
}
ns[block*2-1].id=ns[block*2].id=block;
ns[block*2-1].mn=lmn,ns[block*2-1].mx=lmx;
ns[block*2].mn=dmn,ns[block*2].mx=dmx;
}
}
if(flag==0){puts("IMPOSSIBLE");continue;}
sort(ns+1,ns+1+block*2);
build(1,1,block*2);
for(int i=1;i<=(block<<1);++i){
int idx=ns[i].id,cmn=INF,cmx=ns[i].mx;
if(pos[idx]){
px=pos[idx],pv=max(ns[i].mn,pmn[idx]);//error2
update(1,1,block*2);
if(cnt>=block){
ql=1,qr=i;
cmn=query(1,1,block*2);
ans=min(ans,cmx-cmn);
}
}
else{
cnt++;
px=pos[idx]=i,pv=pmn[idx]=ns[i].mn;//error3
update(1,1,block*2);
if(cnt>=block){
ql=1,qr=i;
cmn=query(1,1,block*2);
ans=min(ans,cmx-cmn);
}
}
}
printf("%d\n",ans);
}
}