给我自己的博客打个广告，关于莫比乌斯反演和整除分块上面有详细的讲解。

首先，我们求简化版问题：求 $\displaystyle{\sum_{i = 1}^n\sum_{j = 1}^m[(i, j) = 1]}$。

利用 莫比乌斯反演 + 整除分块 我们可以用 $O(\sqrt n)$ 的时间复杂度求解。

注意到，$[(i, j) = 1] = \varepsilon((i, j)) = \sum_{d \mid (i, j)}\mu(d)$。因此该题等价于求

$\displaystyle{\sum_{i = 1}^n \sum_{j = 1}^m \sum_{d \mid (i, j)}\mu(d)}$

交换求和顺序，有

$\displaystyle{\sum_{d = 1}\mu(d)\sum_{i = 1}^n[d \mid i]\sum_{j = 1}^m[d \mid j]}$

注意到，$1 \sim n$ 中 $d$ 的倍数有 $\lfloor \frac{n}{d} \rfloor$ 个，因此 $\sum_{i = 1}^n[d \mid i] = \lfloor \frac{n}{d} \rfloor$，因此有

$\displaystyle{\sum_{d = 1}^{\min(n, m)} \mu(d) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor}$

接下来，就可以用 整除分块 来求解了。

回到本题，我们将和式展开，有

$\begin{align} \sum_{i = a}^n\sum_{j = b}^m[(i, j) = 1] &= \sum_{i = 1}^n\sum_{j = b}^m\sum_{d \mid i, d \mid j}\mu(d) - \sum_{i = 1}^{a - 1}\sum_{j = b}^m\sum_{d \mid i, d \mid j}\mu(d) \\ &= \sum_{i = 1}^n\sum_{j = 1}^m\sum_{d \mid i, d \mid j}\mu(d) - \sum_{i = 1}^n\sum_{j = 1}^{b - 1}\sum_{d \mid i, d \mid j}\mu(d) - \\ & \quad \enspace \sum_{i= 1}^{a - 1}\sum_{j = 1}^m\sum_{d \mid i, d \mid j}\mu(d) + \sum_{i = 1}^{a - 1}\sum_{j = 1}^{b - 1}\sum_{d \mid i, d \mid j}\mu(d) \end{align}$

于是转化为了四个上面的简化版问题。

实际上，简化版问题也有对应的题目，可以直接水掉。

3220. [SDOI 2008] 仪仗队

3609. [BZOJ 1101] Zap

树形dp。

用 $f_{i, 0}$ 表示不选该点时的士兵数，相反，$f_{i, 1}$

每个边上至少选一个点。

由上面的性质可以得知，

1.当一个点不选时，另一个点就一定要选了。

2.当选一个点时，另一个点可选可不选。

因此，有

$$\begin{cases} \displaystyle{f_{i, 0} = \sum_{j \in \text{Son}(i)}{f_{j, 1}}} \\\displaystyle{f_{i, 1} = \sum_{j \in \text{Son}(i)}{\min(f_{j, 0}, f_{j, 1})}}\end{cases}$$

给我自己的博客打个广告(没有写过几篇文章)

给定非负整数 $x, y, m, n, L$。

求最小的非负整数 $t$，使得 $x + tm \equiv y + tn \pmod L$

首先，将题目中同余式化为 $ax + by = c$ 的形式：

 1. 移项，得 $(x - y) + t(m - n) \equiv 0 \pmod L$，即 $L \mid (x - y) + t(m - n)$

 2. 设 $pL = (x - y) + t(m - n)$，整理，得 $pL + t(n - m) = (x - y)$

该方程有解当且仅当 $(L, n - m) \mid (x - y)$

就求出了方程 $pL + t(n - m) = (L, n - m)$ 的特解 $p_0, t_0$。

得到该方程的通解为 $p = \frac{x - y}{d}p_0 + k\frac{n - m}{d}, \quad t = \frac{x - y}{d}t_0 - k\frac{L}{d} \enspace (k \in \mathbb{Z}, \enspace d = (L, n - m))$

最后，对通解进行一些调整，就得到了最小整数解

我们用 $f_{i,j}$ 表示 满足“前 $i$ 个含 $1$ 的数量不大于 $j$”的数的个数，相当于求组合数 ${i \choose j}$，即

$ f_{i, j} = f_{i-1, j} + f_{i-1, j-1} $

处理完动态规划的计算之后，我们从第 $n$ 位(即从右开始数第 $n$ 位)开始，如果 “前 $i-1$ 个含 $1$ 的数量不大于 $L$”的数的个数” 大于序数 $I$ (即 $f_{i-1, L} \ge I$)，那么我们输出 $0$，否则输出 $1$ (想一想，为什么)

不难理解，如果一个数的位数大于另一个数的位数，那么这个数一定大于另一个数(废话)。

那么前 $i-1$ 既然已经大于序数 $I$ 了，那么答案对应的数一定小于当前位取 $1$ 时候的数，所以当前位取 $0$。反过来同理。

输出完一位之后序数 $I$ 应减去对应的 $f_{i-1, L}$，并且确定完一位是 $1$ 之后，$1$ 的数量 $L$ 也应减一。即 

$I \gets I - f_{i-1, L}$, $L \gets L - 1$

看到这题的数据规模，我的第一想法是树状数组离线统计。

毕竟 $5\times 10^5$ 对于线段树什么的会非常吃力，我对 CCF 的评测机并不抱信心。

（然而好像有人用莫队 $O(N\sqrt{N\log N})$ 硬卡过去了）

考虑将所有询问离线，按右端点递增排序，思考怎样快速计算每个点的贡献。

在尝试了很多办法后，不妨回到题目本身，“丹钓战”这个名字似乎在暗示我们使用单调栈。

于是尝试先 $O(N)$ 求出距每个点 $i$ 最近的不合法位置 $L_i$。

然后可以发现，对于每个询问，只需要计算 $\sum\limits_{i=l}^r [L_i \notin [l,r]]$ 即可。

这个问题就非常简单了，和 HH的项链 类似，树状数组离线统计即可。

当然也可以用莫队/主席树，但是效率会比较感人。

时间复杂度 $O(Q\log N+N)$。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 500005;
int n,m,a[maxn],b[maxn],stk[maxn],top,L[maxn];
struct query {
	int x,y,id;
	query() {
		x = y = id = 0;
	}
	bool operator < (const query& p)const {
		return y < p.y;
	}
}Q[maxn];
int c[maxn];
int lowbit(int x) {
	return x & -x;
}
void add(int x,int y) {
	if(!x)return ;
	for(;x <= n;x += lowbit(x))c[x] += y;
	return ;
}
int query(int x) {
	int ans = 0;
	for(;x;x -= lowbit(x))ans += c[x];
	return ans;
}
int ans[maxn];
int main() {
	freopen("noi_online2022_stack.in","r",stdin);
	freopen("noi_online2022_stack.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++ i)scanf("%d",&a[i]);
	for(int i = 1;i <= n;++ i)scanf("%d",&b[i]);
	for(int i = 1;i <= n;++ i) {
		while(top&&(a[stk[top]] == a[i]||b[stk[top]] <= b[i]))stk[top --] = 0;
		L[i] = stk[top];
		stk[++ top] = i;
	}
	for(int i = 1;i <= m;++ i) {
		Q[i].id = i;
		scanf("%d%d",&Q[i].x,&Q[i].y);
	}
	sort(Q + 1 , Q + 1 + m);
	for(int i = 1,j = 1;i <= m;++ i) {
		for(;j <= Q[i].y;++ j) {
			if(!L[j])continue ;
			add(L[j] , 1);
		}
		ans[Q[i].id] = Q[i].y - Q[i].x + 1 - query(Q[i].y) + query(Q[i].x - 1); 
	}
	for(int i = 1;i <= m;++ i)printf("%d\n",ans[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}