P3588 【[POI2015]PUS】

终于有个能让我一遍过的题了，写篇题解纪念一下
给定长度为n的序列和其中部分已知的数，还有m个大小关系：区间\([l,r]\)中，有k个给定的数比剩下的\(r-l+1-k\)个数都大
求是否有解，有解给出任意一个合法方案
按大小关系，从大的数向小的数连边
直接建图肯定不行，考虑用线段树优化，如果你不会线段树优化建边，点这里
对于每个\([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的情况，超出题目要求的值域，无解
剩下的在注释里

#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;
}

P3588 【[POI2015]PUS】（线段树优化建边）

原文：https://www.cnblogs.com/suxxsfe/p/12527538.html