自动搬运

查看原文

来自洛谷，原作者为

	ouuan 如果奇迹有颜色的话，那么其中之一必是橙色的吧。

搬运于2025-08-24 22:05:44，当前版本为作者最后更新于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$。

参考代码：

#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]);
}