感觉显式的根号分治还是太不优美了。

Solution

设 $s_x$ 表示颜色为 $x$ 的下标组成的集合。考虑现在询问 $x,y$，并且 $\lvert s_x\rvert\le \lvert s_y\rvert$（不满足就交换）。

设 $f(i)=\max(\max_{j\le i}\sum_{k\in[j,i]}c_k,\max_{j\ge i}\sum_{k\in[i,j]}c_k)$，也就是以 $i$ 为一个端点的区间的最大 $c_k$ 和。如果 $f(i)<0$，那么这个 $i$ 永远不会在答案区间中。

对于一个只包含在 $s_y$ 中且 $f(i)<0$ 的 $i$ 的极大连续段，选择的区间和这个连续段不能有交，因此随意保留一个连续段中的数，剩下的数可以删掉。为了方便，统一保留 $f(i)=-1$ 的数。

因此，把 $f(i)\ge -1$ 的 $i$ 全部抠出来，放到集合 $B$ 里面。我们显然有 $\mathcal O(\lvert B\rvert)$ 求解答案的算法。

考虑怎么把这些点抠出来。从左往右枚举 $s_x\cup s_y$ 中的点，维护以当前点为右端点的区间的最大 $c_k$ 和 $t$，如果 $t<-1$ 就 $t\gets 0$ 并跳到下一个 $s_x$ 中的位置。同样地在从右往左枚举一遍。

只会有 $\lvert s_x\rvert$ 次 $+1$，因此每次加入的点不超过 $2\lvert s_x\rvert$ 个，故 $\lvert B\lvert\le 5\lvert s_x\rvert$。

一次询问复杂度为 $\mathcal O(\lvert s_x\rvert\log\lvert s_y\rvert)\le\mathcal O(\min(\lvert s_x\rvert,\lvert s_y\rvert)\log n)$。根据经典结论，记忆化一下，复杂度为 $\mathcal O(n\sqrt q\log n)$。$\log$ 可以通过一些方法优化掉，但是没有必要。

Code

很短。

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define ppc(x) __builtin_popcount(x)
using namespace std;
namespace Milkcat {
	typedef long long LL;
	typedef pair<LL, LL> pii;
	typedef vector<int>::iterator IT;
	const int N = 3e5 + 5;
	LL n, q, x, y, a[N], c[N], b[N * 2];
	vector<int> s[N]; map<int, LL> mp[N];
	int main() {
		cin >> n >> q;
		REP(i, 1, n) cin >> c[i], s[c[i]].pb(i);
		REP(i, 1, n) cin >> a[i];
		REP(te, 1, q) {
			cin >> x >> y;
			if (SZ(s[x]) > SZ(s[y])) swap(x, y);
			if (mp[x].count(y)) { cout << mp[x][y] << '\n'; continue; }

			vector<int> B; vector<IT> A{s[y].begin()};
			for (int i : s[x])
				A.pb(lower_bound(ALL(s[y]), i)), B.pb(i);
			A.pb(s[y].end());

			int t = 0;
			REP(i, 1, SZ(A) - 2) {
				auto it = A[i];
				for (t ++; ~t && it != A[i + 1]; )
					B.pb(*it ++), t --;
				t = max(t, 0);
			}
			t = 0;
			DEP(i, SZ(A) - 2, 1) {
				auto it = A[i];
				for (t ++; ~t && it != A[i - 1]; )
					B.pb(*-- it), t --;
				t = max(t, 0);
			}

			sort(ALL(B)), B.erase(unique(ALL(B)), B.end());
			LL rs = -1e18, sm = 0, d = SZ(B); t = d;
			REP(i, 0, d * 2) b[i] = (i == d ? 0 : 1e18);
			for (int i : B) {
				t += (c[i] == x ? 1 : -1), sm += a[i];
				rs = max(rs, sm - b[t]), b[t] = min(b[t], sm);
			}
			cout << (mp[x][y] = rs) << '\n';
		}
		return 0;
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int T = 1;
	while (T --) Milkcat::main();
	return 0;
}