题意
你需要构造一个 \(1∼N\) 的排列，满足
\(M\) 个要求，要求形式是给出 \(l,r\) 中的最大值或最小值。
思路
不难看出，这是一个二分图匹配问题。我们要给每个位置匹配一个数。那么怎么建边呢？我们发现根据题目给出的要求，好像不是很好直接看出每个位置能匹配哪些数。不过正难则反，题目给出的要求是很容易看出每个位置不能匹配哪些数的。显然如果题目给出
\([l,r]\) 中最小的数是 \(x\)，那么这些位置不能与任何小于 \(x\) 的数匹配。大于同理。
这样就够了吗？其实是有问题的。我们这样无法保证 \(x\) 这个数一定被分配到 \([l,r]\) 这个区间里。所以我们还有让所有不在
\([l,r]\) 的数都不能匹配到 \(x\)，这样就保证满足题目条件了。
至于二分图匹配部分，可以用匈牙利，当然我用的 Dinic。
丑陋的代码（跑得贼慢）
``` #include <bits/stdc++.h> #define int long long using
namespace std; bool ok[205][205]; int
n,m,cnt=1,lst[415],s,t,inf=0x3f3f3f3f,now[415],dep[415],flow,seat[415];
struct edge{ int f,t,val,lst; edge(int f=0,int t=0,int val=0,int lst=0):
f(f),t(t),val(val),lst(lst){}; }e[400005]; void add(int u,int v,int w){
e[++cnt]=edge(u,v,w,lst[u]);lst[u]=cnt;
e[++cnt]=edge(v,u,0,lst[v]);lst[v]=cnt; } bool bfs(){
memset(dep,-1,sizeof(dep)); dep[s]=0; queue q; q.push(s);
while(!q.empty()){ int u=q.front(); q.pop(); now[u]=lst[u]; for(int
i=lst[u];i;i=e[i].lst){ int v=e[i].t; if(dep[v]==-1&&e[i].val){
dep[v]=dep[u]+1; q.push(v); } } } return dep[t]!=-1; } int dfs(int u,int
in){ if(u==t)return in; int out=0; for(int i=now[u];i;i=e[i].lst){
now[u]=i; int v=e[i].t; if(dep[v]==dep[u]+1&&e[i].val){ int
go=dfs(v,min(in,e[i].val)); in-=go,out+=go; e[i].val-=go,e[i^1].val+=go;
if(!in)break; } } if(!out)dep[u]=-1; return out; } signed main(){
cin>>n>>m; for(int i=1;i<=m;i++){ int op,u,v,x;
cin>>op>>u>>v>>x; if(op==1){ for(int
j=u;j<=v;j++){ for(int k=x+1;k<=n;k++){ ok[j][k]=1; } } for(int
j=1;j<u;j++){ ok[j][x]=1; } for(int j=v+1;j<=n;j++){ ok[j][x]=1; }
} else{ for(int j=u;j<=v;j++){ for(int k=1;k<x;k++){ ok[j][k]=1; }
} for(int j=1;j<u;j++){ ok[j][x]=1; } for(int j=v+1;j<=n;j++){
ok[j][x]=1; } } } s=0,t=n*2+1; for(int i=1;i<=n;i++){ add(s,i,1);
add(i+n,t,1); for(int j=1;j<=n;j++){ if(!ok[i][j])add(i,j+n,1); } }
while(bfs()){ flow+=dfs(s,inf); } if(flow!=n)puts(“-1”); else{ for(int
i=2;i<=cnt;i++){
if(!e[i].val&&e[i^1].val&&e[i].f<=n&&e[i].f&&e[i].t>n&&e[i].t!=t){
seat[e[i].f]=e[i].t; } } for(int
i=1;i<=n;i++)cout<<seat[i]-n<<’ ’; } return 0; }