题目概述

HDU7171

解题报告

题目保证了DAG，所以是个DAG上的传递闭包问题，考虑用bitset做。

定义 $f_{i,j}$ 表示是否能通过 $j$ 询问中的 $[l_i,r_i]$ 边从 $u_j$ 走到 $i$ 点，用bitset记录。

然后做拓扑，对于 $i$ 号边 $x_i\to y_i$ ，则 $f_{y_i}=f_{y_i}\cup(f_{x_i}\cap S_i)$ ，其中 $S_i$ 表示包含 $i$ 号边的询问集合，可以通过扫描线处理。

由于 $m$ 比较大恭喜我们成功炸空间了，类似这题，我们想办法把空间除掉个常数，因此我们每隔 $4$ 个扫描线中的点才记录一次bitset，然后查询时再花 $4$ 次补全 $S_i$ ，这样就不会炸空间了。

示例程序

#include<cstdio>
#include<cctype>
#include<bitset>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=50000,maxm=100000,maxq=50000,maxs=maxq<<1;

int te,n,m,Q,X[maxm+5],Y[maxm+5];
int U[maxq+5],V[maxq+5],L[maxq+5],R[maxq+5];
int E,D[maxn+5],lnk[maxn+5],nxt[maxm+5],ID[maxm+5],to[maxm+5];
int cnt;pair<int,int> s[maxs+5];
int que[maxn+5];
bitset<maxq> S[(maxs>>2)+5],f[maxn+5],now;

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
inline void Add(int x,int y,int z) {to[++E]=y;ID[E]=z;nxt[E]=lnk[x];lnk[x]=E;}
int Find(int x){
    int L=0,R=cnt-1;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        s[mid].fr<=x?L=mid+1:R=mid-1;
    return R;
}
int main(){
    for (readi(te);te;te--){
        readi(n);readi(m);readi(Q);
        E=0;for (int i=1;i<=n;i++) lnk[i]=D[i]=0,f[i]=0;
        for (int i=1,x,y;i<=m;i++) readi(X[i]),readi(Y[i]),Add(X[i],Y[i],i),D[Y[i]]++;
        cnt=0;
        for (int i=0;i<Q;i++){
            readi(U[i]);readi(V[i]);readi(L[i]);readi(R[i]);
            s[cnt++]=mp(L[i],i);if (R[i]<m) s[cnt++]=mp(R[i]+1,i);
            f[U[i]][i]=1;
        }
        sort(s,s+cnt);
        S[0]=0;
        for (int i=0;i<cnt;i++){
            if (!(i&3)) S[(i>>2)+1]=S[i>>2];
            S[(i>>2)+1].flip(s[i].sc);
        }
        int Head=0,Tail=0;
        for (int i=1;i<=n;i++) if (!D[i]) que[++Tail]=i;
        while (Head!=Tail)
            for (int x=que[++Head],j=lnk[x];j;j=nxt[j]){
                int pos=ID[j],k=Find(pos);
                now=S[k>>2];for (int i=(k>>2)<<2;i<=k;i++) now.flip(s[i].sc);
                f[to[j]]|=f[x]&now;
                if (!(--D[to[j]])) que[++Tail]=to[j];
            }
        for (int i=0;i<Q;i++) puts(f[V[i]][i]?"YES":"NO");
    }
    return 0;
}