几乎全世界秒杀的题，我一直没看懂题目…
于是开着3个坑，全线卡题…
后来把一题比较卡常数的题目搞了以后…发现已经是122分钟了…- –
然后我继续纠结全世界人秒杀的题目…突然想起有forum这种东西可以提问= =…圡死了。
于是把这3个坑都水掉…
由于全世界人都秒杀的题至少搞了纯的2个小时…于是接着的一个简单但题意模糊的dp写不完了…
结果当然是挂了…
review一下没有泄露到题目，于是就这样…希望接下来没那么圡.
作者存档：edward_mj
记CF爆0
AB都是改一个语句就Y了啊，卡在pretest死活YY不出bug。
这寂寞水平在DIV II都要掉一大把rating啊。有木有啊！
几天疯玩迎来如此寂寞的一场CF也是情理之中哎
额，睡觉去、
[HDOJ2295 Radar]【重复覆盖模板】
[ZOJ3209 Treasure Map] DLX解决精确覆盖问题中我的一个错误>.<
HHGG出的题T_T。
本身题目没啥好说的。很容易转化为精确覆盖。
但是我之前的DLX模板超时了。
好吧，那个在HUST1017上跑了4S的模板果然是不能用的。
然后，我照着hh(the small one)的模板YY出意思然后写了一个。HUST上…还是跑了1500+MS.这题还是TLE。
我记得之前那篇CLJ留言鄙视说暴力开指针都600+MS…
我再看了好多遍，觉得和hh的没啥区别嘛…为啥人家说200+MS
好多遍好多遍以后…我突然看到了一个不一样。
hh的：
回溯部分：
for (int j=L[i];j!=i;j=L[j]) resume(Col[j]);
resume函数部分：
for (int i=U[col];i!=col;i=U[i])
for (int j=L[i];j!=i;j=L[j])
我的
回溯部分：
for (int j=R[i];j!=i;j=R[j]) resume(Col[j]);
resume函数部分
for (int i=D[col];i!=col;i=D[i])
for (int j=R[i];j!=i;j=R[j])
然而，我的其实犯了一个错误。
Dancing Link其实必须按照删除的先后顺序，依次恢复的。
比如删除的顺序是i,j，恢复的顺序就应当是j,i。举个例子就能知道原因
HUST的1017上
在for (int j=L[i];j!=i;j=L[j]) resume(Col[j]);这种方式下。无论resume函数里随便用ULDR都可以240MS左右AC。
而for (int j=R[i];j!=i;j=R[j]) resume(Col[j]);这种方式下。resume函数里如果用D可以1500MS AC。然后，如果是U的话就runtime error了。可见这种方式确实是错误的>.<
恩，终于搞了一个能用的精确覆盖模板了。
以后把mat和Num建好，一刷就好了
需要注意的是代码里，为了方便和速度，把二维点映射到一维上了。
Codeforces Beta Round #75 Div 1 (D无思路..)
A
就是加个Next[i][26]的数组来转移，基本上理清题意以后，5分钟内都出想法了吧
B
按a[i]排个序，然后顺序扫描，看最后的是谁就行了。= =脑抽写了线段树，本身线段树的话也不会写多久，但是又跑去尝试新写法。。。然后就写了巨久。。。
C
这个，看了watashi的代码，想了一下。
首先就是如果一个边集能符合题目，充要条件是每个点度数为偶数。
每当添加一条边连接两个不连通的块时，不可能会存在新的欧拉回路通过这条新加的边。所以显然答案不变。
而当添加一条边连接了两个本已连通的块时，假如是一开始只有一条边，答案必然还是0，然后接下来，每次出现这样的边，ans+=2^(k-1)。其中k代表这是第k条连接已连通的两个块的边。
为什么会这样呢？从结论往回看。。。本身的ans是不包含新加边的方案数，而2^(k-1)是包含新加边的方案数。
假设用一个mask代表那k-1条边的使用情况，那么极有可能是每个mask都对应了一种且仅一种方案。
继续YY
除去所有这k条边以后，其实图上是几棵树组成的森林！
然后假定现在这个第k条必取、、、然后前面k-1条组成的每个mask确实就唯一地对应了一种方案。
也就是说假设mask确定，我们森林边的取舍情况也就确定了。这个自行YY一下，明白过来会发现很显然
D
不会>.<
求指导。
E
这种放在省选NOI什么的就是送分题，裸考线段树
就是建一棵线段树，然后线段树每个节点里套一个线性表，以前我写这种比较疼，现在用vector简直好写到爆。。。
然后这个线性表的内容嘛，就是随着t的增长，看看这个线段里的老大是谁。
大概就是表示这样更替情况的一个队列。
然后嘛，假如区间里有i,j满足a[i]<=a[j] && b[i]<=b[j]，那么i肯定就没用了。
剔除这些以后，按a[i]递减排序，变成了b[i]递增的序列。(我的Code中的Select())
然后就是利用决策单调弄这个队列了。由于b[i]递增，所以随着t的递增，必然是越来越倾向于选后面的。
我们现在构建一个栈，使得栈内元素满足Meet_Time(Q[i],Q[i+1])>Meet_Time(Q[i],Q[i-1])，其中Meet_Time(x,y)就是使得a[x]+b[x]*t=a[y]+b[y]*t的t值。
这个很容易扫一遍得出来。(我的Code中的Form())
构建完以后，对于每个询问l,r,t。
直接在线段树里找到l,r对应区间，然后可以三分得当前的t对应的老大是谁(我还是写得二分，Code中的Get_Best())。
按Solution Size排我的还是比较靠前的= =，我也觉得写得还是比较清楚，于是推荐一下。
时间复杂度O(n lg^2 n + q lg ^2 n)
【CODE】http://ideone.com/Aga48
【update】
按照猛犸学长的指示，构造部分可以通过归并排序避免那个sort的调用。
后面可以先对答案排序，然后用指针滑的方法得到均摊的n lg n。
于是总时间复杂度可以做到O(n lg n + q lg n)。