codechef FEB17

比赛刚放出来的时候有7个题，四天以后就只有5个题了。。怎么感觉cc很缺题的样子

有两个题没做。最近越来越懒了。其实是我不会

其他题都是哄小孩子的简单题。

SEAINVS

首先考虑一次询问怎么做。。令$a(i,l_2,r_2)$表示$P_j(l_2\le j\le r_2)>P_i$的$j$的个数，那么首先将$a(i,l_2,r_2)(l_1\le i\le r_1)$排序得到$A_0\le A_1\le \dots\le A_{S-1}$，然后答案就是$\prod_{i=0}^{S-1}(A_i-i)$

证明很简单。。因为是求某个01矩阵的积和式，所以按照1的个数最小的那一行展开即可证明

注意到$r_1<l_2$。设逆序对个数为$I$，则$\sum_{i=0}^{S-1}(S-A_i)\le I$，这说明$A$是一个$O(\sqrt{I})$段的分段常数函数，考虑这样求每一段：将$P_{l_1\dots r_1}$和$P_{l_2\dots r_2}$分别从大到小排序，然后将它们归并排序，那么$a(i,l_2,r_2)$就是在$P_i$之前被取出的$[l_2,r_2]$内元素个数。如果我们定义一次操作为将排序后的$P_{l_1\dots r_1}$或$P_{l_2\dots r_2}$中的前某些(一段)元素拿出来，那么$O(\sqrt{I})$次操作之后归并排序就可以完成，且每一次对$P_{l_1\dots r_1}$的操作时我们可以计算这些元素对答案的贡献。

写一个查询“区间$[l,r]$中$<k$的最大元素是谁”的数据结构，主席树轻虐。

复杂度$O(N\log N+Q\sqrt{I}\log N)$。

这种题不会做不要害怕。。只要牢记sereja的智商不会超过你我的智商(误

DISTNUM3

莫队算法

树上带修改莫队，显然可以做到$O((N+Q)N^{2/3})$，至于为什么能过。。问mgch咯

CHEFYODA

垃圾拼题

把能互相移动的点连边，显然大厨能赢当且仅当任意最大匹配包含$(1,1)$，原理参见我的noi2011 game题解

第一条规则：大厨能赢当且仅当$N,M$中有偶数

第二条规则：大厨能赢当且仅当$N,M$都是偶数

那么可以算出大厨赢一局的概率，$0$或$0.5$或$1$，概率为$0$或$1$的情况很好处理，为$0.5$的情况答案就是

$$\frac{\sum_{i=P}^K\binom{K}{i}}{2^K}$$

为了不爆精度，注意到$\binom{K}{i}$可以直接由$\binom{K}{i-1}$推来，维护$\binom{K}{i}$，写成$a\times 2^b(1\le a<2)$的形式就好

INTERVAL

$f_{i,j}$表示以$A[j\dots j+B_{i-1}-1]$为初始局面从第$i$轮开始玩的最终结果。。转移是个Sliding Window，裸的单调队列，复杂度$O(NM)$

MFREQ

我操。。原来看错了所以写了个主席树啊。。然后看了一下。。好像有一个consecutively啊。。等于问的是有没有连续出现这么多次的啊

那么$a_{\lfloor\frac{l+r}{2}\rfloor}$肯定是这个数。。然后看它往左往右走多远即可，$O(N+M)$

我就说怎么这题300+人过。。

GERMANDE

对每个点处理出它为一个州的起点时Zeros赢还是Ones赢

枚举起点是谁，一共有$o_2$种可能，对每种起点直接判断谁赢，复杂度$O(o_1)$

总复杂度$O(o_1\times o_2)=O(N)$

MAKETRI

这题比想象中难。。开始以为所有可能的长度一定组成一个区间，就卡了30min。。反例$N=3,\{1,10,100\}$，$20$就不是合法长度

应该是枚举三角形的另外两条边中较长的那条$a_i$，为了使方案数最多，较短的那条显然取$a_{i-1}$，那么搞出所有$[a_i-a_{i-1}+1,a_i+a_{i-1}-1]$，取区间并就好

mdzz

CHEFAPAR

丢掉前面连续若干个$1$，剩下的序列长度就是需要补交的$100$卢比数量，再看剩下多少个$0$就是需要补交的$1000$卢比数量