[关闭]
@Cyani 2020-02-03T16:09:44.000000Z 字数 13096 阅读 1010

Codeforces 好题 by zzx

OI

2

欢迎来到Codeforces小课堂第3期，我是consecutivelimit，今天讲的题目比较简单：
http://codeforces.com/contest/966/problem/F
题目大意：给一个上下界网络流图，每条边 的上下界 都是关于全局变量 （） 的一次函数，保证 时恒有 ，问均匀随机取一个 ，图中存在可行流的概率。

判断是否存在上下界可行流，可以新建一个源S和一个汇，然后对每条边 ，连容量为 的边 ，并将 的上界改为 ，下界改为 ，求新图的 最大流是否满流。

这样做的原理相当于预先把所有边的上界先流满，然后用一个最大流处理残余的流量。
最大流满流这个条件似乎不好直接入手，尤其是当所有 都是关于t的一次函数的情况下。这时候，我们需要一个定理——

最小割最大流定理！

嗯对，最大流等于最小割，也就是 ，其中 是点集 的子集， 表示满足 ， 的边 的容量之和。于是满流的条件是 。（QQ空间似乎会把空集符号吃了）

因为每条边的容量都是关于 的一次函数，所以对于一个 ， 也是关于 的一次函数， 则是一个上凸的半平面交，并且不会出现在 轴上方，和 轴重合的部分一定是一段区间。我们要求的是该函数与t轴的重合部分长度。
令 ，显然对于，可以通过一遍网络流把 求出来。如果存在 ，，，那么不难通过二分法，找到最大的 使得 ；如果 ， 也类似。

然而现在的情况是可能 ，，且满足 的 区间非常短，通过猜测 的方法很难找到满足 的 。怎么办呢？

注意到函数是上凸的，所以利用导函数 会很方便：对于 ， 的情况，令 ，如果 ，则令 ，否则令 ，这样就可以二分了。至于导函数 是啥？就是
对于 ，跑网络流把最小割的方案 求出来之后，算一下一次项系数和咯。

这样，如果满足 的 存在，通过二分一定能找到满足此条件的 ，然后对左右两部分二分出满足 的 区间的左右端点，进而得到答案。

怎么样，是不是很简单？当然可能要注意精度问题就是了。
（讲个笑话，这场比赛我还是因为卡前面的题没开这题）
代码： http://codeforces.com/contest/966/submission/41638894

那么今天consecutivelimit的Codeforces小课堂第4期就开始了。
链接： http://codeforces.com/contest/997/problem/E
题目大意：给一个1..n的排列p[1..n]，q次询问某个区间[l,r]内有多少个子区间[l',r']（l≤l'≤r'≤r），满足p[l'..r']出现了所有[min{p[l'..r']},max{p[l'..r']}]内的整数。n,q≤120000。

先考虑一个询问怎么做，这是一个经典问题，可以用分治或者线段树来解决。
csl在考场上尝试将分治做法扩展到多组询问，结果失败了，考后又推了一会儿才推出一个根号log的做法，很不优秀。
先剧透一下，这题复杂度是O((n+q)logn)的哦~
于是我们换一种思路——“枚举右端点，维护左端点”。
设f(l,r)为将p[l..r]排序后，形成了多少个连续段。显然f(r,r)=1，当l f(l,r)=f(l,r-1)+1-[p[r]-1∈p[l..r-1]]-[p[r]+1∈p[l..r-1]]
按r=1,2,...,n的顺序枚举r，用一个数据结构维护f(,r)，可以发现，r增加1，f(,r)的变化是一段区间加1，一段区间减1，不难联想到线段树。可是我们要求的是满足f(l,r)=1的l的个数，怎么办呢？
注意到如果存在f(l,r)=1，那么1一定是f(l,r)的最小值，于是用线段树维护区间最小值以及最小值个数即可。总复杂度O(nlogn)。
不错，我们接着考虑q个询问的做法。对于一个询问[l,r]，通过以上线段树做法，我们可以O(logn)得到满足l≤l'≤r的合法区间[l',r]个数，却难以直接得到l≤r'≤r的合法区间[l',r']个数。当然，脑洞大开一下总是没有什么坏处的——
“把线段树做个前缀和？”
我们可以这么大胆想象：设α(l,r)为一个列向量，除了α(l,r)[f(l,r)]=1以外，其余所有α(l,r)[i]=0。然后用线段树维护α(*,r)的区间和，(α(l,r)+α(l+1,r)+...+α(r,r))[1]就是满足l≤l'≤r的合法区间[l',r]个数。现在给α(l,r)新增一维α(l,r)[0]表示l这个位置的所有历史版本的α(l,r')[1]（r'≤r）之和，那么每个操作都可以表示为区间乘一个矩阵（以n=3为例）：
区间加1（矩阵记为P）：
1 0 0 0
0 0 0 0
0 1 0 0
0 0 1 0
区间减1（矩阵记为M）：
1 0 0 0
0 0 1 0
0 0 0 1
0 0 0 0
更新前缀和（即α[0]+=α[1]，矩阵记为A）：
1 1 0 0
0 1 0 0
0 0 1 0
0 0 0 1
这样就可以用线段树描述前缀和操作了。当然，实现的时候显然不能用矩阵，否则比暴力还慢。。。
只有一次询问的情况相当于只有矩阵P和M，存储时只需存储向量中第一个非0位置及其值（其实就是f(l,r)的最小值及最小值个数），线段树标记也只记录P和M的次数差（其实就是区间加的标记，显然不可能爆出上下界）。
为了处理多次询问，需要在每个r处理完之后把[1,r]区间乘上矩阵A，于是现在的线段树结点标记长这样：P^?*M^?*A*P^?*M^?*A*P^?*M^?...，就是把向量平移若干位，然后把1位置上的数加到0位置，再平移若干位，再加……
同样，对于向量，只要存α[0]以及除α[0]外最低的非0位置及值。考虑如何把标记进行简化存储。显然，只要记录平移到最低点的信息（即后缀M的个数减P的个数最大的A，只需记录一个A后面M的个数减P的个数的最大值，及这样的A的个数），就能把标记简化成P^?*A^?*M^?的形式。
那么线段树做前缀和就搞定了，问题也就得以解决了，复杂度O((n+q)logn)。
代码（如果有问题欢迎hack）： http://codeforces.com/contest/997/submission/40677876

欢迎收看Codeforces小课堂第5期，我是consecutivelimit，今天我们讨论的又是一道数学题哦。
链接： http://codeforces.com/contest/947/problem/E
题目大意：随机变量x的值域为{0,1,...,N}，给出x的分布列，问进行M次将x变为{0,1,...,x}内的均匀随机数之后，x的分布列。输入和输出均对998244353取模。N≤10^5，M≤10^18。

先讲一个NOIP难度算法：设f(i,j)为经过i次操作之后，x=j的概率，则f(i,j)=Σ[k≥j]f(i-1,k)/(k+1)，f(0,j)就是输入的x的分布列，f(M,j)就是答案分布列，复杂度O(NM)（前缀和优化）。
可是M是10^18级别，做一遍都炸了，怎么办？
好的，再讲一个省选级别的算法：注意到f(i,)是f(i-1,)乘上这样一个矩阵A（以N=3为例）：
1 1/2 1/3 1/4
0 1/2 1/3 1/4
0 0 1/3 1/4
0 0 0 1/4
所以f(M,*)=A^M*f(0,)，用矩阵快速幂计算，复杂度O(N^3logM)。
现在M的瓶颈是没了，但出现了一个新的瓶颈N^3，怎么办？
不妨找一找这种变换有啥性质。
一种思路是把它转化成分层图的路径来考虑，嗯，本csl考场上就是这么想的，以为它就是一个M+1层网格图从第一行到最后一行的路径条数，可惜这样概率就不均匀了，于是辛辛苦苦写完FFT最后才发现它是错的。。。
发散一下思维想想还有没有别的转化途径。如果不是矩阵乘法，而是多项式乘法，有什么更好的做法吗？对，把f(x)乘上g(x)，就是先把f(x)和g(x)做一个DFT，然后把f(x)的每一项对应乘上g(x)的每一项，最后再IDFT回来。那么，f(i,j)=Σ[k≥j]f(i-1,k)/(k+1)这个变换，能不能认为是先对f(i-1,)做一个变换，得到一个序列[a(i-1,0),a(i-1,1),...,a(i-1,N)]，接着每一项乘一个常数b[i]，变成[a(i-1,0)b[0],a(i-1,1)b[1],...,a(i-1,N)b[N]]，再把这个序列逆变换回来得到f(i,)呢？
如果存在这样的变换，就只要对f(0,)做这样的变换，再乘上b[i]^M，得到序列[a(0,0)b[0]^M,a(0,1)b[1]^M,...,a(0,N)b[N]^M]，再把它逆变换回来就好了。
开始尝试这个构造吧！
其实就只要提取出f(i,)中的N+1个线性组合a(i,0),...,a(i,N)，每个线性组合使得无论f(i-1,)如何取值，a(i,j)都是a(i-1,j)的常数倍，这个常数就是b[j]。
显然，由于f(i,N)=f(i-1,N)/(N+1)，很容易提取出一个线性组合，就是f(i,N)单独一项，即：a(i,N)=f(i,N)，并且常数b[N]=1/(N+1)。
尝试构造下一个组合。由于f(i,N-1)=f(i-1,N-1)/N+f(i-1,N)/(N+1)，所以f(i,N-1)并不是f(i-1,N-1)的常数倍，但可以构造一个系数k，使得f(i,N-1)+k*f(i,N)是f(i-1,N-1)+k*f(i-1,N)的常数倍，由于
f(i,N-1)+k*f(i,N)=f(i-1,N-1)/N+(k+1)/(N+1)*f(i-1,N)
所以必有常数b[N-1]=1/N，于是(k+1)/(N+1)=k/N，得k=N。这样就得到了下一个线性组合：a(i,N-1)=f(i,N-1)+N*f(i,N)，并且常数b[N-1]=1/N。
类似地，我们可以构造第三个组合。设这个组合为f(i,N-2)+k1*f(i,N-1)+k2*f(i,N)=f(i-1,N-2)/(N-1)+(1+k1)/N*f(i-1,N-1)+(1+k1+k2)/(N+1)f(i-1,N)=bN-2，得b[N-2]=1/(N-1)，k1=N-1，k2=N(N-1)/2。
以此类推，可以归纳得到每个线性组合（j=0,1,...,N）：
b[j]=1/(j+1)
a(i,j)=Σ[k≥j]C(k,j)f(i,k)
很棒，我们已经有一个O(N^2+NlogM)的做法了！
1、根据a(0,j)=Σ[k≥j]C(k,j)f(0,k)将输入的分布列转化为序列a(0,)；
2、令a(M,j)=a(0,j)/(j+1)^M；
3、利用二项式反演逆变换f(M,j)=Σk≥j^(k-j)C(k,j)a(M,k)，得到答案分布列f(M,*)。
至于最后一步的优化，也很简单了，就是把第1步和第3步的变换用FFT优化就行了。以第1步为例：
a[j]=ΣC(k,j)f[k]=Σk!f(k)/j!(k-j)!
a[j]/j!=Σk!f(k)/(k-j)!
看出来a[j]/j!是j!f(j)和1/(-j)!的卷积了吗？FFT就好了。第3步也类似。
这样我们就以O(NlogN+NlogM)的复杂度解决了本题！完结撒花！

6_1
6_2
6_3

7_2
7_1
7_3

没错，今天的CF小课堂第8期并没有鸽！虽然题目很简单就是了。
链接： http://codeforces.com/contest/1037/problem/H
题目大意：给定字符串s和q个询问，每次询问给出整数1≤l≤r≤|s|和字符串x，要求输出s[l..r]的所有子串s[l'..r']（l≤l'≤r'≤r）中字典序比x大的最小的一个。|s|≤10^5，Σ|x|≤2*10^5。

这类子串问题一般都可以尝试用后缀数组解决。
首先，建出s的后缀数组sa[]，然后对于每个询问，将x在后缀数组上二分，可以O(|x|log|s|)找到后缀数组中，第一个字典序比x大的后缀sa[i]。
考虑先选一个字典序大于x的后缀t，再选t的一个字典序大于x的最短前缀t'作为答案，不难证明t'去掉最后一个字符后是x的前缀。
显然，后缀数组中，在sa[i]前面的后缀sa[j]（j 问题来了，如何快速再后缀数组中找到满足sa[j]≥l，sa[j]+LCP(x,s[sa[j],n])≤r的最小的j呢？
直接考虑似乎不太容易……？不，一定是想复杂了。
p=LCP(x,s[sa[j],n])可以暴力枚举！
我们暴力枚举这个p，由于后缀数组中这个LCP就是sa[i]到sa[j]的height最小值，它是关于j递减的，所以满足LCP(x,s[sa[j],n])=p的j一定是后缀数组中的一段连续区间，可以用单调栈二分或者线段树找出这个区间。
接着需要求区间内最小的j使得l≤sa[j]≤l+p。可以直接二分j，然后裸上二维数点，用可持久化线段树做，这样询问复杂度是O(|x|log^2n)。可以做到更好的复杂度吗？答案是肯定的。
按l递减的顺序，用线段树维护sa[j]≥l的位置集合，然后在线段树上二分找出sa[j]的最小值不超过l+p的最小的j。这样询问复杂度就是O(|x|logn)了。
最后，总复杂度O((n+Σ|x|)logn)。
代码： http://codeforces.com/contest/1037/submission/42409646

大家好，我回来了。。。这里是上午下午都在训练累到爆的consecutivelimit。。。Codeforces小课堂第9期开始啦。
链接： http://codeforces.com/contest/1007/problem/D
（画外音：CSL你又拿你考场上没调出来的题来毒害大家了？）

（CSL：诶，是我水平太差而不是题目毒瘤啊）

题目大意：有一棵n个结点的有根树，还有m只蚂蚁，每只蚂蚁有2条备选路径(a[i],b[i])和(c[i],d[i])，你需要给每只蚂蚁选其中一条备选路径，使得不同蚂蚁的路径没有公共边。判断是否有解，如果有解给出一组解。n≤10^5，m≤10^4。
暴力做法是2^m枚举每只蚂蚁选哪条路径，然后判断是否存在一条边被两条路径覆盖。
用x[i]∈{0,1}表示第i只蚂蚁选的路径，容易发现，如果存在一条边同时在第i只蚂蚁的路径a和第j只蚂蚁的路径b上，那么x[i]=a和x[j]=b不能同时满足，当所有约束都满足时就是一个合法的方案。
这样就得到了一个2-SAT模型：枚举两只蚂蚁的各一条路径i,a和j,b，如果相交，就新建约束“x[i]=b或x[j]=a”，用强连通分量算法求解2-SAT即可。
该2-SAT的边数为O(m^2)，显然既会TLE也会MLE。
我们来优化建图。一种显然的思路是：枚举一条树边e，把过e的蚂蚁路径都取出来，然后两两建一个约束。
设过边e的路径有k条，第i条是第p[i]∈{1,...,m}只蚂蚁的第q[i]∈{0,1}条路径，用(x[i],a)表示2-SAT图中代表x[i]=a的结点，那么我们需要对所有的i≠j，建立约束“x[p[i]]=1-q[i]或x[p[j]]=1-q[j]”。
这也是本人考场上的想法。
至于怎么建，我们建一个辅助变量z[e]，当至少有一个x[p[i]]=q[i]成立时，z[e]=1，当z[e]=1时，所有x[p[j]]=1-q[j]成立，即2-SAT中这样建立约束。注意咯，2-SAT要记得建对称边：
(x[p[i]],q[i])->(z[e],1)
(z[e],0)->(x[p[i]],1-q[i])
(z[e],1)->(x[p[j]],1-q[j])
(x[p[j]],q[j])->(z[e],0)
这就只需要一个点和一个子树内所有结点连相同方向的边了。求出树的DFS序，设e子树的DFS序区间为[l,r]，那么需要把一个点和“一端在[l,r]内，一端小于l或大于r”的所有路径连边。
显然可以用可持久化线段树优化建图：将路径按端点DFS序加入可持久化线段树，加到l-1以后往[l,r]就可以连向一段在[l,r]内，一端小于l的路径。另一端大于r的处理方法类似。复杂度O((n+m)logn)。
对，看起来是一个log，但常数巨大。

怎么样，是不是做完了啊？

讲个故事，本人在考场上看这题的时候只剩不到1h了，想到做法以后赶紧写，好不容易写完了，然后一直调不过样例。
考后继续调又调了好久，最后发现……
这个做法！
根！
本！
就！
是！
错！
的！
为啥呢？回到一开始的连边，对于树边e，(x[p[i]],q[i])->(x[p[j]],1-q[j])的要求是i≠j，否则自相矛盾。
可是新建一个点z[e]让其它点和它相连，相当于把i≠j这个限制去掉了。
这就很尴尬了，一时不知道怎么改。。。
看来要换思路了，可能还得用每条链去和除它以外的其它链连边，而不是基于中间结点两两互连。
考虑对于第i只蚂蚁的第j条链u-v，如何找出和它相交的所有链？
对于另一条链u'-v'，令a=LCA(u,v)，a'=LCA(u',v')，那么当a和a'没有祖先关系时，一定不相交；当a是a'的祖先时，只需a'->u'或a'->v'的第一条边在u-v上；a'是a的祖先情况类似；a=a'时，按任意一种处理。
这样，不妨把所有链u-v拆成两条有祖先关系的链a-u和a-v，再考虑建2-SAT。
对于每条链a-u，取出a->u的第一条边e，令过e的第i条链对应的约束为(x[p[i]],q[i])，就然后把a-u链对应的约束(x[p[i]],q[i])和过e的所有链对应的约束(x[p[j]],q[j])（j≠i）都连一组对称边：
(x[p[i]],q[i])->(x[p[j]],1-q[j])
(x[p[j]],q[j])->(x[p[i]],1-q[i])
现在就可以直接按DFS序建可持久化线段树，将所有链a-u按照a的DFS序从小到大依次加入可持久化线段树，和边e（子树DFS区间[l,r]）的子树连边时在DFS序小于l的链加入完之后的可持久化线段树版本上连区间[l,r]的边，即可和过e的所有链相连。
这样就完成对每条链往可持久化线段树的区间连边了。复杂度O(mlogn)，常数非常大。
代码（如果有问题欢迎hack）： http://codeforces.com/contest/1007/submission/41623820

这里是用一点残存的spirit写题解的consecutivelimit。
【Codeforces小课堂第10期】
题目链接： http://codeforces.com/contest/1012/problem/F
题目大意：你准备去N个国家旅行各一次，第i个国家的旅行计划在第s[i]天早上出发，第s[i]+len[i]-1天回家。你有P本护照，在每次旅行前必须让其中一本护照办理该国的签证，如果在第x天开始对某本护照办理第i个国家的签证，那么第x天不能在旅行，且第x+t[i]天中午可完成签证拿回该护照（允许在旅行时拿到）。判断旅行计划能否完成，如果能，给出一种签证方案（时间及哪本护照）。N≤22，P≤2。
分析：
实际上我们需要对每个旅行确定一个护照p[i]和签证开始时间x[i]，使得：
（1）x[i] （2）不存在j使s[j]≤x[i] （3）不存在j使a[i]=a[j]且x[j]≤x[i] （4）不存在j使a[i]=a[j]且x[i]≤s[j]≤x[i]+t[i]。
先考虑P=1怎么做。
对于a[i]相同的i，如果x[i]之间的相对大小关系一定，那么只要从小到大贪心确定x[i]即可。
因为N的范围只有22，所以不妨用状压DP解决排列问题。
令f(S,t)表示能否在t天内完成S集合内的旅行？
可惜t的范围太大，不行。但我们发现这样的状态实在是太浪费了，不如改改:
令f(S)表示完成集合S内的旅行，最晚的旅行的结束时间的最小值。
那么f(S)=min{t(f(S-{i}),i)|t(f(S-{i}),i) 至于t怎么求呢？首先上面式子中超过s[i]就舍去满足了（1），同时i安排在之前所有旅行之后，满足了（3）。
因此只需在x之后没有旅行的时间段内选一端长度至少为t[i]+1的，就能满足（2）和（4）。
这个直接做是O(2^N*N^2)的，不过可以优化：用顺推式更新f(S)→f(S∪{i})，i按照t[i]从小到大更新，这样就能单调性扫来更新DP值了。当f(U)<+inf时说明有解，复杂度O(2^N*N)。
再考虑P=2怎么做。
对于大多约束，可以把旅行分成两个护照，然后每个护照负责的旅行都要满足上述条件，也就是f(S)定义为在其中一个护照上处理完S集合的旅行的最小时间。
所以仍然用顺推式转移，对于每个S，将第f(S)天以后的天去掉S中的旅行时间段以后剩下的段提取出来，那么转移仍然可以按t[i]从小到大的顺序进行f(S)→f(S∪{i})的更新。
那么当f(S)<+inf且f(U-S)<+inf时，把S放护照1，U-S放护照2是合法的。
时间复杂度仍然是O(2^N*N)。
代码： http://codeforces.com/contest/1012/submission/41557815

【Codeforces小课堂第11期】
题目链接： http://codeforces.com/contest/1023/problem/G
题目大意：n个湖由n-1条河连通，每条河连接两个湖，河有长度l[i]，一只鱼游过河i需要l[i]天，在一段时间内，给出k个形如"d[j]天至少有f[j]只鱼在湖p[j]内"的描述，问整个系统至少有多少只鱼。
分析：
首先，看到题目，不难建出一个网络流图：
· 对于每个树上结点i，建一条容量无穷大的链S→v[i,1]→v[i,2]→...→v[i,2D]→T，其中D=max{d[i]}；
· 对于每条树边(i,j)，对所有k连容量无穷大的边(v[i,2k],v[j,2(k+l(i,j)-1)]),(v[j,2k],v[i,2(k+l(i,j))-1])；
· 对于每个1≤i≤k，对边(v[p[i],2d[i]-1],v[p[i],2d[i]])设置流量下界f[i]。
求下界最小流就是答案。
下界最小流显然可以转成最大流来做：考虑判断是否有答案ans≤x，只需连容量为x的边(T,S)，新建源S'和汇T'，然后对每个1≤i≤k去掉(v[p[i],2d[i]-1],v[p[i],2d[i]])的下界并新建容量为f[i]的边(S',v[p[i],2d[i]]),(v[p[i],2d[i]-1],T')。那么当S到T的最大流为Σf[i]时说明满流，即ans≤x。
很好，已经迈出了解决这题的第一步。
下一步应该是被用烂的一个套路了：根据最小割最大流定义，考虑把每条链S→v[i,1]→v[i,2]→...→v[i,2D]→T切成两部分，前一部分属于T'集，后一部分属于S'集，那么问题转成了这么一个玩意：
· 给每个点v分配一个整数x[v]，使得对每条边(u,v)，2(ceil(x[u]/2)-l(u,v))≤x[v]≤2([x[u]/2]+l(u,v))，最大化满足x[p[i]]=2d[i]-1的i的f[i]之和。
不错，推到这一步，就可以充分利用图是树的性质了。
显然，可以用一个O(nD)的DP来做这个东西：令f(i,j)为当x[i]=j时，i子树的最大和是多少。显然这个是TLE的。
怎么办呢？我们不妨试试用数据结构优化这个DP！
（嗯没错，我考场上想到了这一步，然后就没时间了。。。事实证明这题考场上几乎不可能有时间写完）
这一步我绕了好几个弯，最后回到最初的那种思路上才做出来。。。
来，我们用数据结构来维护之前的DP数组。注意到DP数组实际上是若干段连续区间，每段的DP值一样。并且转移有两种：
1. f(u,j)=max{f(v,j')|2(ceil(j/2)-l(u,v))≤j'≤2([j/2]+l(u,v))}
一些区间会变长，一些区间会变短甚至消失。
在数据结构中，我们可以每次暴力删掉将最早消失的区间。
2. f(u,v)=f(v,j)+f(w,j)
在数据结构中，我们可以启发式合并f(v,)和f(w,)，用插入和区间加的操作即可完成。
很棒了。如果能用单次操作O(logn)的数据结构维护f，那么总复杂度就是O(n+klogk)，就可以AC这题了。
由于有插入和区间加，我放弃了用STL的set，写了个Splay树的启发式合并。。。这种做法不仅代码巨长而且细节巨多，所以我花了2天时间才写完调完。。。当然，复杂度是O(n+klogk)，这是没有问题的。
另外，在KAN的提醒下这题其实可以用STL set的，做法是打差分标记。
代码： http://codeforces.com/contest/1023/submission/41908179

12

13_1
13_2
13_3
13_4

【Codeforces小课堂第14期】
题目链接： http://codeforces.com/contest/1039/problem/E
题目大意：给定一个由n个长度均为w的区间构成的序列，和q次询问，每次询问一个k，求至少要将这个区间序列分成多少段，才能使每段内区间的交集长度不小于k。n,q≤10^5，k≤w≤10^9，时限7s。
分析：
先考虑一个询问怎么做。用S表示区间序列[x1,x1+w],[x2,x2+w],...,[xn,xn+w]，那么不难发现，如果S[l,r]内区间交集长度不小于k，那么S[l+1,r]内区间交集长度也不小于k。这样就可以做一个贪心：
* 一开始i=1；
* 每次找一个最小的j使得S[i,j]内的区间交集长度小于k，然后分出一段[i,j-1]，令i=j；
* 当i>n时结束。
很好，那么多次询问怎么搞？
考虑维护这个贪心的过程。对于每个i，令f[i]为最小的满足S[i,j]内区间交集长度小于k的j，把i向f[i]连边，就得到了一个树。以结点n+1为根，那么答案就是结点1的深度。
当k变化时，f[i]也会相应发生变化。考虑按k从大到小处理询问，k减小时，f[i]只会增加。把f[i]增加的事件点记下来，它们和询问放在一起排序。处理事件点时，看起来可以用LCT维护这棵树。等等……
“f[i]变化的事件点有多少个啊？”
“糟了，是O(n)级别的。。。”
于是还是维护不了……
所以呢？不会做就分块吧！
我们不记录下所有的事件点，只记录增加后f[i]≤i+b（b是块大小）的事件点，这样事件点就只有O(nb)个了。
不过只处理这些事件，当有f[i]≥i+b时，f[i]的值可能是不正确的，所以这时候把f[i]设成i，即把i设为根，需要另外计算。
查询怎么办？从i=1出发，不断往上走i=f[i]，直到走到根，然后想办法查询出i的实际f[i]，继续往上走。这时候，一种O(n√n log n)的做法已经出来了：
* 暴力预处理f[i]≤i+b的事件点并排序；
* 用LCT维护i连向f[i]形成的森林，修改f[i]时在LCT上cut、link；
* 查询时，令i=1，不断将i移到根，然后用线段树/二分+Sparse Table都可以O(logn)求出f[i]；直到i=n+1，答案就是i移动的边数；由于每次查询i至少增加b，所以这步总复杂度O(nqn/b)。
最终复杂度O(n(b+q/b)logn)，档b取√n时取得最优复杂度O(n√q log n)，可惜由于LCT常数太大，不太能过。。。
还有救吗？
继续分块！
只不过这回不是对树分块，而是对序列S分块。
设块大小为b，对于每次修改操作，我们只在块内维护f[i]与i在同一块的f[i]。这样，事件点个数仍然是O(nb)，每个事件点需要更新一整个块，复杂度O(b)。
查询时，考虑跳到i和f[i]不在同一块的i时怎么办，这时候块内并没有维护f[i]。如果仍用线段树或者二分+ST，复杂度O(logn)。
等等……总复杂度是啥？
O(nb+qnlogn/b)，当b=√(qlogn)时复杂度最优，为O(nq^(2/3)√logn)。
能不能想办法去掉log？
有个技巧：对每个点维护上次查询出的f[i]，那么查询时设新的f[i]为原来的f[i]+t，用ST+倍增法求t，即先不断地试t=2^0,2^1,2^2...，再二分，复杂度O(logt)而不是O(logn)。
看起来只是个常数优化，实际上已经把log去掉了。为什么？
因为满足f[i]≤i+n^(2/3)的f[i]之和有均摊保证，总共增加不超过n^(5/3)，当f[i]>i+n^(2/3)时，查询时这个情况出现次数不超过qn^(1/3)。
所以总共就是O(n^(5/3)+qn^(1/3)logn)，即O(n^(5/3))。
这个做法可以通过，不过比较慢，需要注意常数。
代码： http://codeforces.com/contest/1039/submission/42741582

【Coodeforces小课堂第15期】
题目链接： http://codeforces.com/contest/956/problem/F
题目大意：求l到r之间有多少个整数x，满足可以将x的数位分成两组，两组数位和之差不超过k。多组数据，数据组数n≤50000，1≤l≤r≤10^18，0≤k≤9。
分析：
这题感觉是CF小课堂系列中比较简单的题目之一了。
先想想给你一个x，如何求x点数位分成两组的数位和之差的最小值。
很显然有一个DP，f(i,j)表示能否把前i位分组使两组差为j，则有：
f(i,j)=f(i-1,j+x)∨f(i-1,|j-x|)
那么最小的满足f(m,j)=1的j就是所求最小值，m是x的位数。
这个子问题解决以后呢，原来的问题只需要再套一层DP就做完了。
具体来说，我们设计一个DP：g(i,s)表示所有i位数x（可以有前导0）中，满足对x做之前的DP以后，DP数组的f(i,)状态为s（也就是说s是一个01串），这样的x有多少个。
因为f(i,)只由f(i-1,*)决定，所以：
g(i,s)=∑[0≤x≤9]g(i-1,s')
其中s'是满足插入一个x以后能转移到s的状态。
看起来状态的s这一维很爆炸，不过我们可以进行剪枝：因为最后只有当s的前10位有1时才有用，所以对于g(i,s)，s只有前9i+1位是有用的，前9i+1位相同而后面不同的状态看成同一个状态。
用记忆化搜索可以搜出所有状态。这样剪完以后，实测总状态数不到10^5，可喜可贺。
可是新的问题来了，这题有多组数据，每次做一遍DP是不现实的。
想象一下，如果你要多次询问DAG中某个点到T的路径条数，那么每次跑一遍DP肯定不优秀。优秀的做法是从T反着做一遍DP，就可以直接询问了。
对这题也是同样道理。我们现在记g(i,s)表示x做到第i位之前的f数组为s，确定后i位有多少种方案。等等，这个定义不明确？
嗯，应该这样：g(i,s,k)表示x做到第i位之前的f数组为s，确定后i位有多少种方案使得数位可以分成差不超过k的两组。
这样询问[l,r]的时候，拆成[0,r+1)和[0,l)。在询问[0,n)时枚举x和n的LCP，就可以直接用DP数组回答了。
bonus：
这题官方题解里提到l,r≤10^100也是能做的。没错，做法仍然很简单。
在之前用记忆化搜索搜状态的基础上，当两个状态对于x=0,1,...,9的后继都相同时，把这两个状态合并。
合并以后状态数骤减，只有715个。那么在现在的状态上DP就可以了。
为了进一步优化，可以对g(i,s,k)做前缀和：g(i,s,k,x)表示在之前的意义基础上，要求下一个数位不超过x。这样预处理复杂度不变，查询复杂度是O(log r)的。
代码： http://codeforces.com/contest/956/submission/42773766

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注