Description

题目链接

题目大意:给定序列 $\{a_n\}$ 和 $q$ 次询问,每次询问区间 $[l, r]$ 经过多少次操作可以全部为 $0$,每次操作可以选择 $[l, r]$ 内的一个长度为偶数的子序列,将第一项 $+1$,第二项 $-1$,第三项 $+1$,$\cdots$。

Solution

先将 $a_i$ 减去 $b_i$。

设 $s_i$ 为 $\{a_n\}$ 的前缀和,显然当 $s_r \ne s_{l - 1}$ 时必定无解。

考虑每次操作对 $\{s_n\}$ 的影响,设操作的位置为 $p_1, p_2, \cdots, p_m$,那么相当于把 $s_{p_1} \sim s_{p_2 - 1}$ 加 $1$,把 $s_{p_3} \sim s_{p_4 - 1}$ 加 $1$,以此类推,而最后由于 $a_i = 0$,即 $s_i = s_{l - 1}$。

因此当 $s_i > s_{l - 1}$ 时也是无解的。

最后考虑最小操作次数怎么求,通过上面的分析可以看出答案即为 $s_{l - 1} - \min \limits_{i = l}^r \{s_i\}$。有一个很奇怪的结论是答案为区间的最大子段和。维护最大值最小值可以使用 ST 表。

不理解的话可以画图观察一下,还是很容易观察出结论的。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

LL f[100010][20], g[100010][20];
LL a[100010], s[100010], lg[100010], b[100010];
int n, q;
 
LL queryMax(int l, int r) {
    int x = lg[r - l + 1];
    return std::max(f[l][x], f[r - (1 << x) + 1][x]);
}

LL queryMin(int l, int r) {
    int x = lg[r - l + 1];
    return std::min(g[l][x], g[r - (1 << x) + 1][x]);
}
 
int main() {
    read(n), read(q);
    for (int i = 2; i <= n; ++i)    lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; ++i)    read(a[i]);
    for (int i = 1; i <= n; ++i)    read(b[i]), a[i] -= b[i];
    for (int i = 1; i <= n; ++i)    s[i] = s[i - 1] + a[i], f[i][0] = g[i][0] = s[i];
    for (int j = 1; j < 20; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            f[i][j] = std::max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            g[i][j] = std::min(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
        }
    }
    while (q--) {
        int l, r;
        read(l), read(r);
        if (s[r] != s[l - 1] || queryMax(l, r) > s[l - 1])    puts("-1");
        else    printf("%lld\n", s[l - 1] - queryMin(l, r));
    }
    return 0;
}
Last modification:September 2nd, 2021 at 02:18 am