PKUSC的题比THUSC的题高到不知道哪里去了。
既然反正都没有纸，只是锻炼的话，干嘛不去PKUSC？
以下全是口胡。因为没有数据甚至没有正式的题面所以都没有写。
Day1T1
可以发现只需要关心是否同行同列。于是设(f_{i,0/1,0/1})表示从行是否相同，列是否相同的某个地方走(i)步到某点的方案数。转移矩阵乘法即可。
Day1T2
考虑如果每个点向后面第一个大于它的点连边，连出一棵树。一次询问相当于查某段祖先后代链的权值和。作差，变成求某个点到根的权值和。
现在维护个序列(c)，每个点记一下它的出现次数。一开始(c={1,1,dots,1})。后面得到的(a')都可以视作(c_i)个(a_i)顺次拼接。
一次修改相当于：对于(c)中的某个区间，找到其中的局部权值最小值，将其(c_i)减一；局部权值最大值，(c_i)加一。
一开始先连好边。如果某个点(c_i=0)，那么它在后面的处理都视作消失（比如不参与区间最小值的比较，不对答案产生贡献），但是树的形态不发生变化。这意味着询问的时候还是可以直接问某个点到根的贡献，只是忽略途中(c_i=0)的罢了。
标一下局部权值最小值是什么。搞个对局部最小值修改的标记，如果发现有减到(0)的就暴力下去修改。因为这个值在这之后就永久消失，所以可以势能分析。将某个(c_i)变成(0)的时候，查查后继将它标成局部最小值。
于是就是用线段树维护(c_i)以及一系列的操作（第几个，前驱后继，区间最大值等），用另一棵线段树维护每个点到根的贡献和。时间(O(nlg n))
Day2T1
枚举哪条边被删除。删除后分成两个连通块，块内好算，直接算两两之间路径和。块间的可以考虑：相当于两个块中各拿出一条路径，然后拼接。那么也用块内两两之间路径和来计算。
Day2T2
考虑一个看起来是对的贪心策略：暂时不考虑优惠券是否能花光，因为优惠券可以当钱使用，所以把它看做和钱同等地位。又因多花钱可以送优惠券，所以先尽量花钱。因为花钱送券时如果不是整除是不优的，所以尝试用优惠券尽量抵消掉(a_imod c)元。就这样一直做到最后，发现还有大量的优惠券，很浪费，那么就从后往前考虑，尝试尽量用优惠券来买这些商品。
总结一下，可以感受到最优解是：有个分界点(mid)，前面(1)到(mid-1)都是每个尽量用优惠券消耗(a_imod c)，(mid+1)到(n)都全部用优惠券购买。并且这个(mid)有可二分性。
二分(mid)然后判断。维护下(1)到(mid-1)能留下多少优惠券，(mid+1)到(n)总共要花多少钱等东西。前者要对区间维护：最多多少优惠券可以在这个区间被抵消，并且进入这个区间又出来之后新增了多少优惠券这样。（或者也可以这么看：(b_i=a_i mod c,d_i=frac{a_i-b_i}{c})，设(S_i)表示搞完(1)到(i)之后的优惠券是多少。那么有(S_i=max(S_{i-1}-b_i,0)+d_i)。对这个操作进行合并即可（当然也可以矩阵乘法））。
Day2T3
假如知道了两个数小数部分的大小关系以及整数部分的差，就可以知道它们实际的差和(k)的大小关系。
可以DP：设(f_{i,x,y,j,l})表示考虑了前(i)个数，最后两个数整数部分分别为(x,y)，小数部分在前(i)个数的排名分别是(j,k)，的方案数。
直接做时间是(O(n^3m^2))（听说是可以前缀和转移）。
发现其实如果(x-y>k)则转移一样。那么只需要记(x)和(x-y)，并且(x-y>k)的一起处理。
因为(k< frac{2m}{n})。然后时间复杂度就变成了(O(n^2m^2))。