题意
有一个\(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，然后其他父节点就++tot
tot=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);
//虚点连向S1
add(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;
}