【2021集训队出题】序列

【2021集训队出题】序列

by AmanoKumiko

Description

有一个长度为\(n\)的序列\(a\)，其中\(a_i∈[1,10^9]\)

给出\(m\)个限制，每次给出\(i,j,k,x\)，你需要满足\(a_i,a_j,a_k\)中的中位数为\(x\)

给出一组合法解

Input

第一行两个数\(n,m\)

接下来\(m\)行，读入限制

Output

若有解，第一行输出\(YES\)，然后输出\(n\)个整数表示\(a\)

反之输出\(NO\)

Sample Input

6 4
1 3 4 2
1 2 5 6
3 6 6 7
2 4 5 3

Sample Output

YES
6 8 2 2 3 7

Data Constraint

\(1\le n,m\le 10^5,1\le i,j,k\le n,1\le x\le 10^9\)

Solution

尝试用\(2-SAT\)解决问题

我们设一个变量\(X(i,j)\)，若为\(1\)，表示\(a_i\ge j\)，若为\(0\)，表示\(a_i

那么每次给出限制，我们只需要形如\(X(i,x)=0\)向\(X(j,x)=1\)连，\(X(i,x)=0\)向\(X(k,x)=1\)连

但是这样的话点特别多，考虑优化

显然，\(a\)中的值只可能是题目给出的\(x\)，若不是，则可以调整

那么我们对每个\(i\)建出它的可能的数的集合，然后拿个\(set\)处理一下就好了

Code

#include
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define N 100010
#define S 1000010

#include 
#include 
using namespace __gnu_pbds;
cc_hash_tablenum[N][2];

sets[N];
set::iterator it;
int n,m,nt,ans[N];
int low[S],dfn[S],cnt,tot,last[S],scc[S],in[S],st[S],top,col;
struct edge{int en,next;}e[S*10];
struct node{int i,j,k,x,kind;}ask[N];

void add(int x,int y){e[++tot]=(edge){y,last[x]};last[x]=tot;}

void Tarjan(int x){
	dfn[x]=low[x]=++cnt;st[++top]=x;in[x]=1;
	for(int i=last[x];i;i=e[i].next){
		int y=e[i].en;
		if(!dfn[y])Tarjan(y),low[x]=min(low[x],low[y]);
		else if(in[y])low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x]){
		col++;
		while(st[top]!=x)in[st[top]]=0,scc[st[top--]]=col;
		in[st[top]]=0;scc[st[top--]]=col;
	}
}

int main(){
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	scanf("%d%d",&n,&m);
	F(i,1,n)s[i].insert(1),s[i].insert(1000000000);
	F(i,1,m){
		scanf("%d%d%d%d",&ask[i].i,&ask[i].j,&ask[i].k,&ask[i].x);
		if(ask[i].i==ask[i].j&&ask[i].j==ask[i].k)ask[i].kind=1;
		else if(ask[i].i==ask[i].j||ask[i].j==ask[i].k||ask[i].i==ask[i].k)ask[i].kind=2;
		else ask[i].kind=3;
		s[ask[i].i].insert(ask[i].x);
		s[ask[i].j].insert(ask[i].x);
		s[ask[i].k].insert(ask[i].x);
	}
	F(i,1,n){
		int lnt=nt;
		for(it=s[i].begin();it!=s[i].end();it++)num[i][0][*it]=++nt,num[i][1][*it]=++nt;
		for(int j=lnt+1;j