题解 P3588 【[POI2015]PUS】
whyl
2019-10-01 21:15:41
今天我才算是真正意义上理解了线段树优化建图
以前我只会一个点想一段区间连边
还不会许多点想许多区间连边
（其实本质意义上是一样的啊。。。）
唯一一个不同的就是要不要新开一个节点
连接两部分罢了
最后拓扑DP判断有无解
看是否有环是否满足范围即可
（其实最后要判a[i]是不是有小于0的
如果有小于0的
那就是无解
但是我没判也A掉了
懒得改了
）
放代码（其实我的代码很亲民的。。。）
```cpp
#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
inline int read(){
int x=0,f=1;
char p=getchar();
while(!isdigit(p)){
if(p=='-') f=-1;
p=getchar();
}
while(isdigit(p)) x=(x<<3)+(x<<1)+p-48,p=getchar();
return x*f;
}
const int maxn=2e5+5;
int n,s,m,a[maxn<<3],head[maxn<<3],ver[maxn<<3],in[maxn<<3],len;
int nxt[maxn<<3],cnt,tot,bel[maxn<<3],pos[maxn<<3],xue[maxn<<3];
inline void add(int x,int y){
nxt[++cnt]=head[x];
head[x]=cnt;
ver[cnt]=y;
}
inline void build(int k,int l,int r){
if(l==r){
bel[k]=l;
pos[l]=k;
return;
}
tot=max(tot,k<<1|1);
add(k,k<<1);
in[k<<1]++;
add(k,k<<1|1);
in[k<<1|1]++;
build(lson);
build(rson);
}
inline void connect(int k,int l,int r,int L,int R,int pos){
if(L>R) return ;
if(L<=l&&r<=R){
add(pos,k);
in[k]++;
return ;
}
if(L<=mid) connect(lson,L,R,pos);
if(R>mid) connect(rson,L,R,pos);
return;
}
inline void topsort(){
queue<int> q;
q.push(1);
a[1]=1e9;
memset(xue,127,sizeof(xue));
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(bel[y]) xue[y]=min(xue[y],a[x]-1);
else xue[y]=min(xue[y],a[x]);
if(xue[y]<a[y]){
cout<<"NIE\n";
exit(0);
}
in[y]--;
if(in[y]==0){
if(bel[y]) len++;
q.push(y);
if(a[y]==0) a[y]=xue[y];
}
}
}
}
int main(){
n=read();s=read();m=read();
build(1,1,n);
for(int i=1;i<=s;i++){
int x=read(),y=read();
a[pos[x]]=y;
}
// for(int i=1;i<=n;i++) cout<<pos[i]<<" ";
// cout<<endl<<endl;
// for(int i=1;i<=n;i++) cout<<a[pos[i]]<<" ";
// cout<<endl<<endl;
for(int i=1;i<=m;i++){
int l=read(),r=read(),k=read();
int last=l;
int node_cnt=++tot;
while(k--){
int x=read();
// cout<<pos[x]<<" "<<node_cnt<<endl;
add(pos[x],node_cnt);
in[node_cnt]++;
// cout<<last<<" "<<x-1<<" "<<node_cnt<<endl;
connect(1,1,n,last,x-1,node_cnt);
last=x+1;
}
// cout<<last<<" "<<r<<" "<<node_cnt<<endl;
connect(1,1,n,last,r,node_cnt);
// cout<<endl;
}
topsort();
if(len!=n){
cout<<"NIE\n";
return 0;
}
cout<<"TAK\n";
for(int i=1;i<=n;i++) cout<<a[pos[i]]<<" ";
cout<<endl;
return 0;
}
```