相关链接
题目传送门: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; }