复习与回顾：2021.7.8 contest 1
A
Description
? 模拟一款坦克游戏的击穿判定（详细部分 略）
Solution
? 分类讨论+模拟（签到题 详解略）
B
Description
? 给定一个长度为 \(n\)? 的序列 \(a\)? ，给出 \(m\) 个操作。
? 每次操作给出 \(x,y\) 表示将序列中所有的 \(x\) 修改为 \(y\) 。
? 定义序列中两个元素的距离: \(dis(a_i,a_j) = \begin{cases}|i-j|, & {a_i = a_j} \\inf(INT\_MAX:2147483647), & {a_i \neq a_j}\end{cases}\)????
? 每次操作后求出 \(max_{i \neq j \ \in [1,n]}\left\{dis(a_i , a_j)\right\}\)
Input
? 第一行两个数 \(n,m\)?
? 第二行 \(n\)? 个数，依次表示序列 \(a\)? ?中的每个元素。
? 然后 \(m\) 行每行两个数 \(x\) 和 \(y\) ，表示序列中所有 \(x\) 会变成 \(y\) 。
Output
? 输出 \(m\) 行，即对于每次修改操作，输出一行一个数表示进行了修改后的答案
Example
input：
5 5
2 7 6 3 8
2 3
6 1
8 1
1 2
2 3
output：
3 3 2 2 1
Hint
? 满足 $1 \leq n,m \leq 10^5 ;,; 1 \leq\ a_i \leq n $?
Solution
? 注意到只有\(a_i\)?相同的前驱、后继才会对答案产生影响，于是利用\(set\)对于每种\(a_i\)???维护位置集合。
? 注意到每次操作后\(a_i\)?的种类数和答案只会减少，于是采用启发式合并的思想，每次操作将\(size\)???小的位置集合中所有元素依次取出并插入到另一集合中，每次插入时查找前驱后继并更新答案。
? 启发式合并均摊复杂度\(O(n\,logn)\)?? ，而每次插入、查找、迭代器迭代的复杂度均为\(O(logn)\)?? ，于是总复杂度\(O(n\;log^2n)\)?
? \(PS\)?.其实按照题意应该特判\(a_i\)?两两不同的情况,或者将Ans变量的初值赋为\(INT\_MAX\)?
Code
（略）
C
Description
? 输入一个01串 \(S1\) 。你需要输出一个最短的01串 \(S2\) ，使得 \(S2\) 在 \(S1\) 中从未出现过。
? 如果有多个可行的解，你需要输出字典序最小的那一个。
Input
? 一行一个字符串，表示\(S1\)
Output
? 一行一个字符串，表示\(S2\)
Example
input
10100011
output
110
Hint
? 时限 \(1s\)?
? 满足 \(1 \leq |S1| \leq 16777216\)
Solution
? 容易发现 若\(|S2|=L\)????????????时有解，则 \(\forall L^{‘}\geq L \;,\;\exists S2(|S2|=L^{‘})\)????????是解??。
? 观察数据范围（其实也是提示），发现 \(16777216=2^{24}\)??? 而当 \(|S2|=24,|S1|=1677216\)? 时共有\(1677216\)??种01串可作为\(S2\)，却最多只有\(1677193\)种长度为\(24\)的01串可作为\(S1\)的子串，根据抽屉原理此时必有一解。
? 于是产生一个想法：暴力枚举\(|S2|\)?，每次\(O(n)\)?????判断并寻找答案。 然而\(|S1|\)?比较大，这样并不能在时限内得出答案。回想起第一段的那句话，发现我们可以改为二分\(|S2|\)?来优化。
Code
（略）
D
Description
? 给定一个序列 \(A\)，定义一个区间\([l,r]\)的最大子段和\(f(l,r)=max_{i \leq j \; \in [l,r]}\left\{\sum_{k=i}^{j}{A_i}\right\}\)
? 求出所有 \(1 \leq l \leq r \leq n\) 的区间\([l,r]\)的最大子段和 的和，答案对\(2^{64}\)取模。
Input
? 第一行一个数 \(n\) 。
? 第二行 \(n\) ?个数，第 \(i\)? 个表示 \(A_i\) 。
Output
? 一行一个数表示答案。
Example
input 1
5
1 -1 1 -1 1
output 1
11
input 2
5
1 -2 3 -4 5
output 2
39
Hint
? 满足 \(1 \leq n \leq 10^5 \ ,\ -10^9 \leq A_i \leq 10^9\)
Solution
? 由于对所有区间求和，考虑线段树分治，于是问题转化为如何求出\(\sum_{i \in [l,mid] \;,\; j \in [mid+1,r]} {f(i,j)}\)
? 设 \(g_l(l,k)=max_{i=l}^{k}\left\{\sum_{j=i}^{k}{A_j}\right\}\) , \(g_r(k,r)=max_{i=k}^{r}\left\{\sum_{j=k}^{i}{A_j}\right\}\)
? 我们知道对于\([l,r]_{l \neq r},f(l,r)=max\left\{f(l,k)\ ,\ g_l(l,k)+g_r(k+1,r)\ ,\ f(k+1,r) \right\}(\ {k \in [l,r)}\ )\)????
? 也就是说\(f(i,j)=max\left\{f(i,mid)\ ,\ g_l(i,mid)+g_r(mid+1,j)\ ,\ f(mid+1,j)\right\}\)??????
? 我们可以枚举\(i\)???计算当 \(f(i,mid) \geq f(mid+1,j)\)??? 时 \(f(i,j)\)??? 的贡献，同理枚举\(j\)???计算当 \(f(i,mid) < f(mid+1,j)\)??? 时 \(f(i,j)\)??? 的贡献
? 具体的，当枚举一个确定的\(i\)?时我们有确定的\(f(i,mid),g_l(i,mid)\)??? ，设此时贡献为\((*)\)?，于是?
? \(p_1\)和\(p_2\)可以通过二分求得
? 上式经过类似前缀和的预处理后可\(O(1)\)计算
? 枚举\(j\)时我们也做相似的处理
? 由于线段树分治+二分，总复杂度为\(O(n\,log^2n)\)
Code
long long MS[100005],NS[100005];//MS:gl/gr NS:f
unsigned long long SM[100005];//前缀和 由于对2^64取模，使用自然溢出
void Solve(int l,int r){
if(l==r){Ans+=A[r];return;}
int mid=(l+r)>>1;
Solve(l,mid);Solve(mid+1,r);
//开始预处理:
for(int i=l;i<=r;i++)SM[i]=MS[i]=NS[i]=0;
SM[mid]=MS[mid]=NS[mid]=A[mid];
for(long long i=mid-1,Mc=A[mid],Nc=A[mid];i>=l;i--){
Mc+=A[i];if(MS[i+1]>Mc)MS[i]=MS[i+1];else MS[i]=Mc;SM[i]=SM[i+1]+MS[i];
(Nc<0?Nc=0:0);Nc+=A[i];if(NS[i+1]>Nc)NS[i]=NS[i+1];else NS[i]=Nc;
}
SM[mid+1]=MS[mid+1]=NS[mid+1]=A[mid+1];
for(long long i=mid+2,Mc=A[mid+1],Nc=A[mid+1];i<=r;i++){
Mc+=A[i];if(MS[i-1]>Mc)MS[i]=MS[i-1];else MS[i]=Mc;SM[i]=SM[i-1]+MS[i];
(Nc<0?Nc=0:0);Nc+=A[i];if(NS[i-1]>Nc)NS[i]=NS[i-1];else NS[i]=Nc;
}
//结束预处理
unsigned long long An=Ans,STO=0;
//枚举i:
for(int i=mid;i>=l;i--){
int L=mid+1,R=r,MD,CT;
long long Mi=MS[i],Ni=NS[i];
while(L<=R){MD=(L+R)>>1;
if(NS[MD]<Ni)L=MD+1;else R=MD-1;
}if(R<=mid)continue;CT=R;//CT==p2
L=mid+1;while(L<=R){MD=(L+R)>>1;
if(MS[MD]<Ni-Mi)L=MD+1;else R=MD-1;
}
Ans+=1ull*(R-mid)*Ni;
Ans+=1ull*(CT-R)*Mi+SM[CT]-(R>mid?SM[R]:0);
}
//枚举j:
for(int i=mid+1;i<=r;i++){
int L=l,R=mid,MD,CT;
long long Mi=MS[i],Ni=NS[i];
while(L<=R){MD=(L+R)>>1;
if(NS[MD]<=Ni)R=MD-1;else L=MD+1;
}if(L>mid)continue;CT=L;//CT==p2
R=mid;while(L<=R){MD=(L+R)>>1;
if(MS[MD]<Ni-Mi)R=MD-1;else L=MD+1;
}
Ans+=1ull*(mid-L+1)*Ni;
Ans+=1ull*(L-CT)*Mi+SM[CT]-(L<=mid?SM[L]:0);
}
}