LINK：POI2015 Pustynia
题意不再说 比余下的数字要大 并且判断是否有解 且输出方案。
考虑差分约束模型。对于连边 由于每次的区间过大我们不可能暴力的去连边 所以考虑线段树优化建图。
复杂度：由于(sum kleq 3*10^5) 所以最多 Klogn条边 不过每次连边需要新建一个点 都是在可接受的范围之内。
考虑如何判断无解 对于 a>b 可以转换成 a>=b+1 变化一下形势 b<=a-1 a向b连一条边 这样做在输出方案好像会很别扭。
就原来的形式 a>=b+1 b向a连边 表示a至少是要>=b+1 我们不能跑spfa了 图过大。
但是考虑这张图的特殊性 这是一个有向无环图 如果有环那么必然无解。
考虑最后如何构造解 我们正向的topsort一下 然后类似dp的形式 求出解即可。
当然最后还需要判断值域是否合适。
const int MAXN=100010,maxn=2000010;
int n,m,v,flag,cnt,len,root;
int a[MAXN],f[maxn],q[maxn];
int lin[maxn],ver[maxn],nex[maxn],e[maxn],ru[maxn];
struct wy{int l,r;}t[MAXN<<2];
inline void add(int x,int y,int z)
{
ver[++len]=y;
nex[len]=lin[x];
lin[x]=len;
e[len]=z;
++ru[y];
}
inline void build(int &p,int l,int r)
{
p=++cnt;
if(l==r){add(p,l,0);return;}
int mid=(l+r)>>1;
build(l(p),l,mid);
build(r(p),mid+1,r);
add(p,l(p),0);add(p,r(p),0);
}
inline void change(int p,int l,int r,int L,int R,int x)
{
if(L>R)return;
if(L<=l&&R>=r){add(x,p,1);return;}
int mid=(l+r)>>1;
if(L<=mid)change(l(p),l,mid,L,R,x);
if(R>mid)change(r(p),mid+1,r,L,R,x);
}
inline void topsort()
{
int l=0,r=0;
for(int i=1;i<=cnt;++i)
{
f[i]=INF;
if(!ru[i])q[++r]=i;
}
while(++l<=r)
{
int x=q[l];
if(f[x]<1){flag=1;return;}
if(x<=n&&a[x])
{
if(f[x]<a[x]){flag=1;return;}
else f[x]=a[x];
}
for(int i=lin[x];i;i=nex[i])
{
int tn=ver[i];
f[tn]=min(f[tn],f[x]-e[i]);
--ru[tn];if(!ru[tn])q[++r]=tn;
}
}
for(int i=1;i<=cnt;++i)if(ru[i])flag=1;
}
int main()
{
freopen("1.in","r",stdin);
get(n);get(v);get(m);
for(int i=1;i<=v;++i)
{
int x;
get(x);get(a[x]);
if(a[x]>INF)flag=1;
}
if(flag){puts("NIE");return 0;}
cnt=n;build(root,1,n);
rep(1,m,i)
{
int x,y,k,p;
get(x);get(y);get(k);
++cnt;
rep(1,k,j)
{
get(p);
add(p,cnt,0);
if(j==1){if(x<p)change(root,1,n,x,p-1,cnt);}
else if(x+1!=p)change(root,1,n,x+1,p-1,cnt);
x=p;
}
if(p<y)change(root,1,n,p+1,y,cnt);
}
topsort();
if(flag){puts("NIE");return 0;}
puts("TAK");
rep(1,n,i)printf("%d ",f[i]);
return 0;
}