先上了两天的课，主要以讲题为主。
考试大巴好像翻车了，我们学校的人\(7\)点半到考场，\(8\)点我们考场总共只来了\(4\)个人，其他人还都是走路/打车来的。\(8\)点\(45\)人才陆续到齐开考。
打开题面：
T1仙人掌什么鬼啊弃疗。。
T2好像可以搞一搞？
T3多项式+字符串好可怕啊不会做只会\(10\)分暴力
于是开始大力推导T2。
意会了一下写错的树状数组相当于前缀修改和两点查询，把他的代码蒯下来随便试了试感觉很对。看了下部分分有个\(30\)分\(n\le 50\)，感觉很暴力呀。记录\(f_{i}\)为每个位置最终为\(1\)的概率直接算就可以了？
然后WA on 样例。
于是换了个想法。令\(a\)表示写对的树状数组的前缀和为\(1\)的概率，\(b\)表示写错的树状数组的前缀和为\(1\)的概率，比较两段似乎就不会有问题了。
算是过了样例。想测一发大样例。打开文件夹一看
cactus/cactus.in cactus.out
bit/
poly/poly.in poly.out
不会这题没大样例吧
于是手造了几组数据。。貌似又WA了
仔细想了想好像概率不独立？
于是直接考虑每次修改对于每种询问的影响：
令\(ans\)为两个树状数组查询结果的异或值，那么\(ans=0\)表示正确，否则为错误。
如果修改了位置\(p\)，那么正确的树状数组中\([p,n]\)的值会异或\(1\)，错误的树状数组中\([1,p]\)的值会异或\(1\)。
那么如果一个询问的端点不在\(p\)上\(ans\)是不会变的。
那么如果一个长度为\(len\)的修改包含了某个询问的一个端点，那么这个询问的\(ans\)就有\(\frac{1}{len}\)的概率变化。
如果一个长度为\(len\)的修改包含了某个询问的两个端点，那么这个询问的\(ans\)就有\(\frac{2}{len}\)的概率变化。
那么就是一些线段的问题了。统计每个修改对每个询问的贡献即可。
先写了个\(n^2\)暴力，手构的数据貌似跑得挺对。如果没错就拿到\(50\)分了？
看了看时间，妈呀怎么只有两个多小时了。
再去看一眼T3貌似还是只会\(10\)分，快速幂FFT似乎也过不了\(30\)。
T1没什么想法。。好像T2离正解也没差多少了接着写吧。
考虑一下用树状数组优化？发现需要减掉一些区间的答案，那么需要贡献的逆过程。
贡献：\(apply(x,y)=x(1-y)+y(1-x)=x+y-2xy\)
逆贡献：\(bpply(x,y)=\frac{x-y}{1-2y}\)
于是写了个cdq+树状数组。
写完拍一拍发现WA了。。发现\(apply\)完\(bpply\)回去居然值不一样了。。难道不能求逆。。那不是gg了。。
仔细看了一下，貌似\(y=\frac{1}{2}\)。。求逆的时候就挂了。。
于是再分析了一下这个\(apply\)的性质：
满足交换律
满足结合律
满足分配律
存在逆元
具有封闭性
…
好优美啊
不对我在做什么。。明明是要分析\(\frac{1}{2}\)
发现\(apply(x,\frac{1}{2})=x+\frac{1}{2}-x=\frac{1}{2}\)
并且由于交换律，只要有\(\frac{1}{2}\)对某个询问产生了贡献那么这个询问的答案就是\(\frac{1}{2}\)了
于是先把所有长度为\(2\)的修改提出来处理一下就好了
终于拍不WA之后看了看时间。。只有半个多小时了
赶快T3暴力写起。。\(10\)分还是不难写的。。测了点数据感觉不会T
接着赶快T1暴力写起
枚举完加的边发现还要判是不是个仙人掌。。只剩不到\(5\)分钟了感觉没什么戏弃疗了
出来问王队长：
“怎么T2没有大样例啊？”
“啊？有的啊。你需要再解压一遍。我第一次解压出来什么都没有。”
然后听说XPZ也是第一遍解压少了东西。。这个解压软件怎么这么鬼畜啊。。。
然后听说伦和YMD都会做T2。。开口就是
“二维线段树”
“当\(l=1\)时balabala，当\(l\ne 1\)时balabala”
都过了大样例。。感觉我的是个萎的啊。。那我要爆零了啊。。
上飞机之前听说有题解了赶快下下来看一下
看到这句话兴奋透了 我的做法可能是正解呀
但是没试大样例还是虚的一B啊
AC还是爆零就看脸了吧。。幸好不是浙江人，没有利益相关
upd：果然还是爆零了呀。。
又仔细想了一下
此处
那么如果一个询问的端点不在\(p\)上\(ans\)是不会变的。
还是有点问题
应该是
如果一个询问的端点同时在或同时不在\(0\)和\(p\)上\(ans\)是不会变的。
也就是说，如果一个询问有一个端点在\(0\)上，那么应将条件改成有\(1-\frac{1}{len}\)的概率变化。
听说他们都是大样例看出的这个问题。。
辣鸡解压软件毁我青春。。吃我大样例。。
不过还是挺开心的 毕竟是来学习的又不是来进队的
发现能在考场上想出一道ZJOI的题 还是挺愉快的
HNOI加油233
前排Orz