原题链接

题解

易得当区间异或和不为完全平方数的时候合法

朴素做法：

遍历所有区间，看看异或和是不是完全平方数

优化：

异或是可以交换运算顺序的，如果区间 \([l,r]\) 异或和为完全平方数，那么代表 \(pre[r] \oplus pre[l-1]==k\) 其中k为完全平方数

也就是说，\(pre[r] \oplus k== pre[l-1]\)，这样的性质指引我们遍历r和所有的完全平方数，然后存储所有的 \(pre[l]\)

时间复杂度为 \(O(n\sqrt{n})\)

code

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll inf=1e18;
const ll mod=1e9+7;

vector<ll> sqare;
void solve()
{
    ll n;
    cin>>n;




    map<ll,ll> q;
    q[0]=1;
    ll pre=0;
    ll ans=0;
    for(ll i=1;i<=n;i++)
    {
        ll x;
        cin>>x;
        pre^=x;
        for(auto it:sqare)
        {
            ans+=q[(pre^it)];
        }
        q[pre]++;
    }
    cout<<(n+1)*n/2-ans<<'\n';
}
int main()
{
    for(ll i=0;i*i<=400000;i++)
    {
        sqare.push_back(i*i);
    }
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TT=1;
    cin>>TT;
    while(TT--) solve();
    return 0;
}