[POI2015]PUS

题目描述

给定一个长度为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个数大（严格大于，即没有等号）。请任意构造出一组满足条件的方案，或者判断无解。

输入输出格式

输入格式：

第一行包含三个正整数n,s,m(1<=s<=n<=100000，1<=m<=200000)。接下来s行，每行包含两个正整数p[i],d，表示已知a[p[i]]=d[i]，保证p[i]递增。接下来m行，每行一开始为三个正整数l[i],r[i],k[i]（1<=l[i]<r[i]<=n，1<=k[i]<=r[i]-l[i]），接下来k[i]个正整数x[1],x[2],...,x[k[i]]（l[i]<=x[1]<x[2]<...<x[k[i]]<=r[i]），表示这k[i]个数中的任意一个都比任意一个剩下的r[i]-l[i]+1-k[i]个数大。Σk <= 300,000

输出格式：

若无解，则输出NIE。否则第一行输出TAK，第二行输出n个正整数，依次输出序列a中每个数。

 

假如给的是单点大小关系，直接差分约束

如果有解，那么必然是DAG

否则成环的话，由于父子节点的连边本身是DAG，并不会对环产生造成影响。只能是约束条件不合法。

DAG的话，topo最长路即可。

dis就是满足条件的最小值

如果一个点要入队了，检查是否有初值，有的话，val[y]<dis[y]返回false，否则dis[y]=val[y]

如果一个点dis>1e9返回false

topo初始点dis为1（有val就是val）

 

最后输出dis即可。

 

对于区间。

 

发现区间关系，所以线段树优化建图。

 

切割出来的k+1个区间，连向一个虚拟节点，虚拟节点再向k个大权点连边。其中之一有边权（区间不能包含k个点，否则不合法）

 

发现，只是区间向单点连边，所以可以只建立一个线段树。两棵的话，入线段树只有叶子有用。

 

（区间向区间连边就不行了。。因为一棵线段树的话，父子节点边方向没有办法分配。要么不能上，要么不能下）

 

 

 

正确性：

1.连边显然正确，可以保证和条件等价。

2.topo保证更新顺序，一个点入队必然已经考虑完所有的约束条件。

3.判断无解正确。

复杂度：

边数：O(2*n+∑k*logn+k)

 

代码：

判无解：存在一个点没有入队

#include
     
      #define ri register int #define il inline #define numb (ch^'0')#define mid ((l+r)>>1)using namespace std;typedef long long ll;const int N=100000+5;const int M=200000+300000+5;int n,m,s;struct node{    int nxt,to;    int val;}e[2*N+300000*18];il void rd(int &x){    char ch;x=0;    while(!isdigit(ch=getchar()));    for(x=numb;isdigit(ch=getchar());x=(x<<1)+(x<<3)+numb);}int hd[M],cnt;int tot;int id[N];int ls[2*N],rs[2*N];void add(int x,int y,int z){    e[++cnt].nxt=hd[x];    e[cnt].to=y;    e[cnt].val=z;    hd[x]=cnt;}bool vis[M];int q[M],l,r;int du[M];int dis[M],val[M];int rt;void build(int x,int l,int r){    if(l==r) {        id[l]=x;return;    }    ls[x]=++tot;add(tot,x,0);du[x]++;    rs[x]=++tot;add(tot,x,0);du[x]++;    build(ls[x],l,mid);    build(rs[x],mid+1,r);}void upda(int x,int l,int r,int L,int R,int to){    if(L>R) return;    if(L<=l&&r<=R){        add(x,to,1);du[to]++;        return;    }    if(L<=mid) upda(ls[x],l,mid,L,R,to);    if(mid
      
       1e9) return false;    }    return true;}int main(){    rd(n);rd(s);rd(m);int x,y;    ++tot;    build(1,1,n);    for(ri i=1;i<=s;++i){        rd(x);rd(y);        val[id[x]]=y;    }    int l,r,k;    int las=0;//cout<
       
        <
       
      
     

总结：

看到区间，线段树优化建图。

topo可以找答案。所以要判环判断无解。