怎么还要填原题链接啊,这 QOJ 的题没法弄上去啊。
考虑暴力做法。抽出 $c$ 数组之后,求出最长子段和即可。这一部分可以扫描线,维护后缀 $c$ 和为 $v$ 的后缀 $b$ 和 $\min$。复杂度 $O(qn)$。
不难想到根号分治。不妨设阈值 $B$。
对于出现次数 $\le B$ 的两种颜色,可以直接套用上面的暴力,复杂度 $O(qB)$。
对于出现次数都 $> B$ 的情况,出现次数超过 $B$ 的数,不超过 $\dfrac{n}{B}$ 种。因此对于这样的 $x, y$ 不超过 $\dfrac{n^2}{B^2}$ 种方案。每个都要 $O(B)$ 的复杂度去求,总的就是 $O(\dfrac{n ^ 2}{B})$。
对于上面两部分,当 $\dfrac{n ^ 2}{B} = qB$,即 $B = \dfrac{n}{\sqrt q}$ 时有最小值,最小值为 $n \sqrt q$。
接下来考虑小块对大块的贡献。这部分我并不会,先考虑一下。思考半天无果,正解可能不是根号分治?唉。
先扔一下 $\mathbf{Sub1}$ 的代码。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define int long long
#define vit vector<int>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )
using namespace std;
const int N = 600050;
const int Base = 300010;
const int INF = 1e15;
int a[N], b[N], n, q;
vector<int> vec[N];
int mn[N], s[N], c[N];
vit merge(const vit &a, const vit &b) {
vit p; int i = 0, j = 0;
while (i < a.size() and j < b.size())
if (a[i] < b[j]) p.push_back(a[i ++ ]);
else p.push_back(b[j ++ ]);
while (i < a.size()) p.push_back(a[i ++ ]);
while (j < b.size()) p.push_back(b[j ++ ]);
return p;
}
long long solve(int x, int y) {
vit p = merge(vec[x], vec[y]); int ans = -INF;
rop(i, 0, p.size()) {
c[i] = (i ? c[i - 1] : 0) + (a[p[i]] == x ? 1 : -1);
s[i] = (i ? s[i - 1] : 0) + b[p[i]];
ans = max(ans, s[i] - mn[c[i] + Base]);
mn[c[i] + Base] = min(mn[c[i] + Base], s[i]);
} rop(i, 0, p.size()) mn[c[i] + Base] = INF; mn[Base] = 0; return ans;
}
signed main() {
scanf("%lld%lld", &n, &q);
if (n > 10000) return 0;
rep(i, 1, n) scanf("%lld", &a[i]);
rep(i, 1, n) scanf("%lld", &b[i]);
rep(i, 1, n) vec[a[i]].push_back(i);
memset(mn, 0x3f, sizeof mn); mn[Base] = 0;
rep(i, 1, q) {
int x, y; scanf("%lld%lld", &x, &y);
printf("%lld\n", solve(x, y));
} return 0;
}
期望得分 $20 \text{pts}$。
注:此题目前还未解决,后面可能填。