Posted in: 未分类

「QOJ2342」鸭性统计 duck

首先,聪明的你应该把$duck$反过来读:就是“可达”。

所以这道题就是“可达性统计”的模板题。

只不过,这道题把数据加强到了 $10^5$,并且本题中的图可能存在环。

就是这两个问题,我们一个一个来处理。

对于图中存在环的问题,我们只需要 $\texttt{tarjan}$一下,缩点染色一下就行了,因为在一个环内的两个点肯定两两互相可达,我们把他染成一个颜色并没有问题,其他的操作正常进行,$\texttt{tarjan}$ 缩点肯定大家都会。

接着,我们要对付 $10^5$ 的数据。

对于简单版的可达性统计,我们是建了 bitset<1005> b[1005]b[x][y] 代表的是否能从 $x$ 点到达 $y$ 点,我们用 $\texttt{bitset}$,是为了把第二维压成一个 01 串,从而降低空间。但是对于 $10^5$ 的数据我们把 $\texttt{bitset}$ 建出来:bitset<100005> b[100005]。算一下,上了 $1000\texttt{MiB}$,肯定不可取。

那怎么办呢?

这里就要用到一个很常用的,很重要的技巧:牺牲时间复杂度来补救空间复杂度!
因为我们发现,时间复杂度太优秀了,空间复杂度太菜了。于是我们想到一个类似分块的思想来解决这个问题。
我们可以把 $Q$ 次询问分成 $k$ 段,每一段长为 $len$,然后一段一段地解决,一段一段地处理,我们将每一段询问中 $(u,v)$ 的 $v$ 做一个离散化操作,使得 $\texttt{bitset}$ 的第二维空间降下来,因为这一段最后真正有用的就这 $len$ 个点能否到达,至于其他点能否到达我们不在乎,将它们都看作编号为 0 即可。每一段询问都进行同样的操作,就可以通过本题。其实这样的方法也不叫分块,它就是把一个问题分成了几段,依次处理。

当然,在保证空间复杂度的前提下,$k$ 越小越好。

$code:$

#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<bitset>
#define reg register
using namespace std;
const int maxn=2e5+5;
const int mod=1e9+7;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')
        f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int n,m,Q;
int wugui=0;
int head1[maxn];
struct node
{
    int to;
    int nxt;
}edge[maxn];
void add(int x,int y)
{
    wugui++;
    edge[wugui].to=y;
    edge[wugui].nxt=head1[x];
    head1[x]=wugui;
}
int in[maxn];
queue<int> q;
vector<int> v[maxn];
int low[maxn];
int dfn[maxn];
int cnt=0;
int s[maxn];
int col[maxn];
int color=0;
int vis[maxn];
int index1=0;
struct Query
{
    int x,y;
}ask[maxn];

//tarjan

void tarjan(int x)
{
    low[x]=dfn[x]=++index1;
    vis[x]=1;   
    s[++cnt]=x;
    for(reg int i=0;i<(int)v[x].size();i++)
    {
        int t=v[x][i];
        if(dfn[t]==0)
        {
            tarjan(t);
            low[x]=min(low[x],low[t]);
        }
        else
        {
            if(vis[t]==1)
            low[x]=min(low[x],dfn[t]);
        }
    }
    if(dfn[x]==low[x])
    {
        int v;
        color++;
        do
        {
            v=s[cnt];
            cnt--;
            col[v]=color;
            vis[v]=0;
        }
        while(v!=x);
    }
}

bitset<20005> a[maxn];
int re_in[maxn];
int tot=0;
int b[maxn];
int id[maxn];
int Get(int x)
{
    return lower_bound(s+1,s+1+tot,x)-s;
}
int order[maxn];
int ORDER=0;
void Work(int l,int r)
{

    // re_sort  & Get_id

    tot=0;
    int fuck=0;
    for(reg int i=l;i<=r;i++)
        b[++fuck]=col[ask[i].y];
    sort(b+1,b+1+fuck);
    b[0]=-1e9;
    for(reg int i=1;i<=fuck;i++)
    {
        if(b[i]!=b[i-1])
        s[++tot]=b[i];
    }

    // bitset_dp & topo

    for(reg int i=1;i<=color;i++)
    {
        id[i]=Get(i);
        if(s[id[i]]!=i)
        id[i]=0;
        a[i].reset();
        if(re_in[i]==0)
        {
            q.push(i);
            int x=id[i];
            a[i][x]=1;
        }
    }
    for(reg int j=1;j<=ORDER;j++)
    {
        int point=order[j];
        int x=id[point];
        a[point][x]=1;
        for(reg int i=head1[point];i;i=edge[i].nxt)
        {
            int t=edge[i].to;
            a[t] |= a[point];
        }
    }

    // Get_ans

    for(reg int i=l;i<=r;i++)
    {
        int x=col[ask[i].x];
        int y=col[ask[i].y];
        if(a[x][id[y]])
            cout<<"Y";
        else
            cout<<"N";
    }
}
int main()
{
    //tarjan

    n=read(),m=read(),Q=read();
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        v[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0)
        tarjan(i);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<(int)v[i].size();j++)
        {
            int x=col[i];
            int y=col[v[i][j]];
            if(x==y)
                continue;       
            in[x]++;
            add(y,x);
        }
    }

    //topo_sort

    for(int i=1;i<=color;i++)
        re_in[i]=in[i];
    for(reg int i=1;i<=color;i++)
    {
        if(in[i]==0)
            q.push(i);
    }
    while(!q.empty())
    {
        int point=q.front();
        q.pop();
        order[++ORDER]=point;
        for(reg int i=head1[point];i;i=edge[i].nxt)
        {
            int t=edge[i].to;
            in[t]--;
            if(in[t]==0)
            q.push(t);
        }
    }

    // divide segments

    for(int i=1;i<=Q;i++)
        ask[i].x=read(),ask[i].y=read();
    int len=20000;
    int now=1;
    while(true)
    {
        if(now+len-1<Q)
        {
            Work(now,now+len-1); // Get_ans
            now=now+len;
        }
        else
        {
            Work(now,Q); // Get_ans
            break;
        }
    }
    return 0;
}
Back to Top