【ZJOI2017】树状数组


分析1

打个暴力,小范围的找一下规律,就会发现,这个写错的树状数组,其实就是单点修改,查询后缀和

那么因为所有的结果都对2取模,那么我们可以看成是查询后缀异或和

这样一来,我们\(Find(x)\)就是\(XOR_{i=x}^{n} a_i\)

于是\(Query(l,r)\)就是\(XOR_{i=l-1}^{n} a_i \oplus XOR_{i=r}^{n} a_i=XOR_{i=l-1}^{r-1} a_i\)

而实际,正确的答案应该是\(XOR_{i=l}^{r} a_i\),那么我们只要看\(a_{l-1}\oplus a_{r}\)的结果就行了

但是,当\(l=1\)的时候,情况就不一样了,因为Find函数,特判了\(l=1\)的情况

\(Query(1,r)=XOR_{i=r}^{n} a_i\),而实际需要的是\(XOR_{i=l}^{r} a_i\),那么就要看\(XOR_{i=1}^{n(i\neq r)} a_i\),也就是\(T\oplus a_r\),\(T\)表示\(1\)操作的次数,即修改的次数

那么,这样一来就变成了单点修改问题,直接暴力解决,时间复杂度\(O(nm)\),可以得到50分


分析2

这样一来,我们可以把问题转化到平面上来做

对于一个修改\([l,r]\),我们可以转为平面上的点\((l,r)\)

那么,对于一个询问,我们可以分三类讨论

第一类是仅包含左端点的,即\(1≤x≤l-1,1≤y<r\)

第二类是仅包含右端点的,即\(l≤x≤r,r≤y≤n\)

第三类是包含左右端点的,即\(l≤x≤l-1,r≤y≤n\)

显然,前两部分可以合在一起做,不过似乎网上的代码大都是三部分合在一起做的,这或许也是我常数大的原因吧

那么,我们就变成了动态二维数点问题,直接用二维线段树维护一下就好(我直接写了一棵四分树)

对于第一类,我们保留端点为\(1\)的概率,合并两个点的概率\(x\)和\(y\),显然可以保留其中一个,那么\(P=x*(1-y)+y*(1-x)\)

对于第二类,我们保留两端点相同的概率,合并两个点的概率\(x\)和\(y\),显然可以两个相等得到,也可以是都不同得到,那么\(P=x*y+(1-x)*(1-y)\)

然后就是写代码的问题了,没什么细节问题,就是要注意常数问题

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 21,626

Categories

Archive

Comments