luoguP3588

luoguP3588

题意

有一个\(n\)个数的序列，已知其中的\(k\)个数，然后有\(m\)个信息，每个信息给出区间\([l,r]\)，和\(k\)个数，表示区间\([l,r]\)中这\(k\)个数大于剩下的\(r-l+1-k\)个数，求出一个方案。

分析

• 抄做的第一题线段树优化建图的题目，很巧妙。
• 大小关系我们可以看成是一条有向边，由小数连向大数，而两数之差就是边权，最后跑一遍拓扑排序，从最小的值更新，判断是否有环或者数值超过范围即可。
• 对于每一个信息，如果将大的数和小的数暴力两两连边，显然不行。
• 第一个优化是在两个数集之间加一个虚点，小数连向虚点，虚点连向大数，就相当于两两连边了，不过这样还是不够。
• 第二个优化就是用线段树来优化建图，因为给定的\(k\)个数其实是将区间\([l,r]\)分成\(k+1\)个小区间，这些小数集合，其实并不需要一一连边，只需要整个区间连向虚点即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define ls i<<1
#define rs i<<1|1
#define mid (l+r)/2
const int N=5e5+50;
const int INF=1e9;
struct Edge{int v,w,next;
}e[N*10];
int cnt,head[N],ind[N];
int n,s,m,l,r,k,x,a[N];
void init(){cnt=0;memset(head,-1,sizeof(head));
}
void add(int u,int v,int w){e[cnt]=Edge{v,w,head[u]};head[u]=cnt++;ind[v]++;
}
//记录每个线段树节点的实际编号(图论中的节点)
int pt[N],tot;
void build(int i,int l,int r){if(l==r){pt[i]=l;return;}pt[i]=++tot;build(ls,l,mid);build(rs,mid+1,r);add(pt[ls],pt[i],0);add(pt[rs],pt[i],0);
}
//线段树区间[ql,qr]对应的节点连向x(图)
void link(int i,int l,int r,int ql,int qr,int x){if(ql<=l && qr>=r){add(pt[i],x,0);return;}if(ql<=mid){link(ls,l,mid,ql,qr,x);}if(qr>mid){link(rs,mid+1,r,ql,qr,x);}
}
int ans[N],vis[N];
bool topo(){queue<int> q;int c=0;for(int i=1;i<=tot;i++){if(!ind[i]){q.push(i);}if(!ans[i]){//还不确定的数ans[i]=1;}}while(!q.empty()){int u=q.front();q.pop();c++;for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].v;int w=e[i].w;ans[v]=max(ans[v],ans[u]+w);if(a[v] && ans[v]>a[v]){return false;}--ind[v];if(!ind[v]){q.push(v);}}}return c==tot;
}
int main(){
//    freopen("in.txt","r",stdin);scanf("%d%d%d",&n,&s,&m);init();//线段树n个叶子节点1-n，然后其他父节点就++tottot=n;build(1,1,n);for(int i=1;i<=s;i++){scanf("%d%d",&k,&x);a[k]=ans[k]=x;}//对于给定的k个数也就是集合S1，都大于等于[l,r]剩下的数S2，因此需要两两连边//优化1 建立虚点，S2连向虚点，虚点连向S1//优化2 S2都是一些连续区间，可以用线段树来优化建图，让线段树区间连向虚点for(int i=1;i<=m;i++){scanf("%d%d%d",&l,&r,&k);tot++;int p=l-1;//k个数将区间分为k+1段，对应的线段树区间分别连向虚点for(int j=1;j<=k;j++){scanf("%d",&x);//虚点连向S1add(tot,x,1);//连续区间连向虚点if(x>p+1){//和上一个点之间有一段连续区间link(1,1,n,p+1,x-1,tot);}p=x;}if(x<r){link(1,1,n,x+1,r,tot);}}//拓扑排序求出方案bool flag=topo();if(!flag){printf("NIE\n");return 0;}for(int i=1;i<=n;i++){if(ans[i]>INF){printf("NIE\n");return 0;}}printf("TAK\n");for(int i=1;i<=n;i++){printf("%d%c",ans[i],i==n?'\n':' ');}return 0;
}

转载于:.html