CF1732C2 Sheikh (Hard Version)

思路

首先证明一下当序列扩大时答案一定不劣。考虑 $f(l,r)$ 到 $f(l,r + 1)$ 的变化。

$$\begin{aligned} f(l,r) - f(l,r + 1) &= s_{l,r} - xs_{l,r} - s_{l,r + 1} + xs_{l,r + 1}\\ &= xs_{l,r + 1} - xs_{l,r} - a_{r + 1}\\ &\leq 0 \end{aligned}$$

同理可证 $f(l,r) \geq f(l - 1,r)$。因此上述猜想成立。

那么问题转变为找到最小的 $r' - l'$ 使得 $f(l',r') = f(l,r)$。

显然，被我们去掉的数一定满足 $\sum x = \oplus x$，根据抽屉原理这种数不超过 $30$ 个（提前处理掉 $0$）。

直接暴力枚举即可。

Code

#include <bits/stdc++.h>
#define re register
#define int long long

using namespace std;

const int N = 2e5 + 10;
int n,q;
int arr[N],s[N],xs[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline void solve(){
    int len;
    vector<int> v;
    n = read(),q = read();
    for (re int i = 1;i <= n;i++){
        arr[i] = read();
        s[i] = s[i - 1] + arr[i];
        xs[i] = xs[i - 1] ^ arr[i];
        if (arr[i] > 0) v.push_back(i);
    }
    len = v.size();
    while (q--){
        int l,r,p;
        l = p = read(),r = read();
        int ansl = l,ansr = r,Min = r - l + 1;
        l = lower_bound(v.begin(),v.end(),l) - v.begin();
        r = upper_bound(v.begin(),v.end(),r) - v.begin() - 1;
        if (!len || l > r){
            printf("%lld %lld\n",p,p); continue;
        }
        for (re int i = l;i <= l + 30;i++){
            for (re int j = r - 30;j <= r;j++){
                if (i > j || i >= len || j >= len || j < 0) continue;
                int L = v[i],R = v[j];
                if ((s[R] - s[L - 1]) - (xs[R] ^ xs[L - 1]) == (s[v[r]] - s[v[l] - 1]) - (xs[v[r]] ^ xs[v[l] - 1])){
                    if (R - L + 1 < Min){
                        Min = R - L + 1;
                        ansl = L; ansr = R;
                    }
                }
            }
        }
        printf("%lld %lld\n",ansl,ansr);
    }
}

signed main(){
    int T; T = read();
    while (T--) solve();
    return 0;
}