1 solutions

  • 0
    @ 2024-10-04 00:05:24
    #include <bits/stdc++.h>
    using namespace std;
    #define SC               scanf
    #define PF               printf
    #define ull              unsigned long long
    #define ld               long double
    #define F                first
    #define S                second
    #define pb               push_back
    #define sort_a(a)        sort(a.begin(),a.end());
    #define sort_d(a)        sort(a.rbegin(),a.rend());
    #define READ(f)          freopen(f, "r", stdin)
    #define WRITE(f)         freopen(f, "w", stdout)
    #define rev(s)           reverse(s.begin(),s.end())
    #define P(ok)            cout << (ok ? "YES\n": "NO\n")
    #define __Heart__              ios_base :: sync_with_stdio(false); cin.tie(NULL);
    #define ll long long
    typedef pair< ll , ll>                   PII;
    const int sz = 2e5 + 5 ;
    int dp[sz] ;
    void solve()
    {
        ll n , a , Ans = 0; cin >> n ;
        for(ll i = 0 ; i < n ; i++){
            cin >> a ;
            (i == 0? dp[i] = a : dp[i] = dp[i - 1] ^ a) ;
        }
        map < ll , ll > value , range ;
        for(ll i = 0 ; i < n ; i++){
            if(value[dp[i]] > 0){
                ll cur = (i - 1) * value[dp[i]] - range[dp[i]] ;
                Ans += cur ;
                value[dp[i]]++ ;
                range[dp[i]] += i ;
                if(dp[i] == 0) Ans += i ;
            } else {
    
                 if(dp[i] == 0) Ans += i ;
                 value[dp[i]]++ ;
                 range[dp[i]] += i ;
            }
        }
        cout << Ans << "\n" ;
    }
    int main()
    {
         __Heart__
         // READ("input9.txt") ;
         //WRITE("output9.txt") ;
         int t ; cin >> t ; while(t--) solve() ;
    }
    
    
    
  • 1

Information

ID
1096
Difficulty
6
Category
Math | Implementation | DP Click to Show
Tags
# Submissions
73
Accepted
17
Accepted Ratio
23%
Uploaded By