多校联训2(Multi school joint training 2)

多校省选模拟2

A

题意

将前 \(n\) 个正整数,分成 \(m\) 个集合里,(应该是按照第二类斯特林数的类别分的),然后一个划分是好的,当且仅当存在 \(m\) 的圆排列。然后求好的划分的数量,

我的做法

我们考虑一个问题的转化,我们一个集合 \(A\) 可以向另一个集合连边 \(B\),当且仅当,\(\max(A)>\min(B)\),容易发现这样的边至少是单向的。

也就是说,如果我们把所有的这这些边的图画出来,那么这个图一定是一个强于竞赛图的图。

我们要做的,就是求这个图中的哈密顿回路。竞赛图的一些性质 – _zwl – 博客园 (cnblogs.com) 上面文章讲了一个竞赛图的性质。

那么这个哈密顿回路的条件等价于整个竞赛图是强连通的。考虑在我们上面得到的那个强于竞赛图的图上,也是这样的条件,因为这个图的连通性肯定比竞赛图要强。如果这个玩意是强连通的,但是没有一条哈密顿回路,这明显是不可能的,假设左边是一个强连通块,右边是一个强连通块,中间有一个桥连接这个块,我们总可以通过左边连通块的其他的边去往右边的块,然后从桥回来。

那么,我们直接计算这个图的强连通情况的个数明显是不好做的,我们在考虑问题的一个转化。

我们建立一个下面的图,先将数字从小到大排列,然后大的数字向小的数字连边,然后同一集合的数字向集合中的最大数字连边。

不难发现这个图的连通性和上面那个图是相等的。

那么我们按照顺序dp下面这个图的即可。

我们设计状态为 \(F[i][j][k]\) 表示从后向前 \(\text{dp}\) 到了第 \(i\) 个数字,已经有了 \(j\) 个集合,然后我们从 \(i\) 这个数字开始到后面一共连续有 \(k\) 个集合没有跟最后一个集合相连(不考虑这些集合的联通状态)。最初状态是 \(F[N][1][1]=1\)

那么我们可以分下面几个情况转移 \(i\rightarrow i-1\):

  • 这个数字单独成为一个集合 \(F[i][j][k]\rightarrow F[i – 1][j+1][k+1]\)
  • 这个数字和最后面 \(j-k\) 个和最后一个集合相连的集合连边 \((j-k)F[i][j][k]\rightarrow F[i-1][j][0]\)
  • 这个数字和教后面 \(k\) 个集合的某个最大数字相连 \(kF[i][j][k]\rightarrow F[i-1][j][k]\)

最后的答案就是 \(F[1][M][0]\)。

我们注意到这个解法的空间是 \(O(N^3)\),而时间也是 \(O(N^3)\),我们可以通过滚动数组把空间优化到 \(O(N^2)\)。

这是我和武汉外国语学校的熊子豪讨论的求解第一题的一个可能可行的方法,但是由于知识所限,不能完成算法的最后部分,因为没有学习二元多项式相关理论。

考虑化用题解中的性质:不能将值域划分成两部分。

如果去掉这个条件,答案显然是 \(\displaystyle {n\brace m}\);加上来,考虑容斥原理。令 \(f(i)\) 表示钦定了值域被划分为个 \(i\) 部分的方案数。所求即为:

考虑求解这个 \(f(k)\),最暴力的想法是枚举值域的一个划分 \(\{(0,i_1],(i_1,i_1+i_2],(i_1+i_2,i_1+i_2+i_3],\dots ,(\dots,n]\}\),其中 \(\sum i = n\)。然后再枚举分成的集合数量,分别是 \(j_1,j_2,\dots,j_k\),且 \(\sum j = m\)。这样的一种划分,对应的方案数是 \(\displaystyle\prod _{x=1}^k {i_x\brace j_x}\)。化一下上面的式子:

下面可能需要一些二元多项式求逆之类的高级东西,这我就不太会了。

// 这是我的解法的代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
const int MAXN = 505, MOD = 998244353;
/*
问题转化
强连通图
f[i][j][k] 为从后向前做到 i 个, 然后已经有 j 个集合,有 k 个集合没有跟 $n$ 那个相连
那么 最后的答案就是 f[1][M][0]
*/
int N, M, F[2][MAXN][MAXN];
auto Mod = [] (int x) {
	if (x >= MOD) {
		return x - MOD;
	}
	else if (x < 0) {
		return x + MOD;
	}
	else {
		return x;
	}
};
int main() {
	freopen("partition.in", "r", stdin);
	freopen("partition.out", "w", stdout);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	if (M >= N) {
		cout << 0 << '\n';
		return 0;
	}
	F[N & 1][1][0] = 1;
	for (int i = N - 1; i; --i) {
		int nw = i & 1;
		memset(F[nw], 0, sizeof F[nw]);
		//不连边,则多一个集合,并且
		int num = N - i + 1;
		for (int j = 1; j < num && j < M; ++j) {
			for (int k = 0; k < j; ++k) {
				F[nw][j + 1][k + 1] = Mod(F[nw][j + 1][k + 1] + F[nw ^ 1][j][k]);
			}
		}
		// 连向之前的一个集合和 最后一个集合相连的
		for (int j = 1; j <= M && j < num; ++j) {
			for (int k = 0; k < j; ++k) {
				F[nw][j][0] = ((long long) F[nw ^ 1][j][k] * (j - k) + F[nw][j][0]) % MOD;
			}
			// 连向之前的 j - k 个集合均可
		}
		// 和之前一个集合不和最后一个集合相连的相连
		for (int j = 1; j < num; ++j) {
			for (int k = 1; k < j; ++k) {
				F[nw][j][k] = (F[nw][j][k] + (long long) F[nw ^ 1][j][k] * k) % MOD;
			}
		}
	}
	cout << F[1][M][0] << '\n';
	return 0;
}

B

题意

设 \(1\sim n\) 中与 \(n\) 互质的数字数量为 \(\varphi (n)\),然后给定一个 \(n\) 个正整数序列 \(A\),一次执行 \(q\) 个操作,操作有三种类型。

  • 0 pos x 修改 \(A_{pos}\) 位置的值为 \(x\)。
  • 1 l r 查询 \(\varphi (\sum_{i=l}^r A_i)\)
  • 2 l r 查询 \(\varphi (\prod _{i=l}^r A_i)\)

\(n\le 5 \times 10^4\),\(q\le 1\times 10^5\),\(A_i\le 4\times 10^4\) 数据完全随机。

题解

我们考虑,由于数据随机,所以可以写一些复杂度看起来完全不对的算法,但是他在数据随机的时候保证复杂度即可。

我们考虑直接用线段树维护这个序列,然后维护区间和和区间乘法即可。

我们对于一操作的答案,由于值域不大,答案最大是 \(2e9\) 级别的,我们可以每次 \(O(\sqrt{nV})\) 的求出来他的 \(\varphi\) 值即可。

这样每次的复杂度为 \(O(\log n+\sqrt {nV})\)

我们在考虑二操作,这玩意答案明显很大,但是我们由于 \(\varphi\) 的计算可以知道,我们只要找到他的每个质因数 \(x\),然后乘上 \(\frac{x-1}{x}\) 即可。

于是我们考虑,可以在每个线段树节点上维护一个 每一位表示有没有第 \(i\) 个质因数即可。

bitset

由于数据随机,这样做是很快的。我们可以得到 \(4\times 10^4\) 内的质因数数量一共为 \(4203\) 个,不多。

所以只要按照上面这样做即可。

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
const int MAXV = 40005, MOD = 1e9 + 7, MAXN = 5e4 + 10;
using std::bitset;
int pri[MAXV], vis[MAXV], idx[MAXV], inv[MAXV], P[MAXV];
bitset<4210> factor[MAXV], ANS;
int N, M, A[MAXN], sc[MAXN];
void print(int x) {
	if (x < 10) {
		putchar(x + 48);
		return;
	}
	print(x / 10);
	putchar(x % 10 + 48);
}
int read() {
	int x = 0;
	char ch = getchar();
	while (!isdigit(ch)) {
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x;
}
struct Node {
	long long mul;
	bitset<4210> jy;
} nd[MAXN * 4];
#define jy(i) nd[i].jy
#define mul(i) nd[i].mul
inline int ls(int k) {
	return k << 1;
}
inline int rs(int k) {
	return k << 1 | 1;
}
inline void up(int k) {
	mul(k) = mul(ls(k)) * mul(rs(k)) % MOD;
	jy(k) = jy(ls(k)) | jy(rs(k));
}
void build(int k, int l, int r) {
	if (l == r) {
		mul(k) = A[l];
		jy(k) = factor[A[l]];
		return;
	}
	int mid = (l + r) / 2;
	build(ls(k), l, mid);
	build(rs(k), mid + 1, r);
	up(k);
}
auto Ksm = [] (int x, int y) -> int {
	int ret = 1;
	for (; y; y >>= 1, x = (long long) x * x % MOD) {
		if (y & 1) {
			ret = (long long) ret * x % MOD;
		}
	}
	return ret;
};
void modify(int k, int l, int r, int pos) {
	if (l == r) {
		mul(k)  = A[pos];
		jy(k) = factor[A[pos]];
		return;
	}
	int mid = (l + r) / 2;
	if (pos <= mid) {
		modify(ls(k), l, mid, pos);
	}
	else {
		modify(rs(k), mid + 1, r, pos);
	}
	up(k);
}
long long query2(int k, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) {
		ANS |= jy(k);
		return mul(k);
	}
	int mid = (l + r) / 2;
	long long ret = 1;
	if (ql <= mid) {
		ret *= query2(ls(k), l, mid, ql, qr);
	}
	if (mid < qr) {
		ret = ret * query2(rs(k), mid + 1, r, ql, qr) % MOD;
	}
	return ret;
}
void add(int x, int y) {
	for (; x <= N; x += x & -x) {
		sc[x] += y;
	}
}
int query1(int r) {
	int ret = 0;
	for (; r; r -= r & -r) {
		ret += sc[r];
	}
	return ret;
}
int main() {
	freopen("phi.in", "r", stdin);
	freopen("phi.out", "w", stdout);
	// INIT
	std::ios::sync_with_stdio(0);
	for (int i = 2; i < MAXV; ++i) {
		if (!vis[i]) {
			pri[++pri[0]] = i;
			idx[i] = pri[0];
		}
		for (int j = 1; j <= pri[0] && pri[j] * i < MAXV; ++j) {
			vis[pri[j] * i] = 1;
			if (i % pri[j] == 0) {
				break;
			}
		}
	}
	inv[0] = inv[1] = 1;
	for (int i = 2; i < MAXV; ++i) {
		inv[i] = (long long) (MOD - MOD / i) * inv[MOD % i] % MOD;
	}
	for (int i = 1; i <= pri[0]; ++i) {
		P[i] = (long long) (pri[i] - 1) * inv[pri[i]] % MOD;
	}
	for (int i = 1; i < MAXV; ++i) {
		int x = i;
		for (int j = 1; j <= pri[0] && pri[j] * pri[j] <= x; ++j) {
			while (x % pri[j] == 0) {
				x /= pri[j];
				factor[i].set(j);
			}
		}
		if (x != 1) {
			factor[i].set(idx[x]);
		}
	}
	// 
	N = read();
	M = read();
	for (int i = 1; i <= N; ++i) {
		add(i, A[i] = read());
	}
	build(1, 1, N);
	for (int opt, l, r; M--; ) {
		opt = read();
		l = read();
		r = read();
		if (opt == 0) {
			add(l, r - A[l]);
			A[l] = r;
			modify(1, 1, N, l);
		}
		else if (opt == 1) {
			int ret = query1(r) - query1(l - 1), k = ret;
			for (int i = 2; i * i <= k; ++i) {
				if (!(k % i)) {
					ret -= ret / i;
					while (!(k % i)) {
						k /= i;
					}
				}
			}
			if (k > 1) {
				ret -= ret / k;
			}
			print(ret);
			putchar('\n');
		}
		else {
			ANS.reset();
			long long ret = query2(1, 1, N, l, r);
			for (int i = ANS._Find_first(); i < ANS.size(); i = ANS._Find_next(i)) {
				ret = ret * P[i] % MOD;
			}
			print(ret);
			putchar('\n');
		}
	}
	return 0;
}

实际实现的时候,由于可能有点卡常,可以考虑把求和的线段树换成树状数组。

————————

Multi school provincial selection simulation 2

A

meaning of the title

Divide the first \ (n \) positive integers into \ (m \) sets (which should be divided according to the category of the second kind of Stirling number), and then a division is good if and only if there is a circular arrangement of \ (m \). Then find the number of good partitions,

My approach

We consider the transformation of a problem. We believe that one set \ (a \) can connect edges \ (B \) to another set if and only if, \ (\ max (a) & gt; \Min (b) \), it is easy to find that such an edge is at least unidirectional.

In other words, if we draw all the pictures on these sides, then this picture must be a picture < strong > stronger than the competition picture < / strong >.

All we have to do is find the Hamiltonian circuit in this graph. Some properties of tournaments -_ ZWL – blog Park (cnblogs. Com) the above article talks about the nature of a competition chart.

Then the condition of this Hamiltonian loop is equivalent to that the whole tournament is strongly connected. Consider the same condition on the graph stronger than the tournament graph we obtained above, because the connectivity of this graph must be stronger than the tournament graph. If this thing is strongly connected, but there is no Hamiltonian circuit, it is obviously impossible. Suppose that the left is a strongly connected block, the right is a strongly connected block, and there is a bridge connecting this block in the middle, we can always go to the right block through the other edges of the left connected block, and then come back from the bridge.

So, it is obviously not easy for us to directly calculate the number of strong connected cases of this graph. We are considering a transformation of the problem.

Let’s create the following graph, first arrange the numbers from small to large, then connect the large numbers to the small numbers, and then connect the numbers of the same set to the largest number in the set.

It is not difficult to find that the connectivity of this graph is equal to that of the graph above.

Then we can DP the following figure in order.

Our design status is \ (f [i] [J] [k] \), which means that there are \ (J \) sets from the back to the front \ (\ text {dp} \) to the \ (I \), and then there are \ (K \) sets continuously from the number \ (I \) to the back, which are not connected with the last set (regardless of the connectivity status of these sets). The initial state is \ (f [n] [1] [1] = 1 \)

Then we can transfer \ (I \ rightarrow i-1 \) in the following cases:

  • This number becomes a single set \ (f [i] [J] [k] \ rightarrow f [I – 1] [J + 1] [K + 1] \)
  • This number is bordered by the last \ (J-K \) set connected to the last set \ ((J-K) f [i] [J] [k] \ rightarrow f [I-1] [J] [0] \)
  • This number is connected with a maximum number of the following \ (K \) sets \ (KF [i] [J] [k] \ rightarrow f [I-1] [J] [k] \)

The final answer is \ (f [1] [M] [0] \).

We notice that the space of this solution is \ (O (n ^ 3) \) and the time is also \ (O (n ^ 3) \). We can optimize the space to \ (O (n ^ 2) \) by scrolling the array.

This is a possible and feasible method to solve the first problem discussed by Xiong Zihao of Wuhan foreign language school. However, due to the limitation of knowledge, the last part of the algorithm can not be completed because we have not learned the theory of binary polynomials.

Consider the nature of the solution to the problem of chemical application: the value range cannot be divided into two parts.

If this condition is removed, the answer is obviously \ (\ displaystyle {n \ brace m} \); In addition, consider the inclusion exclusion principle. Let \ (f (I) \) indicate the number of schemes whose value range is divided into \ (I \) parts. What is required is:

Considering solving this \ (f (k) \), the most violent idea is to enumerate a partition of the value range \ (\ {(0, i_1], (i_1, i_1 + i_2], (i_1 + i_2, i_1 + i_2 + i_3], \ dots, (\ dots, n]\} \), where \ (\ sum I = n \). Then enumerate the number of sets divided into, which are \ (j_1, j_2, \ dots, j_k \) and \ (\ sum J = m \). For such a division, the corresponding number of schemes is \ (\ displaystyle \ prod {x = 1} ^ k {i_x \ brace j_x} \). Change the above formula:

The following may require some advanced things such as the inverse of binary polynomials, which I don’t know very well.

// 这是我的解法的代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
const int MAXN = 505, MOD = 998244353;
/*
问题转化
强连通图
f[i][j][k] 为从后向前做到 i 个, 然后已经有 j 个集合,有 k 个集合没有跟 $n$ 那个相连
那么 最后的答案就是 f[1][M][0]
*/
int N, M, F[2][MAXN][MAXN];
auto Mod = [] (int x) {
	if (x >= MOD) {
		return x - MOD;
	}
	else if (x < 0) {
		return x + MOD;
	}
	else {
		return x;
	}
};
int main() {
	freopen("partition.in", "r", stdin);
	freopen("partition.out", "w", stdout);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	if (M >= N) {
		cout << 0 << '\n';
		return 0;
	}
	F[N & 1][1][0] = 1;
	for (int i = N - 1; i; --i) {
		int nw = i & 1;
		memset(F[nw], 0, sizeof F[nw]);
		//不连边,则多一个集合,并且
		int num = N - i + 1;
		for (int j = 1; j < num && j < M; ++j) {
			for (int k = 0; k < j; ++k) {
				F[nw][j + 1][k + 1] = Mod(F[nw][j + 1][k + 1] + F[nw ^ 1][j][k]);
			}
		}
		// 连向之前的一个集合和 最后一个集合相连的
		for (int j = 1; j <= M && j < num; ++j) {
			for (int k = 0; k < j; ++k) {
				F[nw][j][0] = ((long long) F[nw ^ 1][j][k] * (j - k) + F[nw][j][0]) % MOD;
			}
			// 连向之前的 j - k 个集合均可
		}
		// 和之前一个集合不和最后一个集合相连的相连
		for (int j = 1; j < num; ++j) {
			for (int k = 1; k < j; ++k) {
				F[nw][j][k] = (F[nw][j][k] + (long long) F[nw ^ 1][j][k] * k) % MOD;
			}
		}
	}
	cout << F[1][M][0] << '\n';
	return 0;
}

B

meaning of the title

Let the number of numbers in \ (1 \ SIM n \) that are coprime with \ (n \) be \ (\ varphi (n) \), then give a \ (n \) positive integer sequence \ (a \), and execute \ (Q \) operations at a time. There are three types of operations.

  • The value of 0 POS x modified \ (a {POS} \) position is \ (x \).
  • 1 L R query \ (\ varphi (\ sum {I = l} ^ R a _i) \)
  • 2 l r 查询 \(\varphi (\prod _{i=l}^r A_i)\)

\(n \ Le 5 \ times 10 ^ 4 \), \ (Q \ le 1 \ times 10 ^ 5 \), \ (a_i \ Le 4 \ times 10 ^ 4 \) data are completely random.

Problem solution

We consider that because the data is random, we can write some algorithms whose complexity seems completely wrong, but it can ensure the complexity when the data is random.

We consider maintaining the sequence directly with the line segment tree, and then maintaining the interval and interval multiplication.

For our answer to an operation, because the value range is small, the maximum answer is \ (2E9 \) level. We can find its \ (\ varphi \) value every time \ (O (\ sqrt{nv}) \).

In this way, the complexity of each time is \ (O (\ log n + \ sqrt {NV}) \)

We are considering two operations. The answer is obviously big, but we can know from the calculation of \ (\ varphi \), we just need to find each prime factor \ (x \) and multiply it by \ (\ frac{x-1}{x} \).

Therefore, we consider that we can maintain a prime factor of \ (I \) for each bit representation on each segment tree node.

bitset

Because the data is random, this is fast< Strong > we can get that the number of prime factors in \ (4 \ times 10 ^ 4 \) is \ (4203 \), not much

So just follow the above.

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
const int MAXV = 40005, MOD = 1e9 + 7, MAXN = 5e4 + 10;
using std::bitset;
int pri[MAXV], vis[MAXV], idx[MAXV], inv[MAXV], P[MAXV];
bitset<4210> factor[MAXV], ANS;
int N, M, A[MAXN], sc[MAXN];
void print(int x) {
	if (x < 10) {
		putchar(x + 48);
		return;
	}
	print(x / 10);
	putchar(x % 10 + 48);
}
int read() {
	int x = 0;
	char ch = getchar();
	while (!isdigit(ch)) {
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x;
}
struct Node {
	long long mul;
	bitset<4210> jy;
} nd[MAXN * 4];
#define jy(i) nd[i].jy
#define mul(i) nd[i].mul
inline int ls(int k) {
	return k << 1;
}
inline int rs(int k) {
	return k << 1 | 1;
}
inline void up(int k) {
	mul(k) = mul(ls(k)) * mul(rs(k)) % MOD;
	jy(k) = jy(ls(k)) | jy(rs(k));
}
void build(int k, int l, int r) {
	if (l == r) {
		mul(k) = A[l];
		jy(k) = factor[A[l]];
		return;
	}
	int mid = (l + r) / 2;
	build(ls(k), l, mid);
	build(rs(k), mid + 1, r);
	up(k);
}
auto Ksm = [] (int x, int y) -> int {
	int ret = 1;
	for (; y; y >>= 1, x = (long long) x * x % MOD) {
		if (y & 1) {
			ret = (long long) ret * x % MOD;
		}
	}
	return ret;
};
void modify(int k, int l, int r, int pos) {
	if (l == r) {
		mul(k)  = A[pos];
		jy(k) = factor[A[pos]];
		return;
	}
	int mid = (l + r) / 2;
	if (pos <= mid) {
		modify(ls(k), l, mid, pos);
	}
	else {
		modify(rs(k), mid + 1, r, pos);
	}
	up(k);
}
long long query2(int k, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) {
		ANS |= jy(k);
		return mul(k);
	}
	int mid = (l + r) / 2;
	long long ret = 1;
	if (ql <= mid) {
		ret *= query2(ls(k), l, mid, ql, qr);
	}
	if (mid < qr) {
		ret = ret * query2(rs(k), mid + 1, r, ql, qr) % MOD;
	}
	return ret;
}
void add(int x, int y) {
	for (; x <= N; x += x & -x) {
		sc[x] += y;
	}
}
int query1(int r) {
	int ret = 0;
	for (; r; r -= r & -r) {
		ret += sc[r];
	}
	return ret;
}
int main() {
	freopen("phi.in", "r", stdin);
	freopen("phi.out", "w", stdout);
	// INIT
	std::ios::sync_with_stdio(0);
	for (int i = 2; i < MAXV; ++i) {
		if (!vis[i]) {
			pri[++pri[0]] = i;
			idx[i] = pri[0];
		}
		for (int j = 1; j <= pri[0] && pri[j] * i < MAXV; ++j) {
			vis[pri[j] * i] = 1;
			if (i % pri[j] == 0) {
				break;
			}
		}
	}
	inv[0] = inv[1] = 1;
	for (int i = 2; i < MAXV; ++i) {
		inv[i] = (long long) (MOD - MOD / i) * inv[MOD % i] % MOD;
	}
	for (int i = 1; i <= pri[0]; ++i) {
		P[i] = (long long) (pri[i] - 1) * inv[pri[i]] % MOD;
	}
	for (int i = 1; i < MAXV; ++i) {
		int x = i;
		for (int j = 1; j <= pri[0] && pri[j] * pri[j] <= x; ++j) {
			while (x % pri[j] == 0) {
				x /= pri[j];
				factor[i].set(j);
			}
		}
		if (x != 1) {
			factor[i].set(idx[x]);
		}
	}
	// 
	N = read();
	M = read();
	for (int i = 1; i <= N; ++i) {
		add(i, A[i] = read());
	}
	build(1, 1, N);
	for (int opt, l, r; M--; ) {
		opt = read();
		l = read();
		r = read();
		if (opt == 0) {
			add(l, r - A[l]);
			A[l] = r;
			modify(1, 1, N, l);
		}
		else if (opt == 1) {
			int ret = query1(r) - query1(l - 1), k = ret;
			for (int i = 2; i * i <= k; ++i) {
				if (!(k % i)) {
					ret -= ret / i;
					while (!(k % i)) {
						k /= i;
					}
				}
			}
			if (k > 1) {
				ret -= ret / k;
			}
			print(ret);
			putchar('\n');
		}
		else {
			ANS.reset();
			long long ret = query2(1, 1, N, l, r);
			for (int i = ANS._Find_first(); i < ANS.size(); i = ANS._Find_next(i)) {
				ret = ret * P[i] % MOD;
			}
			print(ret);
			putchar('\n');
		}
	}
	return 0;
}

In the actual implementation, because it may be a little stuck, we can consider replacing the summation line segment tree with a tree array.