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)。