唉……搞了这么久OI还是只会暴力打打，没救了……

51nod算法马拉松24

最近没有一场比赛打得爽，互测Round 5 GG，校内训练GG，Codechef GG，省选GG。本来想打打51nod出点气，结果TM又崩了。。。

51nod被两道码农数据结构恶心了一脸（应该是我太弱），F题写了个 $O(n\log^2n)$ 的东西被卡常数卡内存，然后才发现做复杂了。最后。。。被9min绝杀，#11滚粗。。。真是不爽。

以下是本人参加51nod算法马拉松24的滚粗过程。

开场看题，A一开始没懂，跳过，看B。

B一开始猜贪心结论，每个尽量往后选，然后随手叉掉了。看 $n\le 20$ 奥妙重重的样子，似乎暴力状压DP可过。

于是10min+的时候把B题过了。

C一开始以为是丧题，感觉数据范围这么大一定有什么性质。先猜足够大的图一定有解，然后发现死活没法把一个格子取反，才发现怎么弄xor和都是0。。。

于是猜想足够大的图有偶数个1就行了。为了验证这个规律，写了个暴力高斯消元观察规律。。。好像确实是这样2333

然后特判了 $n=1$、$m=1$、$n=m=2$ 的情况就切掉了C题，大概30min+？

D目测套路题。。。推下式子 $\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=1}^{j-i+1}sum_{i,j,k}$，$sum_{i,j,k}$ 为区间 $[i,j]$ 前 $k$ 大和，再推一下变成 $$\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=i}^ja_k\cdot rank_{i,j}(a_k)=\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=i}^ja_k\sum_{t=i}^j[a_t\le a_k]$$

$rank_{i,j}(x)$ 表示 $x$ 是 $[i,j]$ 里面第几小的，假设所有数互不相同。于是交换下求和顺序 $$\sum_{k=1}^na_k\sum_{t=1}^n[a_t\le a_k] (\sum_{l=1}^{\min\{k,t\}}\sum_{r=\max\{k,t\}}^n1)=\sum_{k=1}^na_k\left[\sum_{t=1}^k[a_t\le a_k]t(n-k+1)+\sum_{t=k+1}^n[a_t\le a_k] (n-t+1)k\right]$$

两个和式BIT搞搞就 $O(n\log n)$ 做完了。然后在1h左右的时候过掉了。。。

接着开E。然后就进入了SB时间。。。一开始想直接弄个DFS序然后按深度奇偶性分成两个序列，接着发现操作3的LCA询问不会做。然后感觉LCA的条件很不好搞，似乎用距离来做更好做一些？于是作死时间开始。。。$dist(a,b)=dep(a)+dep(b)-2\cdot dep(LCA(a,b))$，通过构造边权使得 $dep(a)=a$，然后变成询问某点到所有黑点的距离和。接着继续作大死。。。树分治一波看看能不能搞出来，接着脑补了好久的树分治发现并不会做= =

浪费了好久，回头考虑别的做法。对于每个询问，如果把 $\sum_{i=1}^nLCA(i,x)$ 换成 $\sum_{a=1}^n\sum_{x=1}^n[LCA(i,x)=a]$ 呢？然后发现 $\sum_{x=1}^n[LCA(i,x)=a]$ 并不是 $a$ 子树内的点数。。。如果强行按子树内的点来算呢？那就把LCA和它的所有祖先全算上了。如果构造点权 $v_a$ 使得 $a$ 到祖先的所有点的点权和等于 $a$ 呢？

好像问题简单了些。。。记 $s(i)$ 为 $i$ 子树内黑点数乘以 $v_i$，查询只要查 $x$ 到根的路径上 $s(i)$ 的和。似乎可以强上树剖线段树，然而信息不是很好维护？又纠结了一会儿无果。

看了下好多人过了A，就回去看A，终于正确理解题意了。列了几个方程发现 $n$ 偶数才有解，有解的时候外圈填 $1,2,\cdots,n-1$ 内圈列个方程，似乎直接解出来了= =然后就过了A。

回去研究E树剖以后怎么维护线段树信息，但搞不清楚，于是准备第二天起来继续研究。

……

之后的思路大概是，$x$ 到根的路径只要每个点加一个数就行了，然而 $x$ 子树就不会搞了- -感觉是取反，但取反以后和该怎么变？好像是 $siz_i\cdot v_i-s(i)$。。。接着继续大作死。。。既然修改是子树，那么就是DFS序的一个区间，在线段树上对应 $O(\log n)$ 个节点。那么对一个节点取反的时候，它对应的树上节点的祖先都会受到影响，是不是会影响到这些节点的答案？然后顿时不会了。。。

又瞎折腾了一堆奇奇怪怪的东西没折腾出来，真不知道自己的脑子哪去了。。。

后来又想想暴力该怎么写，发现就是

for(int i=pre[x];i<=pos[x];i++)s[i]=siz[i]*v[i]-s[i];

感觉自己真是无比SB。。。初始化几个前缀和然后线段树维护一堆东西就行了。

然后开始写，写的时候发现忘了考虑深度的奇偶性这一回事，又强行记了两倍东西，常数飞起，不过时限4.5s不虚。继续写，又发现我好像没维护单点的颜色，于是往上更新就更新不动了= =

总之写完花了挺久的吧，代码还巨长。调过小样例以后测大样例不出意外地挂了，又花了好久调。。。把修改打出来看。。。已经中午了。。。

才发现我误把 $s(i)$ 当成 $i$ 子树内的黑点数来更新祖先节点了，惨。

又多写了好多代码终于在14:00前完事了。光这题就花了半天，我这代码能力恐怕是没救了？

最后做F。

一开始看到这种题觉得是个 priority_queue 练习题，先把最小的塞进去，每次 pop 掉最小的，把它能到的最小的以及它的上级能到的比它大的最小的塞进 priority_queue，重复 $K-1$ 次以后取 top 就是答案。接着继续作死。。。

前一种转移相当于子矩形最小值，后一种转移相当于先查出子矩形中某个数的rank为 $x$，再求子矩形第 $x+1$ 小值。区间第 $x$ 小怎么做？可持久化线段树。。。矩阵呢？可持久化线段树套可持久化线段树，时间空间都是 $O(n\log^2n)$。。。然而空间204800KB算了算发现过不去。。。

换成可持久化BIT套可持久化线段树？BIT就用vector记下所有版本，查询时二分出所在版本就行。然而内存还是好虚。。。大力卡卡内存试试。

写到一半发现好像可以优化的样子，然而并没有去优化。。。

写了好久结果大样例一直WA，调了好久发现 $i,j$ 打反。

总算调过以后交上去各种TLE，然后自己生成大数据RE，惨。把数组开大不RE了，但是要跑10s+，GG。。。交上去试试，结果MLE。。。开小点RE，开大点MLE，而且不管怎样都TLE，没救了。。。

当时20:30看已经有9个人AK了，很慌，觉得快要没奖金拿了。于是把之前的优化思路再想想。。。卧槽为什么我这么SB啊。。。

只要查最小值就行了啊然后把 $[l,r]$ 沿最小值位置 $p$ 分成 $[l,p-1]$ 和 $[p+1,r]$ 两边递归下去找最小值就行了啊，区间最小值没必要用可持久化线段树用普通线段树就行了啊，二维的就线段树套线段树空间 $O(n\log n)$。。。代码也简单得多，真是不知道自己为何如此逗逼。。。

最后花1h大力码代码大力调代码，终于在21:30的时候交上去，F题过了。。。

接着看到榜就悲催了，#11。。。上一名在我前面9min绝杀了。。。

总结就是，我的数据结构代码能力实在是太辣鸡了，以及做题老是想复杂掉坑。

LYDSY 5月份月赛

打了个LYDSY的ACM赛，结果被屠成SB，2题滚粗。。。

由于晚上在外面吃饭，20:00多才回家

吃饭的时候先看了前面的题，A不太会构造，B诶这不是傻逼题吗，倒着模拟。。。于是写了发现过不去，才发现题意理解错了，有点懵逼

回家以后发现A的构造很傻逼，就写掉了

B想想感觉套个二分就行了，然后写了好久

交上去，WA。。。

自己出了几组数据找到哪里WA了，改

交上去，又WA。。。

小数据发现不了问题，开始生成大数据，然后发现忘了开64位整数。。。

交上去，TLE。。。

加个输入优化

交上去，又TLE。。。没救了

剩1h。。。

弃疗看后面的题，C好像极角排序就行，D好像线段树优化DFS就行

D可能好写点就去写D了

很快就写完了，手构数据发现一个bug，改完就过了

最后剩半小时左右写C，最后5min调过样例

交上去，WA最后还是没调出来。。。结束了。。。2题滚粗，再见看了下排名只有#39，这在NOI可能只能压线进队啊，这不行啊，看来我姿势水平有待提高

UPD：

我怎么这么菜啊，D题答案就是2^k，k为满足区间[i,n]的最小值为i的i个数。感觉我把简单题想复杂的本领不是一般地高。。。

继续调C，调出一个错又WA了一发然后过了