提高二 特殊价值 WA20分

常规
1

利用了 a + b \ge a \text{xor} b 这一个特点

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 1e6 + 10;
int a[maxn],d[maxn];
int sum[maxn],xorsum[maxn];
int n,m,l,r,cnt;
int get(int l,int r)
{
    return sum[r] - sum[l - 1] - (xorsum[r] ^ xorsum[l - 1]);
}
signed main()
{
    int T;
    cin >> T;
    while(T--)
    {
        cnt = 0;
        cin >> n >> m;
        for(int i = 1;i <= n;i++)
        {
            cin >> a[i];
            if(a[i] > 0)d[++cnt] = i;
        }
        n = cnt;
        for(int i = 1;i <= n;i++)
        {
            sum[i] = sum[i - 1] + a[d[i]];
            xorsum[i] = xorsum[i - 1] ^ a[d[i]];
        }
        while(m--)
        {
            int l,r;
            cin >> l >> r;
            int p = l;
            l = lower_bound(d + 1,d + n + 1,l) - d;
            r = upper_bound(d + 1,d + n + 1,r) - d - 1;
            if(l > r || !n)
            {
                cout << p << " " << p << '\n';
                continue;
            }
            int L = l,R = r;
            for(int i = l;i <= l + 40;i++)
            {
                for(int j = r - 40;j <= r;j++)
                {
                    if(i <= j && get(l,r) == get(i,j) && d[j] - d[i] < d[R] - d[L])
                    {
                        L = i;
                        R = j;
                    }
                }
            }
            cout << d[L] << " " << d[R] << '\n';
        }
    }
    return 0;
}
1 个赞
2 
long long ma = su[n] - xo[n];
  for (int i = n, ml = n; i >= 1; --i) {
    ml = min(ml, i);
    while (ml >= 1 && su[i] - su[ml - 1] - (xo[i] ^ xo[ml - 1]) < ma) {
      --ml;
    }
    if (ml < 1) {
      break;
    }
    long long now = su[i] - su[ml - 1] - (xo[i] ^ xo[ml - 1]);
    if (now > ma || now == ma && i - ml <= ans.second - ans.first) {
      ans = make_pair(ml, i);
      ma = now;
    }
  }

双指针一趟跑完就行, su是求和 xo是异或

2 个赞