Mato is No.1

原题见这里（BZOJ和BSOJ都挂了，真杯具，只能借助RQ了囧……）

难度不是很大，就是特殊情况比较多，比较猥琐（不过本题数据弱，就算不考虑所有的特殊情况也能过7个点）。
首先O(NM)的朴素算法很好想到：枚举K，然后给每个结点编号即可。在编号时，先随便指定一个未编号的点，设它的编号为0，然后遍历所有和它相关联的边（这里可以把原图想象成一个无向图），将这些边的另一个端点编上号即可，中间若某个点的编号出现矛盾，则这个K不合法，否则这个K合法。
然后进行优化：合法的K实际上是有限制的，它必然是某个数的因数，具体来说，对这个图进行DFS，并考察其中所有的跨越边和逆向边，对于跨越边<i, j>，设遍历树中i、j间距离为D，则合法的K必然是(D-1)的因数（因为i和遍历树中j的父结点都有指向j的边，它们的编号应相同，而它们之间的距离为(D-1)）；对于逆向边<i, j>，设遍历树中i、j间距离为D'，则合法的K必然是(D'+1)的因数（因为这里形成了一个环，环的长度为(D'+1)）。这样一来就明显缩小了K的取值范围，再进行枚举，就可以显著缩短时间。

下面是一些极其猥琐的特殊情况：
（1）根据题意，必须是K类每类都有，因此在尝试编号成功（没有发生任何矛盾）后，还要看一下实际出现的编号数目是否等于K，若小于K，同样不合法；
（2）该图的基图可能不连通，此时对于其基图的每个连通块，其编号互不影响，所以要对每个连通块分别统计实际出现的编号数目，设它们的和为SUM，则不大于SUM的K值均合法（只要中间不出现矛盾），因此可以直接得到最大值为SUM，提前结束；不过，这种特判只有在总共实际出现的编号数目小于K的情况下才能进行；
（3）由于考察的是实际出现的编号数目，因此最后求出的最大值、最小值可能小于3，这时应作出如下处理：若最大值小于3，则无解；若最小值小于3，则将最小值改为3。

本题比较猥琐的数据是第4、5、6个点，分别出现了上述的第（1）、（2）、（3）种特殊情况，此外，这三个点建出的图中竟然没有一条跨越边或逆向边！

代码：

     摘要: 【2-SAT问题】现有一个由N个布尔值组成的序列A，给出一些限制关系，比如A[x] AND A[y]=0、A[x] OR A[y] OR A[z]=1等，要确定A[0..N-1]的值，使得其满足所有限制关系。这个称为SAT问题，特别的，若每种限制关系中最多只对两个元素进行限制，则称为2-SAT问题。由于在2-SAT问题中，最多只对两个元素进行限制，所以可能的限制关系共...  阅读全文

多重背包问题朴素时间复杂度为O(NMS)（这里S是所有物品的数量s之和），经过二进制优化后时间复杂度为O(NMlog2S)，这个复杂度已经能够应付大多数题了，但对于某些特别卡时间的题（比如N*M=10⁷的)，仍然会TLE。这时，可以用单调队列优化，时间复杂度降为O(NM)。

首先看一下多重背包问题的朴素转移方程：
F[i][j] = max{F[i-1][j-x*w[i]]+x*v[i]} (0<=x<=s[i], j>=x*w[i])
如果使用滚动数组，忽略i这一维，设w0=w[i]，v0=v[i]，s0=s[i]，得：
F[j] = max{F[j-x*w0]+x*v0} (0<=x<=s0, j>=x*w0)
看上去这和单调队列木有神马关系，因为决策下标（j-x*w0）不是一个整数区间，中间是有间隔的。然而可以发现，这个方程的限制条件“0<=x<=s0，j>=x*w0”，也就是x的下界是max{0, j/w0（下取整）}，当j单调递增时，这个下界也是单调递增的。这满足单调队列优化的条件中的“决策下标的下界单调”……不是，还不能这样说，因为这里的决策下标是j-x*w0，而不是x。
那么怎样才可以把决策下标变为x？

将决策下标按照模w0的余数进行分类，可以分成w0类，分别对应模w0余0、余1……余(w0-1)的情况。这时，上面方程中的所有决策下标j-x*w0都是同一类的。进一步，设q =j/w0（下取整），r=j%w0，则j=q*w0+r，对于某个决策下标j'，设k=(j'-r)/w0，即j'=k*w0+r。显然可以发现，k的取值范围是：k>=0且q-s0<=k<=q，也即k的下界是max{0, q-s0}——随j的单调而单调。
然后，转移方程可以改为（这里把r当成一个已知量了）：
F[q*w0+r] = max{F[k*w0+r]+(q-k)*v0} (k>=0且q-s0<=k<=q)
即F[q*w0+r]=max{F[k*w0+r]-k*v0}+q*v0 (k>=0且q-s0<=k<=q)
设G[k]=F[k*w0+r]得：
G[q]=max{G[k]-k*v0}+q*v0 (k>=0且q-s0<=k<=q)
这个方程已经可以使用单调队列来优化了！

这样可以得出算法：
（1）从1到n，枚举i，建立w[i]个空的单调队列，每个队列的元素都是两个int值：(k, val)，表示转换后下标和决策值(G[k]-k*v[i])；
（2）从0到m，枚举j，得出q、r的值，对于队列r：
【1】删去队首过时（k<q-m[i]）的元素；
【2】F[j]入队（这里的F[j]指上一阶段的F[j]，即F[i-1][j]。因此这一步操作一定要先进行），删去队尾所有决策值val不大于(F[j]-q*v[i])的元素。
【3】取出队首结点，其val值加上q*v[i]后即为本阶段F[j]的值。
最后F[m]即为结果。总时间复杂度为O(NM)。

其实这个是可以推广的，即对于如下形式的转移方程（其中H、G和W均为常量，B[i]为决策下标的下界，随i单调）：
F[i] = opt{F[i-x*H+W]}+G (B[i]<=i-x*H+W<i，x∈N）
都可以用上述的办法进行转化，从而进行单调队列优化。

在没有修改操作时，应用划分树可以在O(MlogN)时间内解决查找区间第K小的问题，但是在引入修改（将原序列中的某个值改为另一个值）之后，划分树就不行了。
这时，需要数据结构联合的思想。
可以观察一下：
（1）区间操作：使用线段树；
（2）修改值（其实是先删除再插入）和找第K小：使用平衡树；
现在这两种操作都有，应该使用线段树+平衡树！
准确来说是线段树套平衡树，即对原序列建立一棵线段树，其中的每个结点内套一棵对该结点管辖区间内的平衡树。

<1>结点类型（结构）： 其中seg_node是线段树结点类型，SBT_node是平衡树(SBT)结点类型。需要注意的是seg_node里面的rt域（root的缩写），它是该结点内套的平衡树的根结点下标索引（因为对于任意一棵平衡树，只要知道了其根结点就可以遍历整棵树）。

<2>建树：
建树是线段树和平衡树一起建。在建立线段树结点的时候，先建立一棵空的平衡树（rt域置0），然后再在平衡树里面逐个插入该结点管辖区间内的所有元素即可；

<3>修改：
修改操作要注意：如果要将A[x]（A为原序列）的值修改为y，则需要自顶向下遍历整棵线段树，将所有包含了A[x]的结点内的平衡树全部执行“删除v=A[x]（这个可以通过真正维护一个序列得到），再插入y”的操作；

<4>找区间第K小：
这个操作极其麻烦。需要借助二分。
设要在区间[l, r]中找到第K小。首先将[l, r]拆分成若干个线段树结点，然后二分一个值x，在这些结点的平衡树中找到x的rank（这里的rank指平衡树中有多少个值比x小，不需要加1），加起来，最后再加1，就是x在[l, r]中的总名次。问题是，设[l..r]中第K小的数为v1，第(K+1)小的数为v2（如果不存在的话，v2=+∞），则[v1, v2)内的数都是“第K小”的。因此，不能二分数字，而应该二分元素。设S[i]为原序列中第i小的数，二分i，然后在根结点的平衡树中找到第i小的即为S[i]，再求其名次，这样直到找到总名次为K的元素为止。问题还没完，序列中可能有元素的值相同，这时可能永远也找不到第K小的（比如序列1 2 3 3 3 4 5，K=4，若“序列中比x小的元素总数+1”为x的名次，则永远也找不到第4小的），因此，若这样求出的“名次”小于等于K，都应该将下一次的左边界设为mid而不是(mid+1)，而“名次”大于K时，该元素肯定不是第K小的，所以下一次右边界设为(mid-1)。

代码（本机测最猥琐数据4s以内，交到ZJU上TLE，不知为什么，神犇指点一下，3x）：