Description

有一个大小为 n ( n ≤ 1 0 9 ) n(n≤10^9) n(n≤109)的排列和 m ( m ≤ 50 ) m(m≤50) m(m≤50)个限制，每个限制 ( l , r , q ) (l,r,q) (l,r,q)表示在区间 [ l , r ] [l,r] [l,r]内的最大值必须是 q q q，问是否存在一个满足所有条件的排列

Solution

考虑贪心（网络流也可以做，本质是一样的）
分析“ [ l , r ] [l,r] [l,r]内的最大值必须是 q q q”这句话，发现 ① [ l , r ] ①[l,r] ①[l,r]内必须有一个 q q q， ② [ l , r ] ②[l,r] ②[l,r]内所有数必须 ≤ q ≤q ≤q
1. 1. 1.如果有一个 q q q对应的所有区间的交集为空，不满足 ① ① ①（ q q q必须同时在这些区间内）
2. 2. 2.如果在 &lt; q &lt;q <q的那些对应区间的并中填 1... q − 1 1...q-1 1...q−1不能填满的话，一定有一个 q q q要填在 &lt; q &lt;q <q的某个区间内，不满足 ② ② ②
n n n可以通过离散化解决
复杂度 O ( T m 2 ) O(Tm^2) O(Tm2)（ T T T为数据组数）

Code

#include<bits/stdc++.h>
using namespace std;
const int N=102;
int len[N],mn[N],l[N],r[N],q[N],b[N],L,R,i,j,k,T,n,m,id[N],cnt,tot,c[N],las,sum;
bool fl,flag;
bool cmp(int x,int y){return q[x]<q[y];}
bool cmp1(int x,int y){return mn[x]<mn[y] || mn[x]==mn[y] && x<y;}
int main(){
	scanf("%d",&T);
	for (;T--;){
		scanf("%d%d",&n,&m);
		memset(len,0,sizeof(len));
		memset(mn,1,sizeof(mn));
		cnt=tot=0;
		for (i=1;i<=m;i++){
			scanf("%d%d%d",&l[i],&r[i],&q[i]);
			id[i]=i,b[++cnt]=l[i]-1,b[++cnt]=r[i];
		}
		sort(b+1,b+cnt+1);
		cnt=unique(b+1,b+cnt+1)-b-1;
		for (i=1;i<=m;i++)
			for (j=1;j<cnt;j++)
				if (l[i]-1<=b[j] && b[j+1]<=r[i]) mn[j]=min(mn[j],q[i]);
		sort(id+1,id+m+1,cmp);
		flag=1;
		for (i=j=1;i<=m && flag;i=j+1){
			L=l[id[i]]-1,R=r[id[i]],j=i;
			while (j<m && q[id[j]]==q[id[j+1]]) j++,L=max(L,l[id[j]]-1),R=min(R,r[id[j]]);
			if (L>R) flag=0;
			fl=0;
			for (k=1;k<cnt && !fl;k++)
				if (L<=b[k] && b[k+1]<=R && mn[k]==q[id[j]]) fl=1;
			if (!fl) flag=0;
		}
		if (!flag){puts("Impossible");continue;}
		for (i=1;i<cnt;i++) id[i]=i;
		sort(id+1,id+cnt,cmp1);
		for (i=1;i<cnt;i++){
			if (mn[id[i]]!=mn[id[i-1]]) c[++tot]=id[i];
			len[tot]+=b[id[i]+1]-b[id[i]];
		}
		sum=las=0;
		for (i=1;i<=tot && flag;i++){
			sum+=mn[c[i]]-las,las=mn[c[i]];
			if (sum<len[i]) flag=0;
			sum-=len[i];
		}
		puts(flag?"Possible":"Impossible");
	}
}