题解 P3588 【[POI2015]PUS】——线段树优化建边
suxxsfe
2020-02-21 20:46:38
# [P3588 【[POI2015]PUS】](https://www.luogu.com.cn/problem/P3588)
终于有个能让我一遍过的题了，写篇题解纪念一下
给定长度为n的序列和其中部分已知的数，还有m个大小关系：区间$[l,r]$中，有k个给定的数比剩下的$r-l+1-k$个数都大
求是否有解，有解给出任意一个合法方案
按大小关系，从大的数向小的数连边
直接建图肯定不行，考虑用线段树优化，如果你不会线段树优化建边，点[这里](https://www.luogu.com.cn/blog/suxxsfe/xian-duan-shu-you-hua-jian-bian)
对于每个$[l,r]$的区间，这k个给定的数会把区间分成$k+1$个小区间
新建一个虚拟节点，这k个数分别向虚拟节点连边，这个虚拟节点再通过线段树向$k+1$个小区间连边
有环会出现自己大于自己的情况，要先判掉
再拓扑排序，求一种序列
先把未给出的数赋值为1e9，然后对于每一条u->v的边，```a[v]=min(a[v],a[u]-len[i])```，```len[i]```为边权
线段树中的边是虚构的只是为了让它联通起来，所以边权为0，实际的边边权为1，也就是```a[v]```至少比```a[u]```少1
如果出现```a[v]```为给定的数，且```a[v]>a[u]-len[i]```，则找不出合法方案
如果出现了```a[v]<0```的情况，超出题目要求的值域，无解
剩下的在注释里
```cpp
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<iomanip>
#include<cstring>
#define R register
#define EN std::puts("")
#define LL long long
inline int read(){
int x=0,y=1;
char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
int n,s,m,nn;
int a[2000006],should[2000006];//should[i]=1，说明i号数字为给定的数字
int in[2000006];
struct tr{
tr *ls,*rs;
int id;
}dizhi[2000006],*root=&dizhi[0];
int tot;
int fir[2000006],to[2000006],nex[2000006],len[2000006];
int etot;
int vis[2000006],instack[2000006];//vis标记是否被访问，instack标记是否在栈中
int huan;//记录是否有环
void dfs(int u){
vis[u]=instack[u]=1;
for(R int i=fir[u];i;i=nex[i]){
if(instack[to[i]]) huan=1;//遇到已经在栈中节点，说明有环
if(!vis[to[i]]) dfs(to[i]);
}
instack[u]=0;
}
inline void add(int u,int v,int x){
to[++etot]=v;len[etot]=x;
nex[etot]=fir[u];fir[u]=etot;
}
void build(tr *tree,int l,int r){
if(l==r){tree->id=l;return;}
int mid=(l+r)>>1;
tree->ls=&dizhi[++tot];tree->rs=&dizhi[++tot];
build(tree->ls,l,mid);build(tree->rs,mid+1,r);
tree->id=++nn;
// std::printf("block %d %d id:%d\n",l,r,tree->id);
add(tree->id,tree->ls->id,0);add(tree->id,tree->rs->id,0);
in[tree->ls->id]++;in[tree->rs->id]++;
}
void addtree(tr *tree,int l,int r,int ql,int qr,int u){
if(ql<=l&&r<=qr){add(u,tree->id,0);in[tree->id]++;return;}//在由k个点向虚拟节点连边时建的边边权为1，所以这里要建边权为0的边
int mid=(l+r)>>1;
if(ql<=mid) addtree(tree->ls,l,mid,ql,qr,u);
if(qr>mid) addtree(tree->rs,mid+1,r,ql,qr,u);
}
std::queue<int>q;
inline void topo(){
for(R int i=1;i<=nn;i++) if(!a[i])a[i]=1e9;//先把为给定的数设为最大
for(R int i=1;i<=nn;i++) if(!in[i])q.push(i);
while(!q.empty()){
R int u=q.front();q.pop();
for(R int i=fir[u];i;i=nex[i]){
int v=to[i];
if(should[v]){
if(a[v]>a[u]-len[i]){std::puts("NIE");std::exit(0);}
}
else a[v]=std::min(a[v],a[u]-len[i]);
if(a[v]<1){std::puts("NIE");std::exit(0);}//超出值域
if(!--in[v]) q.push(v);
}
}
}
int main(){
nn=n=read();s=read();m=read();
for(R int i=1;i<=s;i++){
int pos=read();
a[pos]=read();should[pos]=1;
}
build(root,1,n);
while(m--){
int l=read(),r=read(),k=read();nn++;
R int last=l,x;
for(R int j=1;j<=k;j++){
x=read();
add(x,nn,1);in[nn]++;
if(x>last) addtree(root,1,n,last,x-1,nn);
last=x+1;
}
if(last<=r) addtree(root,1,n,last,r,nn);
}
for(R int i=1;i<=n;i++)if(!vis[i]){
huan=0;dfs(i);
if(huan){std::puts("NIE");std::exit(0);}
}
topo();
std::puts("TAK");
for(R int i=1;i<=n;i++) std::printf("%d ",a[i]);
// EN;
// for(R int i=1;i<=nn;i++){
// std::printf("%d:",i);
// for(R int j=fir[i];j;j=nex[j]){
// std::printf("(%d %d) ",to[j],len[j]);
// }
// EN;
// }
return 0;
}
```