并不对劲的loj2251:p3688[ZJOI2017]树状数组

题目大意

有人用错误的树状数组维护长度为\(n\)的01串\(a_1,...,a_n\)的区间异或和。
错误的树状数组：

void add(int x){for(;x;x-=lowbit(x))tr[x]^=1;return;}
int ask(int x){int k=0;for(;x<=n;x+=lowbit(x))k^=tr[x];return k;}
int query(int l,int r){return ask(l-1)^ask(r);}

有\(m\)次操作，操作分两种：
1.给定\(l,r\)，在\(a_l,a_{l+1},...,a_r\)中随机选一个修改；
2.给定\(l,r\)，问求\(a_l,a_{l+1},...,a_r\)的异或和，答案正确的概率是多少；
\(n,m\leq 10^5;\)

题解

发现这树状数组的ask求的是后缀异或和，所以query求的是：
\(l=1\)时，\(ask(l-1)=0\)，query求的是\(a_r,...,a_n\)的异或和；\(l\neq 1\)时，\(ask(l-1)\bigoplus ask(r)=a_{l-1},...,a_{r-1}的异或和\)。
\(l=1\)时，答案正确的概率=\((a_r\bigoplus...\bigoplus a_n=a_1\bigoplus ...\bigoplus a_r)\)的概率=\(((a_r\bigoplus...\bigoplus a_n)\bigoplus (a_1\bigoplus ...\bigoplus a_r)=0)\)的概率。由\((a_r\bigoplus...\bigoplus a_n)\bigoplus (a_1\bigoplus ...\bigoplus a_r)=a_r\bigoplus(a_1\bigoplus...\bigoplus a_n)\)，可知答案正确的概率=\((a_r\bigoplus...\bigoplus(a_1\bigoplus...\bigoplus a_n))=0\)的概率。
\(l\neq 1\)时，答案正确的概率=\((a_{l-1}=a_r)\)的概率。
可以用第一维是左端点、第二维是右端点、存左右端点相等的概率的树套树维护。

代码

#include
#include
#include
#include
#include
#include
#include
#include
#include