P8349 题解
donghanwen1225
2022-05-17 00:58:51
upd on $2022-05-17$：补充了一些证明。
------------
SDOI 2022 D1T1。在考场上没有想出来小块对大块的做法，写了个 $O(q(len_x+len_y))$ 的暴力喜提 $\text{30pts}$。
------------
**Part 1 :** 考虑暴力该怎么做。
对于每次询问，首先我们将 $a_i=x$ 和 $a_i=y$ 的所有 $i$ 按照顺序放到一起。令这些 $i$ 组成的序列为 $p$，令 $len_x$ 表示整个 $a$ 序列中 $x$ 的数量，容易得到 $p$ 的长度为 $len_x+len_y$。
那么题意可以转化为，找出一个区间 $[l,r]$，使得 $\sum\limits_{i=l}^{r}[a_{p_i}=x]=\sum\limits_{i=l}^{r}[a_{p_i}=y]$，并令 $\sum\limits_{i=l}^{r}b_{p_i}$ 最大。
设当前考虑到了第 $i$ 个数，在 $p$ 序列的前 $i$ 个数中有 $c_1$ 个是 $x$，$c_2$ 个是 $y$，当前的 $b$ 数列的前缀和为 $sum_i$。令 $q_i=c_1-c_2+len_y$，可以发现，对两个相等的 $q_l,q_r$，区间 $[l,r]$ 是一个满足题意的区间。
考虑维护当前每个 $q_i$ 所对应的 $sum_i$ 的最小值 $mn_{q_i}$。那么在计算到 $i$ 时，只需将答案与 $sum_i-mn_{q_i}$ 比较取最大值即可。另外若 $c_1=c_2$，即 $q_i=len_y$ 时，答案也可以直接更新为当前的前缀和。
时间复杂度为 $O(q(len_x+len_y))$。
**Part 2 :** 考虑根号平衡。
思考为什么上面的暴力无法通过此题。假设 $a$ 序列是这样构成的：其中有 $\dfrac{n}{2}$ 个 $1$，剩余 $\dfrac{n}{2}$ 个全部不同。那么只要每次询问 $1,i$，时间复杂度就将达到 $O(n^2)$。
我们根据 $len_i$ 大小是否达到 $B$，将数分为 “大块” 和 “小块” 两类。
下面分三类讨论：
**1.** 小块对小块。显然直接套用暴力即可。复杂度为 $O(qB)$。
**2.** 大块对大块。因为大块的长度要超过 $B$，所以大块最多有 $\dfrac{n}{B}$ 个。本质不同的询问数只有 $\dfrac{n^2}{B^2}$ 种（对相同的询问，我们将答案用 `unordered_map` 存下来，如果遇到相同的询问直接调用答案即可），直接套用暴力，这部分的复杂度最大为 $O\left(\dfrac{n^2}{B}\right)$。
**3.** 小块对大块。现在我们不能将两部分直接拼起来了。
考虑利用小块的大小不超过 $B$ 的性质。根据暴力的做法，我们将 $p$ 序列中的数分为**有效点**和**无效点**两类。
显然，小块中每个点都是需要考虑在内的有效点。
然而大块中，许多点对答案是不可能产生贡献的。这是因为，选中的区间 $[l,r]$ 中，$x$ 和 $y$ 的数量必须相等，而大块因为点数多，而往往导致其远远压过小块，所以有很多点是无效点。
具体的，我们仍然考虑 $p$ 序列，令 $len_x\leq B<len_y$，
设 $p$ 中有一段极长的 $x$ 连续子段，其长度为 $l$，这个连续子段的左右端点分别为 $L,R$。那么，$p$ 序列中只有在 $L$ 左侧和 $R$ 右侧的 $l+1$ 个 $y$ 才可能成为有效点。这是因为，更多的 $y$ 会压过 $x$ 的个数。我们把这些点加入真正计算的 $p$ 序列中。
另外注意，若 $L$ 左侧 $l+1$ 个 $y$ 中间还包含了另外一些 $x$ 的极长连续子段，则这些 $x$ 子段向两侧拓展时要跳过这些已经成为有效点的 $y$。这个过程可以使用 `set` 去快速维护。
得到有效点后将其离散化，再套用暴力即可。有效点的个数始终只与大小 $\leq B$ 的小块相关，所以是 $O(B)$ 级别的。
考虑到大块的数量不多，且复杂度取决于实际的小块长度，这部分的复杂度应当为 $O\left(\dfrac{n^2\log n}{B}\right)$。虽然有效点个数带大常数，但从下面的复杂度分析来看，实际上还要带一个非常小的常数，整体来看常数较小。
大块对大块的复杂度较小直接忽略，总复杂度为 $O\left(qB+\dfrac{n^2\log n}{B}\right)$。由均值不等式，在 $B=\sqrt{\dfrac{n^2\log n}{q}}$ 时，复杂度为 $O\left(n\sqrt{q\log n}\right)$ 最优。这式子看起来好像能达到 $10^9$，不过因为跑不满 + 常数小，而且时限 $7s$，所以是可以通过的。
按理论计算出来 $B=1200$ 左右最优，但由于数据非常离谱，实际上取 $100,200,300,550$ 时间都差不多，但是取 $1000$ 的时候反而会 TLE。这样就通过了此题。
代码中为了简便，拓展 $l+1$ 个有效点时直接是拓展了 $2l$ 个。
------------
upd 1：补充大块对大块、小块对大块的复杂度的证明。
大块对大块：假设有 $k$ 个大块，第 $i$ 个的长度为 $len_i$。极限情况下令 $\sum\limits_{i=1}^{k}len_i=n$。
考虑令这 $k$ 个大块两两配对进行询问，共进行 $\dfrac{k(k-1)}{2}$ 次询问。总计算次数为 $\sum\limits_{1\leq i<j\leq k}len_i+len_j=(k-1)\sum\limits_{i=1}^{k}len_i=n(k-1)$。
由于 $len_i\geq B$，得 $k\leq\dfrac{n}{B}$，故极限复杂度为 $O\left(\dfrac{n^2}{B}\right)$。
小块对大块：设有 $k_1$ 个大块，第 $i$ 个的长度为 $l_i$；有 $k_2$ 个小块，第 $i$ 个的长度为 $L_i$。则有 $\sum\limits_{i=1}^{k_1}l_i+\sum\limits_{i=1}^{k_2}L_i=n$。
考虑到小块对大块的复杂度只取决于小块长度，我们用最长的 $\dfrac{q}{k_1}$ 个小块对着大块进行询问。极限情况下，有 $k_2=\dfrac{q}{k_1}$，也即每个小块都对着每个大块查了一次。总计算次数为 $\sum\limits_{i=1}^{k_2}\sum\limits_{j=1}^{k_1}L_i\log l_j\leq k_1\log n\sum\limits_{i=1}^{k_2}L_i$。
最强的情况下，可构造 $\dfrac{n}{2B}$ 个长度略大于 $B$ 的大块，和总长度大约为 $\dfrac{n}{2}$ 的一些小块，此时 $k_1\approx\dfrac{n}{B},\sum\limits_{i=1}^{k_2}L_i\approx n$，故极限复杂度为 $O\left(\dfrac{n^2\log n}{B}\right)$。此时要有 $k_2\leq\dfrac{qB}{n}$。
code：
```cpp
#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int blo=300;
int n,q,x,y,a[300005],len[300005],st[300005],tim[300005],pre[300005],cl[300005];
ll b[300005],mn[300005];unordered_map<int,ll> mp[300005];set<int> pos[300005];
struct node{int id;ll v;} xl[300005];
vector<node> tj[300005];vector<ll> qz[300005];
template<typename T> void Read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9') f=f||(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
x=f==0?x:-x;
}
int main()
{
Read(n);Read(q);
for(int i=1;i<=n;i++) Read(a[i]),tim[i]=tim[pre[a[i]]]+1,pre[a[i]]=i;
for(int i=1;i<=n;i++) Read(b[i]);
for(int i=1;i<=n;i++) tj[a[i]].push_back({i,b[i]}),pos[a[i]].insert(i);
for(int i=1;i<=n;i++)
if(tj[i].size())
{
len[i]=tj[i].size();qz[i].resize(len[i]+1);
for(int j=0;j<len[i];j++) qz[i][j+1]=qz[i][j]+tj[i][j].v;
}
for(int i=0;i<=n;i++) mn[i]=1ll<<60;
while(q--)
{
Read(x);Read(y);
if(mp[x].find(y)!=mp[x].end()){printf("%lld\n",mp[x][y]);continue;}
if((len[x]>blo&&len[y]>blo)||(len[x]+len[y]<=blo))
{
int tl=0,tr=0;ll ans=-(1ll<<60);
while(tl<len[x]&&tr<len[y])
{
if(tj[x][tl].id<tj[y][tr].id) xl[tl+tr]=tj[x][tl],tl++;
else xl[tl+tr]=tj[y][tr],tr++;
}
while(tl<len[x]) xl[tl+tr]=tj[x][tl],tl++;
while(tr<len[y]) xl[tl+tr]=tj[y][tr],tr++;
int cur1=0,cur2=0;
for(int i=0;i<len[x]+len[y];i++)
{
if(a[xl[i].id]==x) cur1++;
if(a[xl[i].id]==y) cur2++;
int sl=cur1-cur2+len[y];
if(sl==len[y]) ans=max(ans,qz[x][cur1]+qz[y][cur2]);
ans=max(ans,qz[x][cur1]+qz[y][cur2]-mn[sl]);
mn[sl]=min(mn[sl],qz[x][cur1]+qz[y][cur2]);cl[i]=sl;
}
mp[x][y]=mp[y][x]=ans;printf("%lld\n",ans);
for(int i=0;i<len[x]+len[y];i++) mn[cl[i]]=1ll<<60;
}
else
{
if(len[x]>len[y]) swap(x,y);
int top=0;ll ans=-(1ll<<60);
for(int i=0;i<len[x];i++)
{
if(!pos[y].size()) continue;
auto tmp=pos[y].lower_bound(tj[x][i].id);
if(tmp==pos[y].begin()) continue;--tmp;st[++top]=*tmp;
auto del=tmp;if(tmp==pos[y].begin()) continue;--tmp;
st[++top]=*tmp;pos[y].erase(del);pos[y].erase(tmp);
}
for(int i=0;i<len[x];i++)
{
if(!pos[y].size()) continue;
auto tmp=pos[y].upper_bound(tj[x][i].id);
if(tmp==pos[y].end()) continue;st[++top]=*tmp;
auto del=tmp;++tmp;if(tmp==pos[y].end()) continue;
st[++top]=*tmp;pos[y].erase(del);pos[y].erase(tmp);
}
for(int i=1;i<=top;i++) pos[y].insert(st[i]);
for(int i=0;i<len[x];i++) st[++top]=tj[x][i].id;
sort(st+1,st+1+top);int cnt=unique(st+1,st+1+top)-st-1;
for(int i=1;i<=cnt;i++) xl[i]={st[i],b[st[i]]};
int cur1=0,cur2=0,las1=0,las2=0;
for(int i=1;i<=cnt;i++)
{
if(a[xl[i].id]==x) cur1+=tim[xl[i].id]-las1,las1=tim[xl[i].id];
if(a[xl[i].id]==y) cur2+=tim[xl[i].id]-las2,las2=tim[xl[i].id];
int sl=cur2-cur1+len[x];
if(sl==len[x]) ans=max(ans,qz[x][cur1]+qz[y][cur2]);
ans=max(ans,qz[x][cur1]+qz[y][cur2]-mn[sl]);
mn[sl]=min(mn[sl],qz[x][cur1]+qz[y][cur2]);cl[i]=sl;
}
mp[x][y]=mp[y][x]=ans;printf("%lld\n",ans);
for(int i=1;i<=cnt;i++) mn[cl[i]]=1ll<<60;
}
}
return 0;
}
```