还以为是差分约束，原来拓扑排序也能解决这样的问题=。=
类似差分约束的建图方式，我们把大小关系看做有向边。这样一来图上是不允许存在环的，于是我们可以做拓扑排序。然后问题来了，边数非常大，根本建不出图来=。=
不过我们有一个套路的做法，为每个区间配一个虚点，然后连边时先连到虚点再连到各个目标点。然后问题又来了，这样连边其实是$O(len^2)$的，$len$为区间长度，如果有个很大的区间这就萎了=。=
那什么东西解决区间问题好用呢？线段树— —我们用线段树优化建图，每次直接从虚点连到区间上，这样最多会连出来$k+klog$ $n$条边(点向虚点连的+虚点向区间连的)，然后线段树内还有$4*n$条边，总共大概有不到570万条边，还可以接受。再之后做拓扑排序就可以了
注意数值的最大值和连边时的边权
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=,maxx=1e9;
int num[N],ls[N],rs[N];
int vis[N],ins[N],dp[N],mem[N],que[N];
int p[N],noww[M],goal[M],val[M],deg[N];
int n,s,m,l,r,k,f,b,rd,t1,t2,t3,tn,cnt,tot,pos;
void GG(){printf("NIE"),exit();}
void link(int f,int t,int v)
{
noww[++cnt]=p[f],p[f]=cnt;
goal[cnt]=t,val[cnt]=v,deg[t]++;
}
void Create(int nde,int l,int r)
{
if(l==r) num[l]=nde;
else
{
int mid=(l+r)/;
ls[nde]=++tot,rs[nde]=++tot;
link(nde,ls[nde],),link(nde,rs[nde],);
Create(ls[nde],l,mid),Create(rs[nde],mid+,r);
}
}
void Change(int nde,int l,int r,int nl,int nr,int task)
{
if(l>nr||r<nl)
return ;
else if(l>=nl&&r<=nr)
link(task,nde,);
else
{
int mid=(l+r)/;
Change(ls[nde],l,mid,nl,nr,task);
Change(rs[nde],mid+,r,nl,nr,task);
}
}
bool DFS(int nde)
{
vis[nde]=ins[nde]=true;
for(int i=p[nde];i;i=noww[i])
{
if(ins[goal[i]]) return false;
if(!vis[goal[i]]&&!DFS(goal[i])) return false;
}
ins[nde]=false; return true;
}
int main ()
{
scanf("%d%d%d",&n,&s,&m);
Create(tot=,,n),b=-;
for(int i=;i<=s;i++)
{
scanf("%d%d",&pos,&rd);
mem[num[pos]]=rd;
}
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&t1,&t2,&t3);
int last=t1; tot++;
for(int j=;j<=t3;j++)
{
scanf("%d",&rd); link(num[rd],tot,);
if(last<rd) Change(,,n,last,rd-,tot);
last=rd+;
}
if(last<=t2) Change(,,n,last,t2,tot);
}
for(int i=;i<=tot;i++)
dp[i]=mem[i]?mem[i]:maxx;
for(int i=;i<=tot;i++)
{
if(!vis[i]&&!DFS(i)) GG();
if(!deg[i]) que[++b]=i;
}
while(f<=b)
{
if(dp[tn=que[f++]]<) GG();
for(int i=p[tn];i;i=noww[i])
{
if(dp[tn]-val[i]<mem[goal[i]]) GG();
dp[goal[i]]=min(dp[goal[i]],dp[tn]-val[i]);
if(!(--deg[goal[i]])) que[++b]=goal[i];
}
}
printf("TAK\n");
for(int i=;i<=n;i++) printf("%d ",dp[num[i]]);
return ;
}