题解 P4964 【绫小路的特别考试】
ouuan
2018-11-03 23:11:24
### 〇、暴力
首先这题有一个比较好想的暴力：对于每对可以传递答案的同学连单向边，然后从每个可以独立作出的同学开始dfs。
这个暴力主要有两个问题：
1. 边数太多，最多可以达到 $O(n^2)$ 的级别。
2. 每次询问都要dfs一次。
下面将分别进行讲解：
### 一、连边
其实对于每个同学，只需要向左右两边最近的能够接收到的同学各连一条边即可。
不妨令当前同学为第 $u$ 位同学，他左边最近的能够接收到他的广播的同学为 $l_u(l_u=\max\{v|v<u,v+d_v\ge u\})$.
若存在比 $l_u$ 更远的一位同学 $p(p<l_u,p+d_p\ge u)$ 能够接收到 $u$ 的广播，那么 $p$ 一定能够接收到 $l_u$ 的广播，而 $l_u$ 又能接收到 $u$ 的广播。
所以，$u$ 向左只用连 $(u,l_u)$ 这条边即可。向右是类似的。一共只要连不到 $2n$ 条边。
~~说得好，怎么实现呢？~~
用一个栈，从左往右扫一遍，如果栈顶无法接收到当前同学的广播就弹出，若栈非空就向栈顶连边，然后将当前同学入栈。然后再从右往左扫一遍就好了。
### 二、单次dfs
> 注：这里的单次dfs不是指只dfs一次，而是指所有的dfs过程总复杂度为 $O(n)$
每次询问的时候dfs的起点都是 $w_i$ 中最大的一些，所以先对 $w_i$ 排序。
~~然后按顺序依次进行dfs就可以啦！~~
停！怎么dfs？怎么回答询问？
从大到小枚举 $x$，每次把 $w_i=x$ 的点作为起点dfs，然后记录每个询问 $x$ 的答案，就可以回答询问啦！
~~你当这题没有修改吗？？？~~
事实上，修改造成的影响只有 $w_c<x$，$w_c\ge x$ 两种，所以分两种情况，$ans[0][x]$ 表示 $w_c<x$ 时询问 $x$ 的答案，$ans[1][x]$ 表示 $w_c\ge x$ 时询问 $x$ 的答案。计算 $ans[0][x]$ 时跳过 $c$，计算 $ans[1][x]$ 时先以 $c$ 为起点dfs再dfs其它点。
总复杂度：$O(n+q)$
~~等等？排序呢？？？~~
$0\le w_i<n$，所以可以用各种 $O(n)$ 排序算法，比如计数排序。
值得注意的是，vector/前向星常数可能较大。由于每个点最多只连两条边，可以用两个数组分别存向左/向右的边。同时最好不要用vector/前向星来作为桶排序的容器。
当然，~~ctr非常良心~~，实测前向星存图+前向星桶排~~只需~~$2.7s$，是可过的。两个数组存图+`std::sort`也只需 $1.8s$。
### 参考代码：
```cpp
#include <cstdio>
#include <cstring>
const int N=2000010;
void dfs(int u);
unsigned long long seed;
int n, m, c, mfq, mind, maxd, k, w[2000001], d[2000001];
int sta[N],top,tot,ans[2][N],l[N],r[N],ord[N],cnt[N];
bool vis[N];
inline int randInt() { seed = 99999989 * seed + 1000000007; return seed >> 33; }
void generate()
{
for (int i = 1; i <= n; i++) { w[i] = randInt() % n; }
for (int i = 1; i <= n; i++) { d[i] = randInt() % (maxd - mind + 1) + mind; }
}
void getOperation(int lastans, int &opt, int &x)
{
if ((0ll + randInt() + lastans) % mfq) { opt = 1; } else { opt = 2; }
x = (0ll + randInt() + lastans) % n;
}
int main()
{
int i,j,lxl;
scanf("%d %d %d", &n, &m, &c);
scanf("%llu %d %d %d %d", &seed, &mind, &maxd, &mfq, &k);
generate();
for (int i = 1; i <= k; i++)
{
int p, t;
scanf("%d %d", &p, &t);
d[p] = t;
}
lxl=w[c]; //lxl表示当前绫小路的能力值
for (i=1;i<=n;++i) //连边
{
while (top&&sta[top]+d[sta[top]]<i)
{
--top;
}
if (top)
{
l[i]=sta[top];
}
sta[++top]=i;
}
top=0;
for (i=n;i>=1;--i)
{
while (top&&sta[top]-d[sta[top]]>i)
{
--top;
}
if (top)
{
r[i]=sta[top];
}
sta[++top]=i;
}
for (i=1;i<=n;++i) //计数排序
{
++cnt[w[i]];
}
for (i=n-1;i>=0;--i)
{
cnt[i]+=cnt[i+1];
}
for (i=1;i<=n;++i)
{
ord[--cnt[w[i]]]=i;
}
for (i=n-1,j=0;i>=0;--i) //计算ans[0][i]
{
while (j<n&&w[ord[j]]==i)
{
if (ord[j]!=c)
{
dfs(ord[j]);
}
++j;
}
ans[0][i]=tot;
}
tot=0;
memset(vis,false,sizeof(vis));
dfs(c);
for (i=n-1,j=0;i>=0;--i) //计算ans[1][i]
{
while (j<n&&w[ord[j]]==i)
{
if (ord[j]!=c)
{
dfs(ord[j]);
}
++j;
}
ans[1][i]=tot;
}
int lastans = 0, finalans = 0;
for (i = 1; i <= m; i++)
{
int opt, x;
getOperation(lastans, opt, x);
if (opt == 1)
{
finalans = (finalans * 233ll + ans[lxl>=x][x]) % 998244353;
lastans = ans[lxl>=x][x];
}
else
{
lxl=x;
}
}
printf("%d\n", finalans);
return 0;
}
void dfs(int u)
{
if (vis[u]||u==0)
{
return;
}
vis[u]=true;
++tot;
dfs(l[u]);
dfs(r[u]);
}
```