P7003 [NEERC2013] Hack Protection

Transparent · 2023-12-13 17:18:21 · 题解

由于与的性质，固定右端点后，区间与和的每一位都是在一点前全为 0，之后全为 1。根据这个性质，可以推出使得与和不同的左端点至多有 62 个（每两个反转一位）。于是可以暴力维护这些与和相等的区间，并利用异或前缀和查询异或和等于与和的位置的数量。

与和相等的区间可以直接用 vector 维护，每次暴力更新并合并值相同的区间。查询某区间中异或前缀和恰为某值可以用 map<int,vector<int>> 记录每个值出现的位置，然后二分。

注意不要把 vector 从 map 里复制出来。

时间复杂度 O(n \log n \log V)。

目前最快的代码：

#include <bits/stdc++.h>

using namespace std;
using ll=long long;

constexpr int MAXN=1e5+10;

map<int,vector<int>> mp;
int n,a[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    vector<pair<int,int>> val;
    cin>>n; int pre=0; ll ans=0; mp[0].emplace_back(0);
    for(int i=1;i<=n;++i) {
        cin>>a[i]; pre^=a[i]; mp[pre].emplace_back(i);
        for(auto &[r,v]:val) v&=a[i];
        val.emplace_back(i,a[i]);
        vector<pair<int,int>> tmp; int p=0,cur=-1;
        for(auto &[r,v]:val) {
            if(cur!=v) {
                if(p) tmp.emplace_back(p,cur);
                cur=v;
            }
            p=r;
        }
        tmp.emplace_back(p,cur); swap(tmp,val);
        int lst=0;
        for(auto [r,v]:val) {
            int req=pre^v;
            if(mp.find(req)==mp.end()) {lst=r; continue;}
            auto &vec=mp[req];
            ans+=upper_bound(vec.begin(),vec.end(),r-1)-lower_bound(vec.begin(),vec.end(),lst);
            lst=r;
        }
    }
    cout<<ans<<endl;

    return 0;
}