codechef AUG16

这几天在外面旅游。。看了一下题目感觉好难。。难题都不会做，简单题不都会做，而且还没时间打

玫瑰彩虹大爷又出题了。。看到题目就感受到了深深的恶意。。还有一个题叫GOODPROB是什么鬼

CHCHCL

打表找规律，$nm$是偶数就好

CHEFRRUN

每一个箱子的下一个是确定的，就是一个基环内向森林。把环上的节点都找出来就是了。

MAXGRID

令$f(l)$为第一问的答案，那么二分查找可以求出第二问答案，复杂度乘以一个log。

那么考虑求$f(l)$，枚举$x,y$表示正方形左上角，不过复杂度太高会T。

辣么我们只枚举$x$，令$a_i$为$y=i$时正方形内权值和，发现我们需要求的只是$a_i$的最大值。

$x$递增的时候，一些$a_i$会改变。设老的$x$为$x_0$，对每个$x=x_0$的点$(x_0,y)$，它对$(y-l,y]$有负的贡献，贡献值为点权；对每个$x=x_0+l$的点$(x_0+l,y)$，它对$(y-l,y]$有正的贡献，贡献值也是点权。

我们需要动态维护$a$数组，支持区间加法和全局max。线段树即可。

复杂度$O(n\log n)$。考虑到第二问还有一个二分答案，总复杂度$O(n\log^2 n)$。

CHAHG

只考虑第一种情况的话。。就有$n-1$个一元一次不等式，取解集的交就好。

只考虑第二种情况同理。

然后把两个答案合并，注意一种特殊情况就是两个答案区间相邻的时候要合并成一个。

这题我拍了。

复杂度$O(\sum n)$。

SHAIKHGN

艹，这个题想了很久，我智商捉急啊

对每个$0\le l\le 31$，预处理$f_{l,i}$为一个bitmask表示$i$收到笑话后第$2^l$分钟哪些人收到了笑话。

$f_{0,i}$是$i$的所有出边，$f_{l,i}=OR_{j\in f_{l-1,i}}f_{l-1,j}$。预处理的复杂度是$O(\frac{N^3\log k}{w})$，其中$\frac{1}{w}$表示压位。

询问的时候，设询问$x,k$，那么把$k$二进制分解为$2^{a_1}+2^{a_2}+\dots+2^{a_p}$，询问的时候枚举$i$可以维护$2^{a_1}+2^{a_2}+\dots+2^{a_i}$秒后哪些人$S$收到了笑话。加入一个$2^{a_{i+1}}$的时候，把$S$变成$OR_{j\in S}f_{a_{i+1},j}$。复杂度$O(\frac{N^2\log k}{w})$。

CHEFTRE

制杖题。玫瑰彩虹的代表作(大雾)。

首先考虑序列上的版本，为了应付2操作我们显然需要一个hash。。判断相等就直接看hash是否相等就好。

考虑3操作，直接上可持久化AVL显然是可以的。1操作也就很简单了，2操作也就是维护哈希而已。

问题被搬到了树上，显然是要树链剖分。。只是要多资瓷一个操作，就是翻转一段区间。

然后码码码就好了。复杂度$O(N+Q\log^2 N)$。哦对了还要拍拍拍。。

好怀念上个月的cc，最难题1k，最码题3k。。

ps.这题翻译有问题。。“reverse”被翻成了“取反”。。我当“negate”做了很久。。鈤。。不过这样就只用搞两个询问了，询问$1$直接变成询问$3$，参数为$u,v,v,u$就是。

pps.这题要垃圾回收。。我服了玫瑰彩虹。。不过由于有用的节点其实只有$N$个，所以空间复杂度开到$O(N)$都没事。并且，回收节点的均摊复杂度显然是$O(1)$。

GOODPROB

这么早就说它是好题，会不会给人一种硬点、钦定的感觉?

首先考虑一个问题：要求维护一个多重集，支持

• 插入一个数，数的范围$[0,2^{2a})$
• 给出$x(0\le x<2^{2a})$，求集合内有多少个数$p$满足$x\text{ and }p=x$。

令$f[i][j]$表示集合中这样的数的个数：把它看成$2^a$进制的两位数，则高位是$i$，低位$k$满足$k\text{ and }j=j$。插入一个数的时候找出所有满足条件的$j$插入；询问的时候设$x$的高位是$x_0$，低位是$x_1$，枚举$i$满足$i\text{ and }x_0=x_0$，求$f[i][x_1]$的和即可。一次操作复杂度为$O(2^a)$，相当于根号级别。

同理考虑另一个问题：要求维护一个多重集，支持上面两个操作，只是把第二个操作中的$x\text{ and }p=x$改成$x\text{ and }p=p$。令$g[i][j]$表示集合中这样的数的个数：把它看成$2^a$进制的两位数，则高位是$i$，低位$k$满足$k\text{ and }j=k$。剩下的部分跟上面算法几乎完全相同。

考虑笛卡尔树。然后就变成一个点的左子树$T_l$，右子树$T_r$，从$T_l$中选出$L$，从$T_r$中选出$R$使得$L\text{ and }R=L$或$L\text{ and }R=R$求方案数。假设$|T_l|\ge |T_r|$，且已经维护好了$T_l$这个多重集的$f$和$g$，那么把$T_r$中的数一个一个拉出去询问就可以得到答案；为了得到整个子树的$f,g$我们需要把$T_r$中的数一个一个插入$T_l$的$f,g$结构。这样复杂度为$O(|T_r|\sqrt{A})$，其中$A$是数的大小。

这个复杂度就是启发式合并了。。很容易做到$O(N\log N\sqrt{A})$。卡常数秘诀：

• 我们肯定是用挂链哈希来存所有的$f,g$的值。调整哈希函数(一般用$h(x)=x\bmod p$的话调$p$就好)。
• 在遍历所有$a\text{ and }b=a$的$a$时候是这样的：
  for (a=b;a;a=(a-1)&b) process(a); process(0);
  遍历所有$a\text{ and }b=b$的$a$也差不多。
• 反正我卡到随机数据1.6s之后就交了。。cc上好像跑得很快。

CHEFCRUN

假设第一步往左边走，右边同理.。讨论讨论就好。

• $s$走到$t$，过了$t$之后掉头。我们走过的路程是$s$到$t$的路程加上两倍$t$开始且不到$s$的最小前缀。
• $s$走到$t$之前掉头，从$t$的后面绕到$t$。可能会经过$t$然后向前走，走到某个地方掉头后回到$t$。我们走过的路程是一整圈的路程加上$s$到$t$的路程减去$s$到$t$的最大连续子段和。

时间复杂度$O(N)$。

TRICONT

首先你要发现一个性质：三角形能包围住房子，当且仅当原点到三角形三顶点的向量满足，任意两个都在剩下那一个的两侧。

对于一个向量$i$，记严格在它左边的向量个数为$l_i$，严格在它右边的向量个数为$r_i$。

然后思考：给出$n$个点怎么求答案。对于每个向量其实只需要记录其极角，极角排序之后二分一下就能求出$l,r$。我们只要求出不存在共线向量的三元组个数(这里其实省略了超级多的细节。。因为后面的柿子并不完全是不共线的，多算了【两个同向共线和一个不共线】这种情况)，减去$\frac{1}{2}(\sum_{i=1}^N(\binom{l_i}{2}+\binom{r_i}{2}))$就好。后面那个柿子表示有两个向量在另外那个的同侧的情况，每种情况被算了两遍所以乘以了一个$\frac{1}{2}$。

考虑动态维护这玩意，只要用平衡树以极角序维护向量的顺序，插入一个向量$v$的时候，首先找出逆时针区间$(v,rev(v))$，然后把这个区间的$r$都加$1$，这个区间的大小作为新向量的$l$；然后找出顺时针区间$(v,rev(v))$，把这个区间$l$加$1$，区间大小作为新向量的$r$；最后把$v$插在合适的位置即可。

复杂度如果我没算错应该是$O(N\log N)$，算法是在线的。我还说为什么要强制在线，原来是强迫我们写平衡树。。否则线段树应该是可做的。

EBOLA

这题很良心。。不像有的cha题做都做不得/看都看不懂。。

1.退火。。对答案进行退火

2.退火。。对于一个排列$p$我们贪心，每次给$p$中最靠前的、没接种疫苗也没感染的点进行接种。对$p$退火

2的效果比1要好些吧，如果不好就是写萎了→_→2能拿80+分哦

讲真。。这场比赛的四大天王MAXGRID,GOODPROB,CHEFTRE,TRICONT都是垃圾数据结构题。。TRICONT还好一点，稍微有点思维难度