[JSOI2019]精准预测（2-SAT+拓扑排序+bitset）

设第i个人在t时刻生/死为(x,0/1,t)，然后显然能够连上(x,0,t)->(x,0,t-1)，(x,1,t)->(x,1,t+1)，然后对于每个限制，用朴素的2-SAT连边即可。

但这样的点数达到了O(nT)，其实有一种方法可以只把限制的边连接建图，点数为4m，这样可能会被卡常。

有没有更优秀的做法？当然还是有的。对于2-SAT中的边(x,y)，若y在2-SAT中无出边，则x->y与x->y的后继等价，于是点数可以控制在2n+2m。然后很容易发现，生、死状态的图均为拓扑图，而只有生->死的边没有死->生的边，所以原图是拓扑图所以我们的问题变成了对于每一个(x,0,T+1)求出它能够到达的所有(y,1,T+1)的状态数。于是可以topsort+bitset优化，为了能不爆内存，可以分批topsort，每次10⁴个点左右是最好的。

#include<bits/stdc++.h>

using namespace std;

const int N=5e4+,M=3e5+;

struct node{int tp,t,x,y;};

int T,n,m,sum[N],ans[N],in[M],q[M],vis[N];

bitset<>tmp,b[M];

vector<int>G[M],vec[N];

vector<node>now;

void topsort(int L,int R)

{

    int qs=,qe=;

    for(int i=;i<=*sum[n];i++)for(int j=;j<G[i].size();j++)in[G[i][j]]++;

    for(int i=;i<=*sum[n];i++)if(!in[i])q[qe++]=i;

    while(qs<qe)

    {

        int u=q[qs++];

        for(int i=;i<G[u].size();i++)

        {

            b[G[u][i]]|=b[u];

            if(!--in[G[u][i]])q[qe++]=G[u][i];

        }

    }

    tmp.reset();

    for(int i=L;i<=R;i++)if(b[sum[i]][i-L])vis[i]=,tmp.set(i-L);

    for(int i=;i<=n;i++)if(!vis[i])ans[i]+=(b[sum[i]]|tmp).count();

}

int main()

{

    scanf("%d%d%d",&T,&n,&m);

    for(int i=;i<=m;i++)

    {

        node u;scanf("%d%d%d%d",&u.tp,&u.t,&u.x,&u.y),u.tp^=;

        now.push_back(u),vec[u.x].push_back(u.t);

    }

    for(int i=;i<=n;i++)

    {

        sort(vec[i].begin(),vec[i].end());

        vec[i].push_back(T+);

        int t=unique(vec[i].begin(),vec[i].end())-vec[i].begin();

        sum[i]=sum[i-]+t,vec[i].resize(t);

    }

    for(int i=;i<now.size();i++)

    {

        int x=now[i].x,y=now[i].y,t=now[i].t;

        int p=lower_bound(vec[x].begin(),vec[x].end(),t)-vec[x].begin()+sum[x-]+;

        int q=lower_bound(vec[y].begin(),vec[y].end(),now[i].tp+t)-vec[y].begin()+sum[y-]+;

        if(now[i].tp)G[q+sum[n]].push_back(p+sum[n]),G[p].push_back(q);

        else G[q+sum[n]].push_back(p),G[p+sum[n]].push_back(q);

    }

    for(int u=;u<=n;u++)

    for(int i=sum[u-]+;i<sum[u];i++)

    G[i].push_back(i+),G[i++sum[n]].push_back(i+sum[n]);

    for(int i=;i<=n;i+=)

    {

        for(int j=;j<=*sum[n];j++)b[j].reset();

        for(int j=;i+j<=n&&j<;j++)b[sum[i+j]+sum[n]].set(j);

        topsort(i,min(n,i+));

    }

    for(int i=;i<=n;i++)printf("%d ",vis[i]?:n-ans[i]-);

}

[JSOI2019]精准预测（2-SAT+拓扑排序+bitset）的相关教程结束。