[C++知识库]C. Sheikh (Easy/Hard Version)（前缀和/双指针/二分）

Easy Version

题目

题意

给定n个数，q次查询。
每次查询ql,qr这个区间内，f(l,r)函数的最大值。
其中ql<=l<=r<=qr。

f(l,r)=sum(a[l],…,a[r])-xor(a[l],…,a[r])

求最大值对应的l,r，如果有多个相同的f值，求区间长度最小的；如果有多个长度相同，选左下标最小的。

q = 1
ql=1,qr =n

思路

f(l,r)<=f(l,r+1)，因为每次添加一个元素，加一个数x，总是大于等于异或一个数。

双指针搞一搞

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pcc pair<char, char>
#define pii pair<int, int>
#define inf 0x3f3f3f3f
const int maxn = 200010;
const int mod = 998244353;

int n, q, ql, qr;
int a[maxn];
void solve() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    while (q--) {
        scanf("%d%d", &ql, &qr);
    }
    ll s = 0, Xor = 0;
    for (int i = 1; i <= n; ++i) {
        s += a[i];
        Xor ^= a[i];
    }
    ll target = s - Xor;
    if (!target) {
        printf("1 1\n");
        return;
    }
    ll cur_add = 0, cur_xor = 0;
    int resl = 1, resr = n;
    for (int l = 0, r = 0; l < n; ++l) {
        while (r + 1 <= n && cur_add - cur_xor < target) {
            cur_add += a[r+1];
            cur_xor ^= a[r+1];
            ++r;
        }
        if (cur_add - cur_xor < target) {
            break;
        }
        if (r - l < resr - resl + 1) {
            resl = l + 1;
            resr = r;
        }
        cur_add -= a[l+1];
        cur_xor ^= a[l+1];
    }

//	printf("res:%d {%d %d}\n", res, resl, resr);
    printf("%d %d\n", resl, resr);
}
int main() {
    int t = 1;
    scanf("%d", &t);
    int cas = 1;
    while (t--) {
//		printf("cas %d:\n", cas++);
        solve();
    }

}
 

Hard Version

题目

题意

在easy version的基础上，限定q=n。

思路

由easy version的思路推论，最大值显然是f(ql,qr)。
现在要想办法缩小区间长度。

注意到，f(l,r)<f(l,r+1)，当且仅当a[r+1]这个元素，存在和f(l,r)都是1的位；f(l,r)==f(l,r+1)，当且仅当a[r+1]存在的1对应的位，在f(l,r)上都是0。

因为a[i]都是int范围，最多存在31个元素能保持f(l,r)==f(l,r+1)

利用这个思路，对于每次查询，我们可以二分长度，每次判断时，枚举31个非0元素，并利用前缀和判断当前枚举的子区间是否满足。

代码

代码源自 CCSU_Wine

// Problem: C1. Sheikh (Easy version)
// Contest: Codeforces - Codeforces Round #830 (Div. 2)
// URL: https://codeforces.com/contest/1732/problem/C1
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// author: https://codeforces.com/profile/CCSU_Wine 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
ll preS[N], preX[N], a[N], nex[N];
bool check(int ql,int qr,ll ans,int mid,int &ansl, int &ansr)
{
	// printf("mid = %d\n",mid);
    for(int i = ql, j = 1; j <= 32; i = nex[i], j ++){
        int l = i, r = i + mid - 1;
        // printf("l = %d r = %d\n",l,r);
        r = min(r, qr);
        ll res = preS[r] - preS[l - 1] - (preX[r] ^ preX[l - 1]);
        if(res == ans) {
            ansl = l, ansr = r;
            return true;
        }
        if(r == qr) return false;
        // printf("nex[i] = %d ql = %d qr = %d\n",nex[i],ql,qr);
        if(!nex[i] || nex[i] > qr) return false;
    }
    return false;
}
void solve()
{
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i = 1; i <= n; i ++){
        scanf("%d",&a[i]);
        preS[i] = preS[i - 1] + a[i];
        preX[i] = preX[i - 1] ^ a[i];
    }

    int id = 0;
    for(int i = n; i >= 1; i --){
        nex[i] = id;
        if(a[i]) id = i;
    }
    while(q --)
    {
        int ql,qr;
        scanf("%d%d",&ql,&qr);
        if(!nex[ql] || nex[ql] > qr){
            printf("%d %d\n",ql,ql);
            continue ;
        }
        int l = 1, r = qr - ql + 1;
        ll ans = preS[qr] - preS[ql - 1] - (preX[qr] ^ preX[ql - 1]);
        int ansl = 1, ansr = r;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(check(ql,qr,ans,mid,ansl,ansr))r = mid - 1;
            else l = mid + 1;
        }
        printf("%d %d\n",ansl,ansr);
    }
    return ;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}