[POI2015]PUS

PUS"/>

[POI2015]PUS

传送门

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！

转载于:.html