Codeforces 1438E Yurii Can Do Everything 暴力

Codeforces 1438E Yurii Can Do Everything

题意

给定一个长度为(n)的数组(a)，问有多少个区间([l,r])满足：

• (l+1 le r-1)。
• ((a_loplus a_r)=(a_{l+1}+a_{l+2}+ cdots +a_{r-1}))。

(nle 2cdot 10^5,a_i le 10^9)

分析

因为(sum(l+1,r-1)le 2cdot max(a_l,a_r))，所以可以固定左端点，暴力枚举右端点并保证(sum(l+1,r-1)le 2cdot a_l)，对于每个右端点都(check)一下是否满足条件，再反过来做一遍，用(set)去下重。

这样做的复杂度是(O(nlog(max(a_i))))，复杂度证明可以看下官方题解。

Code

#include<bits/stdc++.h>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=2e5+10;
const int inf=1e9;
int n;
int a[N];
ll pre[N];
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pre[i]=pre[i-1]+a[i];
    }
    set<pii>ans;
    for(int i=1;i<=n;i++){
        for(int j=i+2;j<=n&&pre[j-1]-pre[i]<=2*a[i];j++) if((a[i]^a[j])==pre[j-1]-pre[i]){
            ans.insert(mp(i,j));
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=i-2;j>=1&&pre[i-1]-pre[j]<=2*a[i];j--) if((a[i]^a[j])==pre[i-1]-pre[j]){
            ans.insert(mp(j,i));
        }
    }
    printf("%d
",sz(ans));
    return 0;
}