「解题报告」[luoguP6592]幼儿园 (DP)

传送门

题面

题意

给定一个 \(n\) 个点, \(m\) 条边的带权有向图.

每条边的边权是唯一的, 且第 \(i\) 条边的边权为 \(i\).

\(k\) 个形如 \((x,l,r)\) 的询问, 回答是否存在一条从 \(x\) 到 \(1\) 的路径, 满足路径上的边权 \(w\) 大于等于 \(l\) 小于等于 \(r\) 且路径上的边权递减.

强制在线.

数据范围

\(1 \le n \le 10^5,\ 1 \le m \le 2 \times 10^5,\ 0 \le k \le 2\times 10^5,\ 1\le l,r \le m\).

思路

为了方便描述, 把图反向, 点 \(x\) 到 \(1\) 的单调递减路径 就转变为 点 \(1\) 到 \(x\) 的单调递增路径.

对于到点 \(x\) 的一条路径 \([l,r]\) , 若存在另一条路径 \([l‘,r]\) , 满足 \(l‘ > l\) , 那么路径 \([l,r]\) 就没有存在的意义了.

因为路径上的边权是单调递增的, 所以如果我们按边权从小到大枚举每一条边, 一条合法路径上的边一定会被顺序枚举到.

考虑 \(DP\) , 设 \(d[x]\) 为从点 \(1\) 到点 \(x\) 路径上最小边 \(l\) 的最大值. 按边权从小到大枚举每条边 \((u,v)\) , 用 \(d[u]\) 更新 \(d[v]\) (若 \(u=1\) , 则 \(d[v]\) 为该边的边权) , 并把路径 \([d[v],len(u,v)]\) 加入点 \(v\) 的备选路径中.

这样的话, 对于每一个 \(len(u,v)\) , 它都仅会与一个最大的 \(l\) 组成路径, 并且每个 \((u,v)\) 都只会使路径数 \(+1\), 总路径数便为 \(m\).

最后询问点 \(x\) 的时候, 在点 \(x\) 的备选路径中二分查找一下就行了.

代码

#include<bits/stdc++.h>
#define pii pair<int,int>
#define sz(x) (int)(x).size()
#define pb push_back
#define mkp make_pair
using namespace std;
const int _=1e5+7;
int n,m,Q,ty,d[_];
vector<pii> pth[_];
int main(){
#ifndef ONLINE_JUDGE
    freopen("x.in","r",stdin);
#endif
    cin>>n>>m>>Q>>ty;
    int x,y;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&y,&x);
        if(x==1) d[y]=i;
        else d[y]=max(d[y],d[x]);
        if(d[y]) pth[y].pb(mkp(d[y],i));
    }
    for(int i=1;i<=n;i++)
	for(int j=sz(pth[i])-2;j>=0;j--)
	    pth[i][j].second=min(pth[i][j].second,pth[i][j+1].second);
    int l,r,L=0; bool ans;
    while(Q--){
        scanf("%d%d%d",&x,&l,&r);
        if(ty) x^=L,l^=L,r^=L;
        if(x==1) ans=1;
        else{
            int p=lower_bound(pth[x].begin(),pth[x].end(),mkp(l,0))-pth[x].begin();
            if(p==sz(pth[x])) ans=0;
            else ans=(pth[x][p].second<=r);
        }
        L+=ans;
        printf("%d\n",ans);
    }
    return 0;
}

「解题报告」[luoguP6592]幼儿园 (DP)

原文：https://www.cnblogs.com/BruceW/p/13149530.html