「解题报告」[JSOI2019] 精准预测 (2-SAT)

传送门

题面

题意

有 (T) 个时刻, (n) 个居民, (m) 条预言 ((ty,t,x,y)), 含义为 :

(ty==0), 在 (t) 时刻, 若 (x) 是死亡状态, 则在 (t+1) 时刻, (y) 是死亡状态.
(ty==1), 在 (t) 时刻, 若 (x) 是生存状态, 则在 (t) 时刻, (y) 是死亡状态.

每一时刻都可能有居民死去, 有些居民会在 (0) 时刻死去. (由你决定)

对每一个居民求出, 有多少个除了他本身的居民有可能和他一起活到 (T+1) 时刻.

数据范围

(T le 10^6, nle 5 imes10^4,m le 10^5.)

思路

(bool) 变量 + 限制条件, 看到这两个元素在一起第一反应就应该是 (2-SAT).

但毕竟不是板子题, 还是需要一些特殊处理.

让我们分步骤来吧.

建点 & 连边

显然, 我需要把每一个居民拆成代表若干个时刻的点, 如果直接拆成 (T) 个点的话显然会炸, 那么对于点 (u), 对于每一条预言 ((ty,t,u,v)), 我们都新建一个时刻为 (t) 的点. 全部预言都处理完后, 再对每个点建一个时刻为 (T+1) 的点, 表示它最终的生死状态.

然后对于每条预言 ((ty,t,u,v)), 我们不需要对 (v) 建一个时刻为 (t) (或 (t+1)) 的点, 只需要在 (v) 的所有时刻的点中找出第一个时刻 (ge t) (或 (>t)) 的点, 并进行连边.

除此之外, 对于每个点 (u), 我们还需要在它表示死亡状态的点中, 按照时刻从小到大往后连边; 在它表示死亡状态的点中, 按照时刻从大到小往前连边.

这样, 点数就是 (2n+2m le 3 imes 10^5), 边数为 (2m+2m le 4 imes 10^5.)

统计答案

把图建出来后, 再考虑如何计算答案.

与一般的 (2-SAT) 板子不同, 这题不是要求我们判断是否有可行方案或输出一个可行方案, 所以我们就不能直接套 (Tarjan).

考虑如何计算答案.

设 (d'_u,l'_u) 分别表示点 (u) 在时刻 (T+1) 时表示死亡状态和生存状态的点.

对于点 (u), 设 (num_u=sum_{vin V and v ot= u} [path(l'_u,d'_v)]), 其中 ([path(x,y)]=1) 表示存在一条由 (x) 到 (y) 的路径. 则 (ans_u=n-1-num_u.)

特别地, 对于 ([path(l'_u,d'_u)]=1) 的点 (u), (ans_u=0), 并且会使得总体答案 (-1.)

假设我们建出来的图是一个 (DAG) (有向无环图), 那么我们可以用 ( m bitset) 辅助 (DP), 计算出每个点 (u) 的 (num_u), 总时间复杂度为 (Oleft(frac{n(2n+2m)}{w} ight) (w=32)), 约为 (5 imes10^8).

由于内存限制, ( m bitset) 不能直接开到 (n), 所以我们需要分次进行 (DP). 虽然看起来 ( m bitset) 的大小和时间复杂度没什么关系, 但为了避免 (DP) 初始化,赋值等操作带来的常数, 还是尽量越大越好.上面讨论的是 (DAG) 的情况, 而实际上, 我们可以直接证明我们建出来的这张图就是一个 (DAG).

证明原图是一个 (DAG)

我们考虑把所有点分为 (d) (死亡状态), (l) (生存状态), 然后分类证明.

为了方便描述, 我们规定

(x ightarrow y) 表示存在一条从 (x) 到 (y) 的路径, 且 (x) 所代表的时刻小于 (y) 所代表的时刻.
(y leftarrow x) 表示存在一条从 (x) 到 (y) 的路径, 且 (x) 所代表的时刻大于 (y) 所代表的时刻.
(x Rightarrow y) 表示存在一条从 (x) 到 (y) 的路径, 且 (x) 所代表的时刻小于等于 (y) 所代表的时刻.
(y Leftarrow x) 表示存在一条从 (x) 到 (y) 的路径, 且 (x) 所代表的时刻大于等于 (y) 所代表的时刻.

按照上文所述的连边方法, 会存在以下这几种边.

(d ightarrow d)
(l leftarrow l)
(l Rightarrow d)
(d Leftarrow l)

首先考虑 (d). 由于不存在从 (d) 出发到 (l) 的边, 所以若存在一个从 (d) 到 (d) 的环, 则环上的点一定都是 (d). 又因为 (d) 只能连向时刻比它大的 (d), 所以不可能连回自己. 故不存在一个以 (d) 为起点, (d) 为终点的环.

再来考虑 (l). 同样, 由于不存在从 (d) 出发到 (l) 的边, 所以若存在一个从 (l) 到 (l) 的环, 则环上的点一定都是 (l), 又因为 (l) 只能连向时刻比它小的 (l), 所以不可能连回自己. 故不存在一个一 (l) 为起点, (l) 为终点的环.

故, 原图上不存在环. 即证明了原图是一个 (DAG).

那么, 我们就可以按照上述的方法计算出 (num_u) 从而计算出 (ans_u) 了.

没了

还有一些小细节, 比如为了避免 ([path(l'_u,d'_u)=1) 的点的影响, 需要做两遍 (DP) (本人只想到这种方法), 还有连边时不要把 (t) 的关系弄混了.

还有, 这道题需要疯狂卡常, 我这份代码卡到最后也只能随缘过...

赠送(@GreenDay的)卡常火车头

代码

#pragma GCC optimize(3) // 手动开了个 O3 优化
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define sz(x) (int)(x).size()
#define mkp make_pair
#define fi first
#define se second
#define lb lower_bound

const int _=5e5+7;
const int X=12500;

bool be;
int n,m,T;
int de[_],tms[_],bel[_],np,num[_],p[_];
int lst[_],nxt[_],to[_],tot;
bool mst[_];
bitset<X+7> f[_];
queue<int> q;
vector<pair<int,int> > ve[_];
struct edge{
	int p,t,u,v;
#define p(i) e[i].p
#define t(i) e[i].t
#define u(i) e[i].u
#define v(i) e[i].v
}e[_];
bool en;

bool cmp(edge a,edge b){ return a.t<b.t; }

void add(int x,int y){
	nxt[++tot]=lst[y]; to[tot]=x; lst[y]=tot; de[x]++;            // 建反向边
}

void _init(){
	cin>>T>>n>>m;
	for(int i=1;i<=m;i++) cin>>p(i)>>t(i)>>u(i)>>v(i);
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=m;i++){
		int u=u(i),t=t(i),sz=sz(ve[u]);
		if(!sz||ve[u][sz-1].fi!=t) ve[u].pb(mkp(t,++np)),++np;
	}
	for(int i=1;i<=n;i++){
		ve[i].pb(mkp(T+1,++np)); ++np;
		bel[np]=bel[np-1]=i;
		p[i]=np;
		for(int j=0;j<sz(ve[i])-1;j++){
			add(ve[i][j].se,ve[i][j+1].se);
			add(ve[i][j+1].se+1,ve[i][j].se+1);
		}
	}
	for(int i=1;i<=m;i++){
		int u=u(i),v=v(i),t=t(i);
		pair<int,int> tmp=mkp(t,0);
		int t1=lb(ve[u].begin(),ve[u].end(),tmp)-ve[u].begin(),t2=lb(ve[v].begin(),ve[v].end(),tmp)-ve[v].begin();
		if(!p(i)&&ve[v][t2].fi==t) t2++;
		if(p(i)) add(ve[u][t1].se+1,ve[v][t2].se),add(ve[v][t2].se+1,ve[u][t1].se);
		else add(ve[u][t1].se,ve[v][t2].se),add(ve[v][t2].se+1,ve[u][t1].se+1);
	}
}

void _dp(int L,int R){
	for(int i=1;i<=np;i++){
		f[i].reset(); tms[i]=0;
		if(!de[i]) q.push(i);
	}
	while(!q.empty()){
		int u=q.front(); q.pop();
		if(u%2&&!mst[bel[u]]&&bel[u]>=L&&bel[u]<=R) f[u][bel[u]-L]=1;
		for(int i=lst[u];i;i=nxt[i]){
			int v=to[i];
			f[v]|=f[u];
			tms[v]++;
			if(tms[v]==de[v]){ q.push(v); tms[v]++; }
		}
	}
}

void _run(){
	int ls=0;
	for(int i=1;i<=n;i+=X){
		_dp(i,i+X-1);
		for(int j=i;j<=min(n,i+X-1);j++)
			if(f[p[j]][j-i]) mst[j]=1,ls++;
	}
    
	for(int i=1;i<=n;i+=X){
		_dp(i,i+X-1);
		for(int j=1;j<=n;j++) num[j]-=f[p[j]].count();
	}

	for(int i=1;i<=n;i++)
		if(mst[i]) cout<<0<<' ';
		else cout<<n-1+num[i]-ls<<' ';
    
	cout<<endl;
}
int main(){
#ifndef ONLINE_JUDGE
	freopen("9.in","r",stdin);
	freopen("x.out","w",stdout);
#endif
	ios::sync_with_stdio(false);
	clock_t st=clock();
	_init();
	st=clock();
	_run();
	cerr<<(double)(clock()-st)/CLOCKS_PER_SEC<<endl;
	cerr<<(double)1.0*(&en-&be)/(1<<20)<<endl;
	return 0;
}