题解 P3588 【[POI2015]PUS】

· · 题解

我们在做题之前，先要知道这是一道图论题

题意描述有些绕，我在这里再阐述一遍：

大于关系可以看做是一条边，由较大的数指向较小的数。对于每一个询问，我们考虑让这k个位置上的数与区间内其他的位置两两连有向边。这样一来，问题就转化到图上了。

首先，图上若有环则一定无解，因为它意味着x>x。

那么问题变为DAG上问题，只要我们从入读为0的位置开始DP即可。贪心的想，最大的数越大，留给下面的空间就越大(注意数列中的数大于0！)，所以每个数的可能值全部设置为1e9。DP时假如遇到了已经确定的数，却发现它撑死了也打不到他预设的值（否则与其他单调关系矛盾），那么问题无解。

最后若有解，输出答案即可。

好完美啊，在你看到\sum k\leq 300000之前还以为是提高组水题。

假如按之前说的那样建图，一次操作就要加入k(r-l+1-k)条边，最坏情况下加入的边数在N^3级别，空间直接爆炸。

也许你会说，我们可以采用“电话交换机”的建图思想，不再两两连边 而是新拉出一个超级节点，然后只需要k个点向它连边，它向区间内其余点连边即可，只要k+(r-l+1-k)=r-l+1条边即可

然而这还是不行。因为如果每个操作区间都是上十万的大区间，而k每次只有1，最多还是要连N\sum k条边,仍然爆炸。

注意到，每次我们的空间浪费在，有大量位置连续的点，超级节点却向它们一一连了边。发挥想象力，有什么东西能提高区间操作的效率呢？

线段树！！！

没错，我们把数列建成一棵线段树，然后对于每个操作区间，它会被k个点割成最多k+1个子区间，对于每个区间，可以化成线段树上的最多log(n)个已知区间，对于超级节点连出的边，一次操作要加klog(n)条，算上连向超级节点的，总共是k+klog(n)。于是总共的边数在(\sum k)log(n)级别，完全可以接受。

这样连边以后，要注意线段树自身的边只是形式，要赋权为0。

之后按照之前所说的，按拓扑序DP就行了。

#include<iostream>
#include<cstdio>
#include<queue>
#define lson ls[u],l,md
#define rson rs[u],md+1,r 
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(u) for(int i=hd[u],v=e[i].v,w=e[i].w;i;i=e[i].n,v=e[i].v,w=e[i].w) 
using namespace std;
const int N=100100,TO=600600,M=7007000,INF=1000000000;
struct edge{int n,v,w;}e[M];
int n,s,m,p,v,u,x,k,l,r,pr,cnt,fl,ok,id[N],ins[TO];
int hd[TO],vis[TO],in[TO],f[TO],ls[TO],rs[TO],o[TO];
void add(int u,int v,int w){e[++fl]=(edge){hd[u],v,w};hd[u]=fl;in[v]++;}
queue<int>q; 
int read(){
    char ch=getchar();int x=0,o=1;
    for(;ch<'0' || '9'<ch;ch=getchar()) if(ch=='-') o=-1;
    for(;'0'<=ch&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch^'0');
    return x*o;
}
void prg(){
    FOR(x,1,cnt){
        cout<<x<<':';
        REP(x) cout<<v<<'-'<<w<<' ';cout<<endl;
    }
}
void bld(int u,int l,int r){
    if(l==r) {id[l]=u;cnt=max(cnt,u);return;}
    int md=l+r>>1;
    ls[u]=++cnt,rs[u]=++cnt;
    bld(lson),bld(rson);
    add(u,ls[u],0),add(u,rs[u],0); 
}
void adde(int u,int l,int r,int x,int y,int z){
    if(x<=l && r<=y) {add(z,u,1);return;}
    if( y<l || r<x ) return;
    int md=l+r>>1;
    adde(lson,x,y,z),adde(rson,x,y,z);
}
void dfs(int u){
    vis[u]=1;ins[u]=1;
    REP(u){
        if(ins[v]) ok=0;
        if(!vis[v]) dfs(v);
    }
    ins[u]=0;
} 
int main(){
    scanf("%d%d%d",&n,&s,&m); 
    cnt=1,bld(1,1,n);
    FOR(i,1,s) p=read(),f[id[p]]=read(),o[id[p]]=f[id[p]];
    FOR(i,1,m){
        l=read(),r=read(),k=read();
        pr=l;++cnt;
        FOR(j,1,k){
            x=read();
            add(id[x],cnt,0);
            if(pr<=x-1) adde(1,1,n,pr,x-1,cnt);
            pr=x+1; 
        }if(pr<=r) adde(1,1,n,pr,r,cnt);
    } 
    FOR(i,1,cnt) if(!f[i]) f[i]=INF;
    FOR(i,1,cnt) if(!vis[i]){
        ok=1;dfs(i);
        if(!ok){printf("NIE");return 0;}
    }
    FOR(i,1,cnt) if(!in[i]) q.push(i);
    while(!q.empty()){
        u=q.front();q.pop();
        REP(u){
            in[v]--;
            if(o[v]>f[u]-w){printf("NIE");return 0;}
            f[v]=min(f[v],f[u]-w);
            if(!in[v]) q.push(v);
            if(f[v]<1){printf("NIE");return 0;}  
        }
    } 
    printf("TAK\n");
    FOR(i,1,n) printf("%d ",f[id[i]]);
}