YsOI2020 幼儿园 思维

(Updated: )
(6 mins to read)

题意

给定有向图，n个点m条边，每条边有权值i，且恰好是1-m的一个排列，多次询问从x点只走$[l,r]$的边，且边权严格单调下降能否到达1号点，强制在线

做法

限制了边权的范围$[l, r]$，我们可以先考虑$[1,r]$的时候怎么做，考虑dp[u]表示u号点与1连通需要的最小边权，从小到大枚举每一条边，如果该点与1相连，则dp[u]=w，否则如果dp[v]有值，则dp[u]=i，然后只要看dp[u]是不是小于r即可加入下界限制后，将dp[u]转化为与1连通时需要经过的最小边权最大是多少，如果该点与1相连，则dp[u]=i，否则dp[u]=max(dp[u],dp[v])，随着从小到大枚举边权dp，dp[u]是不断变大的，考虑按照枚举顺序建立主席树，每次单点更新u点的值，询问只要查询rt[r]版本的主席树中x点的值是否>=l即可。相当于每个点处有很多单调递增的二维点（x坐标为边权，y坐标为dp），我们对每个点用vector存这些点，那么只要看x<=r的最后一个点的y是否>=l。

思考

严格单调下降的限制只要通过从小到大的顺序dp即可解决，对于既有上界又有下界的限制，考虑枚举上界，然后最大化下界即可

主席树写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e5 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int n, m, k, w, dp[N];
pii edges[N];
namespace PSegTree
{
  #define ls(x) t[x].l
  #define rs(x) t[x].r
  int rt[N], tot;
  struct node
  {
    int l, r, mx;
  }t[N<<5];
  inline void newnode(int &p)
  {
    t[++tot] = t[p];
    p = tot;
  }
  void upd(int &p, int l, int r, int x, int v)
  {
    newnode(p);
    if(l==r)
    {
      t[p].mx = max(t[p].mx, v);
      return;
    }
    int mid = (l+r) >> 1;
    if(x<=mid) upd(ls(p), l, mid, x, v);
    else upd(rs(p), mid+1, r, x, v);
    t[p].mx = max(t[ls(p)].mx, t[rs(p)].mx);
  }
  int ask(int p, int l, int r, int x)
  {
    if(l==r) return t[p].mx;
    int mid = (l+r) >> 1;
    if(x<=mid) return ask(ls(p), l, mid, x);
    else return ask(rs(p), mid+1, r, x);
  }
  #undef ls
  #undef rs
}
using namespace PSegTree;
int main()
{
  scanf("%d%d%d%d", &n, &m, &k, &w);
  for(int i=1; i<=m; i++) scanf("%d%d", &edges[i].fi, &edges[i].se);
  for(int i=1; i<=m; i++)
  {
    int u = edges[i].fi, v = edges[i].se;
    if(v==1) dp[u] = i;
    else dp[u] = max(dp[u], dp[v]);
    rt[i] = rt[i-1];
    upd(rt[i], 1, m, u, dp[u]);
  }
  int L = 0;
  for(int i=1; i<=k; i++)
  {
    int x, l, r;
    scanf("%d%d%d", &x, &l, &r);
    if(w) x ^= L, l ^= L, r ^= L;
    if(x==1||ask(rt[r], 1, m, x)>=l) ++L, puts("1");
    else puts("0");
  }
  return 0;
}