相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4785
出题人传送门：http://jiruyi910387714.is-programmer.com/posts/209073.html
官方题解：https://pan.baidu.com/s/1dFGHFfr
解题报告
我们发现正常的代码是统计的前缀和
但劼的写法实际是统计后缀和
然后画一画发现，只有$l-1,r$这两个点被改到的时候才会影响答案
我们考虑询问区间是$[l,r]$，一个修改区间是$[a,b]$
那么如果$l,r \in [a,b]$则这个修改区间有$\frac{2}{b-a+1}$的可能影响到答案
如果$l,r$只有一个$\in [a,b]$那么这个修改区间有$\frac{1}{b-a+1}$的可能影响到答案
如果两个都不属于，其显然不会影响到答案
于是我们把修改操作看成二维平面上的点的话
每一个询问操作可以拆成三个矩阵的询问
这个是经典问题，可以用树套树/分治/K-d Tree来解决
至于怎么维护标记，直接做的话，我们可以看成矩阵乘法
因为这个转移矩阵非常特殊，搞一搞发现其不但满足结合律，还满足交换律，所以可以标记永久化
但还有更妙的做法：
我们可以搞一个类似生成函数的东西
设第$i$个操作有$p_i$的可能影响到当前询问，设两个端点被改变偶数次的概率为$a$，奇数次为$b$
那么最后$a-b=\prod\limits_{i}{(1-p_i)-p_i}$
为什么是对的呢？因为只有改变奇数次才会为奇数，而$-1$的奇数次方等于$-1$偶数次方等于$1$，所以刚好对上
又因为我们还知道$a+b=1$，所以$a = \frac{1+\prod\limits_{i}{(1-p_i)-p_i}}{2}$
另外的话，这题有一个坑点：如果$l-1=0$的话，我们需要特判
因为之前我们的推导基于$l-1$那个点记录的是一个后缀
而实际算法中我们我们默认$l-1$那个点的值为$0$，所以需要判断一下总操作次数奇偶
考试的时候就这一点没想到，血wa三小时，最后这题挂零
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100009;
const int M = 30000000;
const int MOD = 998244353;
const int REV = 499122177;
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
int n,m,tot;
class Segment_Tree{
int cnt,root,AnsTmp,ch[M][2],prod[M][2];
public:
inline void modify(int x, int y, int v, bool t) {
modify(root, 1, n, x, y, v, t);
}
inline int query(int x1, int x2, int y1, int y2, bool t) {
if (x1 > x2 || y1 > y2) return 1;
AnsTmp = 1;
query(root, 1, n, x1, x2, y1, y2, t);
return (AnsTmp+MOD)%MOD;
}
private:
void modify(int &w, int l, int r, int x, int y, int v, bool t) { //X
if (!w) w = ++cnt; modify(prod[w][0], 1, n, y, v, t);
if (l < r) {
int mid = l + r + 1 >> 1;
if (x < mid) modify(ch[w][0], l, mid-1, x, y, v, t);
else modify(ch[w][1], mid, r, x, y, v, t);
}
}
void modify(int &w, int l, int r, int p, int v, bool t) { //Y
if (!w) w = ++cnt, prod[w][0] = prod[w][1] = 1;
prod[w][t] = (LL)prod[w][t] * v % MOD;
if (l < r) {
int mid = l + r + 1 >> 1;
if (p < mid) modify(ch[w][0], l, mid-1, p, v, t);
else modify(ch[w][1], mid, r, p, v, t);
}
}
void query(int w, int l, int r, int L, int R, int y1, int y2, bool t) { //X
if (!w) return;
if (L <= l && r <= R) query(prod[w][0], 1, n, y1, y2, t);
else {
int mid = l + r + 1 >> 1;
if (L < mid) query(ch[w][0], l, mid-1, L, R, y1, y2, t);
if (mid <= R) query(ch[w][1], mid, r, L, R, y1, y2, t);
}
}
void query(int w, int l, int r, int L, int R, bool t) { //Y
if (!w) return;
if (L <= l && r <= R) AnsTmp = (LL)AnsTmp * prod[w][t] % MOD;
else {
int mid = l + r + 1 >> 1;
if (L < mid) query(ch[w][0], l, mid-1, L, R, t);
if (mid <= R) query(ch[w][1], mid, r, L, R, t);
}
}
}SGT;
inline int Pow(int w, int t) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD)
if (t&1) ret=(LL)ret*w%MOD;
return ret;
}
int main() {
n = read(); m = read();
for (int i=1,l,r,len,ret;i<=m;i++) {
if (read() == 1) {
l = read(); r = read();
len = Pow(r-l+1, MOD-2); ++tot;
SGT.modify(l, r, (1 - (len * 2ll)) % MOD, 0);
SGT.modify(l, r, (1 - (len * 4ll)) % MOD, 1);
} else {
l = read() - 1; r = read(); ret = 1;
ret = (LL)ret * SGT.query(1, l, l, r - 1, 0) % MOD;
ret = (LL)ret * SGT.query(l+1, r, r, n, 0) % MOD;
ret = (LL)ret * SGT.query(1, l, r, n, 1) % MOD;
ret = (ret + 1ll) * REV % MOD;
if (!l&&(tot&1)) ret = (1 - ret) % MOD;
printf("%d\n",(ret+MOD)%MOD);
}
}
return 0;
}
