题意简述
有一个人在写树状数组题,模意义。
题目需要支持单点加,求区间和。
写的时候把所有的变化方向都写反了。
现在你需要执行两种操作:
1 l r : 在中等概率随机一点
执行单点加。
2 l r : 询问在此时调用错误的代码求答案有多大的概率出错。
输出概率时要求对取模。
算法讨论
补题时发现真是清真题,可能亏了一个亿啊??
不过反正我考场上也没时间写,还是自己太菜啊。
首先找一发规律可以知道错误写法求出来的就是后缀和。
由于这里是模意义,那么加法就等价于异或操作。
假设原来调用操作求出来的答案是
,区间
的答案是
。
现在错误的求出来的就是
,区间
的答案就是
,注意这个结论在
才成立,
时求出来的是
,其中
是现在所有
的异或和,即当前1操作的总数的奇偶性。
所以我们现在就知道了,原答案和新答案的异或在时是
,在
时是
。这样就可以把问题规模降成单点,暴力DP就是
啦。
我们发现DP的过程满足结合律和交换律,而且和询问有关的量只有询问点和修改点的关系,分别对应了四种转移。而且我们发现四种转移的范围分别是一个矩形。于是修改时我们就在二维线段树直接打标记,查询时就是一个清真的单点查询啦。
时间复杂度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ LL pow_mod(LL b,LL p,LL k) { LL res=1; for(;p;p>>=1) { if(p&1) res=res*b%k; b=b*b%k; } return res; } const int maxn=(int)(1e5)+5; const int mo=998244353; int rt[maxn<<2]; int ls[maxn*400],rs[maxn*400],ai[maxn*400]; int idx,n,m; inline int add(int a,int b) { return (1LL*a*(mo+1-b)+1LL*b*(mo+1-a))%mo; } int now; void addY(int& x,int l,int r,int lY,int rY) { if(!x) x=++idx; if(lY<=l && r<=rY) { ai[x]=add(ai[x],now); return; } int mid=(l+r)>>1; if(lY<=mid) addY(ls[x],l,mid,lY,rY); if(mid<rY) addY(rs[x],mid+1,r,lY,rY); } void addX(int x,int l,int r,int lX,int rX,int lY,int rY) { if(lX<=l && r<=rX) { addY(rt[x],0,n,lY,rY);return; } int mid=(l+r)>>1; if(lX<=mid) addX(x<<1,l,mid,lX,rX,lY,rY); if(mid<rX) addX(x<<1|1,mid+1,r,lX,rX,lY,rY); } int qsumY(int x,int l,int r,int Y) { if(l==r) return ai[x]; int mid=(l+r)>>1,res=ai[x]; if(Y<=mid) res=add(res,qsumY(ls[x],l,mid,Y)); else res=add(res,qsumY(rs[x],mid+1,r,Y)); return res; } int qsumX(int x,int l,int r,int X,int Y) { if(l==r) return qsumY(rt[x],0,n,Y); int mid=(l+r)>>1,res=qsumY(rt[x],0,n,Y); if(X<=mid) res=add(res,qsumX(x<<1,l,mid,X,Y)); else res=add(res,qsumX(x<<1|1,mid+1,r,X,Y)); return res; } int main() { int cnt=0; read(n);read(m); REP(i,1,m) { int opt,l,r; read(opt);read(l);read(r); if(opt==1) { now=2*pow_mod(r-l+1,mo-2,mo)%mo; addX(1,0,n,l,r,l,r); now=pow_mod(r-l+1,mo-2,mo); addX(1,0,n,l,r,r+1,n); now=pow_mod(r-l+1,mo-2,mo); addX(1,0,n,0,l-1,l,r); ++cnt; } else { int res=(mo+1-qsumX(1,0,n,l-1,r))%mo; if(l==1 && (cnt&1)) res=(mo+1-res)%mo; printf("%d\n",res); } } return 0; } |