题解 P6958 【[NEERC2017]The Great Wall】

· · 题解

小清新双指针+树状数组，不需要离散化/主席树/平衡树之类的东西。

(2021集训队作业 P6958 【[NEERC2017]The Great Wall】)给定三个序列 \{a_{0,n}\},\{a_{1,n}\},\{a_{2,n}\}(a_{i,j}<a_{i+1,j})，你需要选择两个不同的长度为 r 的区间 I,J，使得 w(I,J) 是所有情况中第 k 小的。定义 w(I,J)=\sum a_{[i\in I]+[i\in J],i}。注意，(I,J) 和 (J,I) 视为相同的方案。

考虑二分答案 x，转化为统计答案不超过 x 的方案个数是否至少有 k 个。首先可以将 a_{1} 和 a_2 中每个元素都减去 a_0 对应位置的元素，最后答案加上 a_0 中所有元素之和，转换成对于两个数组的问题 b_{1,i}=a_{1,i}-a_{0,i},b_{2,i}=a_{2,i}-a_{0,i}。

Case 1. I\cap J=\varnothing

设两个区间分别为 I=[s,s+r-1] 和 J=[t,t+r-1]，则 w(I,J)=\sum_{i\in I}b_{1,i}+\sum_{j\in J}b_{1,i}，考虑前缀和优化，令 pre_i=\sum_{j=1}^ib_{1,j}，则 w(I,J)=pre_{s+r-1}-pre_{s-1}+pre_{t+r-1}-pre_{t-1}。设 f_i=pre_{i+r-1}-pre_{i-1}，则 w(I,J)=f_s+f_t。于是需要求出有多少对 s,t，满足 1\le s\le n-2r+1,s+r\le t\le n-r+1,f_s+f_t< x(我们不妨设 J 在 I 右边)，显然是一个二维数点问题。

Case 2. I\cap J\not=\varnothing

则 w(I,J)=\sum_{i=s}^{t-1}b_{1,i}+\sum_{i=t}^{s+r-1}b_{2,i}+\sum_{i=s+r}^{t+r-1}b_{1,i}，再令 pre'_i=\sum_{j=1}^ib_{2,j},g_i=pre'_{i+r-1}-pre_{i-1}-pre_{i+r-1},h_i=pre_{i-1}-pre'_{i-1}+pre_{i+r-1}，则 w(I,J)=g_s+h_t。于是也是一个二维数点：1\le s< n-r+1,s< t\le\min(s+r-1,n-r+1),g_i+h_i< x

双指针+BIT 即可。

#define ll long long
#define pli pair<ll, int>
const int N = 30010;
int n, m, r, k, tr[N];
ll a[N], b[N], c[N];
pli f[N], g[N], h[N];
#define lowbit(x) ((x) & -(x))
inline void add(int x, int v) {
    for (; x <= m; x += lowbit(x)) tr[x] += v;
}
inline int qry(int x) {
    int sm = 0;
    for (; x > 0; x -= lowbit(x)) sm += tr[x];
    return sm;
}
inline int calc(ll x) {
    memset(tr, 0, sizeof tr);
    int cnt = 0;
    for (int t = m, s = 1; t; --t) {
        for (; s <= m && f[s].first + f[t].first <= x; ++s) add(f[s].second, 1);
        cnt += qry(f[t].second - r);
    }
    memset(tr, 0, sizeof tr);
    for (int t = m, s = 1; t; --t) {
        for (; s <= m && g[s].first + h[t].first <= x; ++s) add(g[s].second, 1);
        cnt += qry(h[t].second - 1) - qry(h[t].second - r);
    }
    return cnt;
}
int main() {
    n = rd(), r = rd(), k = rd(), m = n - r + 1;
    ll sm = 0;
    for (int i = 1; i <= n; ++i) a[i] = rd(), sm += a[i];
    for (int i = 1; i <= n; ++i) b[i] = b[i - 1] + rd() - a[i];
    for (int i = 1; i <= n; ++i) c[i] = c[i - 1] + rd() - a[i];
    for (int i = 1; i <= m; ++i)
        f[i] = make_pair(b[i + r - 1] - b[i - 1], i),
        g[i] = make_pair(c[i + r - 1] - b[i - 1] - b[i + r - 1], i),
        h[i] = make_pair(b[i - 1] - c[i - 1] + b[i + r - 1], i);
    sort(f + 1, f + m + 1), sort(g + 1, g + m + 1), sort(h + 1, h + m + 1);
    ll l = 0, r = c[n], mid, ans = 0;
    while (l <= r)
        mid = l + r >> 1, calc(mid) >= k ? ans = mid, r = mid - 1 : l = mid + 1;
    printf("%lld", sm + ans);
    return 0;
}