给定一个长度为n的正整数序列a，每个数都在1到10^9范围内，告诉你其中s个数，并给出m条信息，每条信息包含三个数l,r,k以及接下来k个正整数，表示a[l],a[l+1],...,a[r-1],a[r]里这k个数中的任意一个都比任意一个剩下的r-l+1-k个数大（严格大于，即没有等号）。请任意构造出一组满足条件的方案，或者判断无解。
Solution
这个模型有点像差分约束系统，但是建图复杂度过高。
考虑到每次一个区间内的k个数将整段序列划分为k+1个区间，所以我们考虑用线段树优化这个过程，每次建一个s点和这k个点连边，再和剩下的数所对应的区间连边，这样就保证了我们建图的复杂度。
然后题目中给的数域是1-1e9，有两种方法，一种是从极小向大里跑，另一种是从极大往小里跑。
如果是前一种，那么我的转移顺序必须为从小到大，回顾我们的连边，发现需要从一堆区间向S走，但是这一堆区间需要下面的节点转移而来，所以我们在线段树上连边的方式为从下往上连。
后一种反之。
Code
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define N 400002
#define M 4000003
using namespace std;
queue<int>q;
int head[N],tot,du[N],ji[N],anti_ji[N],top,rs[N],ls[N],s,n,m,pos,ss,x,a[N],l,r,k,num[N],tag;
struct node{
int n,to,l;
}e[M];
inline void add(int u,int v,int l){
e[++tot].n=head[u];
e[tot].to=v;
e[tot].l=l;du[v]++;
head[u]=tot;
}
void build(int cnt,int l,int r){
if(l==r){ji[l]=cnt;anti_ji[cnt]=l;return;}
int mid=(l+r)>>;
ls[cnt]=++top;rs[cnt]=++top;
add(ls[cnt],cnt,);add(rs[cnt],cnt,);
build(ls[cnt],l,mid);build(rs[cnt],mid+,r);
}
void query(int cnt,int l,int r,int L,int R){
if(l>=L&&r<=R){
add(cnt,s,);
return;
}
int mid=(l+r)>>;
if(mid>=L)query(ls[cnt],l,mid,L,R);
if(mid<R)query(rs[cnt],mid+,r,L,R);
}
int main(){
top=;
scanf("%d%d%d",&n,&ss,&m);
for(int i=;i<=ss;++i)scanf("%d%d",&pos,&x),a[pos]=x;
build(,,n);
for(int i=;i<=m;++i){
scanf("%d%d%d",&l,&r,&k);int p=l;s=++top;
for(int j=;j<=k;++j){
scanf("%d",&x);add(s,ji[x],);
if(x>p)query(,,n,p,x-);
p=x+;
}
if(p<=r)query(,,n,p,r);
}
for(int i=;i<=top;++i){
if(!du[i])q.push(i),num[i]=;
if(a[anti_ji[i]])num[i]=a[anti_ji[i]];
}
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].n){
int v=e[i].to,x=num[u]+e[i].l;
if(!--du[v])q.push(v);
if(!a[anti_ji[v]]){
num[v]=max(num[v],x);
}
else{
num[v]=a[anti_ji[v]];
if(a[anti_ji[v]]<x)tag=;
}
}
}
for(int i=;i<=top;++i)if(du[i])tag=;
for(int i=;i<=n;++i)if(num[ji[i]]>1e9||!num[ji[i]])tag=;
if(tag){
printf("NIE\n");
return ;
}
printf("TAK\n");
for(int i=;i<=n;++i)printf("%d ",num[ji[i]]);
return ;
}
Code2
#include<iostream>
#include<cstdio>
#include<queue>
#define N 400002
#define M 4000003
using namespace std;
queue<int>q;
int head[N],tot,du[N],ji[N],anti_ji[N],top,rs[N],ls[N],s,n,m,pos,ss,x,a[N],l,r,k,num[N],tag;
struct node{
int n,to,l;
}e[M];
inline void add(int u,int v,int l){
e[++tot].n=head[u];
e[tot].to=v;
e[tot].l=l;du[v]++;
head[u]=tot;
}
void build(int cnt,int l,int r){
if(l==r){ji[l]=cnt;anti_ji[cnt]=l;return;}
int mid=(l+r)>>;
ls[cnt]=++top;rs[cnt]=++top;
add(cnt,ls[cnt],);add(cnt,rs[cnt,);
build(ls[cnt],l,mid);build(rs[cnt],mid+,r);
}
void query(int cnt,int l,int r,int L,int R){
if(l>=L&&r<=R){
add(s,cnt,);
return;
}
int mid=(l+r)>>;
if(mid>=L)query(ls[cnt],l,mid,L,R);
if(mid<R)query(rs[cnt],mid+,r,L,R);
}
int main(){
top=;
scanf("%d%d%d",&n,&ss,&m);
for(int i=;i<=ss;++i)scanf("%d%d",&pos,&x),a[pos]=x;
build(,,n);
for(int i=;i<=m;++i){
scanf("%d%d%d",&l,&r,&k);int p=l;s=++top;
for(int j=;j<=k;++j){
scanf("%d",&x);add(ji[x],s,);
if(x>p)query(,,n,p,x-);
p=x+;
}
if(p<=r)query(,,n,p,r);
}
for(int i=;i<=top;++i){
if(!du[i])q.push(i);
num[i]=1e9;
}
while(!q.empty()){
int u=q.front();q.pop();if(anti_ji[u]&&!num[u])num[u]=1e9;
for(int i=head[u];i;i=e[i].n){
int v=e[i].to,x=num[u]-e[i].l;
if(!--du[v])q.push(v);
if(!a[anti_ji[v]]){
num[v]=min(num[v],x);
}
else{
num[v]=a[anti_ji[v]];
if(a[anti_ji[v]]>x)tag=;
}
}
}
for(int i=;i<=top;++i)if(du[i])tag=;
if(tag){
printf("NIE\n");
return ;
}
printf("TAK\n");
for(int i=;i<=n;++i)printf("%d ",num[ji[i]]);
return ;
}