Description

题库链接

有 \(n\) 个房间排成一列，编号为 \(1,2,...,n\) ，相邻的房间之间都有一道门。其中 \(m\) 个门上锁，其余的门都能直接打开。现在已知每把锁的钥匙在哪个房间里（每把锁有且只有一把钥匙与之对应）。

现给出 \(p\) 个询问：询问从房间 \(S\) 出发是否能到达房间 \(T\) 。

\(1\le n,p\le 10^6\) ， \(0\le m <n\) 。

Solution

推推性质，显然对于每个起点，它能到达的区域一定是一个完整的区间。

\(O(n^2)\) 比较容易搞的，稍微转化一下，把一些约束关系建成图，将与钥匙同侧的房间连边到钥匙所在的房间，钥匙所在的房间连边到异侧的房间。

显然图是具有层次性的，那我可以把最底层的暴力跑出来，逐步上推，每一次都可以利用下一层的信息。

似乎能做到 \(O(n)\) 。考场上想到可能这样的约束关系可能成环（似乎不会），于是还打了个 \(tarjan\) 。因为成环的话，同一个环内的点的“层次”是相同的。

Code

#include <bits/stdc++.h>

#define pb push_back

#define Min(a, b) ((a) < (b) ? (a) : (b))

#define Max(a, b) ((a) > (b) ? (a) : (b))

using namespace std;

const int N = 1e6+5;

int read() {

  int sum = 0; char ch = getchar();

  while (ch < '0' || ch > '9') ch = getchar();

  while (ch >= '0' && ch <= '9') sum = (sum<<1)+(sum<<3)+ch-'0', ch = getchar();

  return sum;

}

int n, m, p, d[N], l[N], r[N], q[N], head, tail, in[N];

int dfn[N], low[N], times, S[N], vis[N], sccno[N], sccnum;

vector<int>to[N], scc[N];

struct tt {int to, next; }edge[N<<1];

int path[N], top;

void tarjan(int u) {

  low[u] = dfn[u] = ++times; S[++top] = u, vis[u] = 1;

  for (int i = path[u]; i; i = edge[i].next) {

    int v = edge[i].to;

    if (!dfn[v]) {

      tarjan(v); low[u] = min(low[u], low[v]);

    }else if (vis[v]) low[u] = min(low[u], dfn[v]);

  }

  if (dfn[u] == low[u]) {

    ++sccnum; int v = 0;

    do {

      v = S[top--]; scc[sccnum].pb(v);

      sccno[v] = sccnum; vis[v] = 0;

    }while(u != v);

  }

}

void topsort() {

  for (int i = 1; i <= sccnum; i++) {if (!in[i]) q[tail++] = i; }

  while (head < tail) {

    int u = q[head++];

    for (int i = 0, sz = to[u].size(); i < sz; i++) {

      int v = to[u][i];

      --in[v]; if (!in[v]) q[tail++] = v;

    }

  }

}

void solve(int x) {

  int L = x, R = x;

  while (true) {

    if (R != n && (d[R] >= L && d[R] <= R || d[R] == 0)) {++R, L = Min(L, l[R]), R = Max(R, r[R]); continue; }

    if (L != 1 && (d[L-1] >= L && d[L-1] <= R || d[L-1] == 0)) {--L; L = Min(L, l[L]), R = Max(R, r[L]); continue; }

    break;

  }

  l[x] = L, r[x] = R;

}

void add(int u, int v) {edge[++top].to = v, edge[top].next = path[u]; path[u] = top; }

void work() {

  n = read(), m = read(), p = read();

  for (int i = 1, x, y; i <= m; i++) {

    x = read(), y = read(); d[x] = y;

    if (y <= x) {

      if (x != y) add(x, y);

      add(y, x+1);

    }else {

      if (x+1 != y) add(x+1, y);

      add(y, x);

    }

  }

  top = 0;

  for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);

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

    for (int i = path[u]; i; i = edge[i].next)

      if (sccno[u] != sccno[edge[i].to])

    to[sccno[u]].pb(sccno[edge[i].to]), ++in[sccno[edge[i].to]];

  topsort();

  for (int i = 1; i <= n; i++) l[i] = n+1;

  for (int i = sccnum-1; i >= 0; i--) {

    int u = q[i];

    for (int i = 0, sz = scc[u].size(); i < sz; i++)

      solve(scc[u][i]);

  }

  int s, t;

  while (p--) {

    s = read(), t = read();

    if (l[s] <= t && r[s] >= t) puts("YES");

    else puts("NO");

  }

}

int main() {work(); return 0; }