[POI2015]PUS

比眉伴天荒 2021-12-22 00:15 106阅读 0赞

## [ 传送门][Link 1] ##

## **Description**  ##

> 给定一个长度为n的正整数序列 a ,每个数都在 1到 10^9范围内,告诉你其中 s个数,并给出 m条信息,每条信息包含三个数 l,r,k以及接下来 k个正整数,表示 \\(a\_l..a\_\{l+1\}...a\_\{r-1\}..a\_r\\)里这 k个数中的任意一个都比任意一个剩下的 \\(r-l+1-k\\)个数大 (严格大于，即没有等号)。
> 
> 请任意构造出一组满足条件的方案，或者判断无解。

## **Solution**  ##

> 显然是一个可以直接用拓扑排序完成的差分约数系统
> 
> 判环很容易，如果有点没有被访问到，就一定存在环了，此时无解
> 
> 涉及到一个点连向一个区间，采用**古老**的线段树优化建图

## **Code**  ##

#include<bits/stdc++.h>
    #define max(a,b) ((a)>(b)?(a):(b))
    inline int read()
    {
        int x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
        return x*f;
    }
    const int MN=1e5+5,MM=MN*5,ME=MN*16;
    #define mid (l+r>>1)
    int N,S,M;
    int a[MM],tt,ls[MM],rs[MM],root,rd[MM];
    struct edge{int to,w,nex;}e[ME];int en,hr[MM];
    inline void ins(int x,int y,int c){++rd[y];e[++en]=(edge){y,c,hr[x]};hr[x]=en;}
    void build(int &x,int l,int r)
    {
        if(l==r) {x=l;return;}
        x=++tt;build(ls[x],l,mid);build(rs[x],mid+1,r);
        ins(ls[x],x,0);ins(rs[x],x,0);
    }
    std::vector<int> A;
    void Insert(int x,int l,int r,int a,int b)
    {
        if(l==a&&r==b){ins(x,tt,0);return;}
        if(b<=mid)Insert(ls[x],l,mid,a,b);
        else if(a>mid) Insert(rs[x],mid+1,r,a,b);
        else Insert(ls[x],l,mid,a,mid),Insert(rs[x],mid+1,r,mid+1,b);
    }
    int d[MM];
    std::queue<int> que;
    inline void topo()
    {
        register int i;
        for(i=1;i<=N;++i)if(!rd[i])que.push(i),d[i]=a[i]?a[i]:1;
        while(!que.empty())
        {
            int u=que.front();que.pop();
            for(i=hr[u];i;i=e[i].nex)
            {
                d[e[i].to]=max(d[e[i].to],d[u]+e[i].w);
                if(d[e[i].to]>a[e[i].to]&&a[e[i].to]>0) puts("NIE"),exit(0);
                if(!--rd[e[i].to])que.push(e[i].to);
            }
        }
    }
    signed main()
    {
        register int i,l,r,k;
        tt=N=read();S=read();M=read();
        while(S--) i=read(),d[i]=a[i]=read();
        build(root,1,N);
        while(M--)
        {
            l=read();r=read();k=read();
            A.clear();A.push_back(l-1);++tt;
            while(k--) A.push_back(read());A.push_back(r+1);
            for(i=A.size()-1;i>0;--i)if(A[i]-A[i-1]>1)Insert(root,1,N,A[i-1]+1,A[i]-1);
            for(i=A.size()-2;i>0;--i)ins(tt,A[i],1);
        }
        topo();
        for(i=1;i<=N;++i)if(d[i]<1||d[i]>1e9)return 0*puts("NIE");
        puts("TAK");
        for(i=1;i<=N;++i)
        {
            if(a[i]) printf("%d ",a[i]);
            else printf("%d ",d[i]);
        }
    }

--------------------

Blog来自**PaperCloud**，未经允许，请勿转载，TKS！

转载于:https://www.cnblogs.com/PaperCloud/p/10568863.html

[Link 1]: https://www.luogu.org/problemnew/show/P3588