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
    
     #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
     
       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
      
        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！