I was tryping to solve problem [https://mirror.codeforces.com/problemset/problem/617/E](https://mirror.codeforces.com/problemset/problem/617/E). I am using Mo's algorithm to solve this problem, but this giving me wrong ans on test case 7. Please help to find where did my code fail.↵
↵
↵
#**My Code**↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
// shortcuts↵
#define M 1000000007↵
#define ll long long↵
#define lld long double↵
#define vi vector<int>↵
#define vll vector<ll>↵
#define mx 1e18↵
#define mn INT_MIN↵
↵
↵
//// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~↵
↵
↵
~~~~~↵
static bool cmp(vector<ll> &a , vector<ll> &b)↵
{↵
if(a[0]/319 != b[0]/319) return a[0]/319 < b[0]/319;↵
else return a[1] < b[1];↵
}↵
↵
void ok(ll t)↵
{↵
ll n , q , k;↵
cin >> n >> q >> k;↵
vector<ll> vt(n+1) , prefix(n+1 , 0);↵
for(ll i = 1; i <= n; i++) cin >> vt[i];↵
for(ll i = 1; i <= n; i++) prefix[i] = prefix[i-1]^vt[i];↵
↵
ll mp[1000500] = {0};↵
vector<vector<ll>> query(q , vector<ll>(3));↵
for(ll i = 0; i < q; i++) ↵
{↵
cin >> query[i][0] >> query[i][1];↵
query[i][0]-=1;↵
query[i][2] =i;↵
}↵
sort(query.begin(), query.end() , cmp);↵
↵
ll total = 0;↵
vector<ll> ans(q , 0);↵
ll left = 0 , right = -1;↵
for(ll i = 0;i<q;i++)↵
{↵
// cout << query[i][0] << " " << query[i][1] << " " << query[i][2] << endl;↵
while(left > query[i][0]) // add↵
{↵
left-=1;↵
total += mp[k^prefix[left]];↵
mp[prefix[left]]+=1;↵
}↵
while(right < query[i][1]) // add↵
{↵
right+=1;↵
total += mp[k^prefix[right]];↵
mp[prefix[right]]+=1;↵
}↵
while(left < query[i][0]) // remove↵
{↵
mp[prefix[left]]-=1;↵
total -= mp[k^prefix[left]];↵
left+=1;↵
}↵
while(right > query[i][1]) // remove↵
{↵
mp[prefix[right]]-=1;↵
total -= mp[k^prefix[right]];↵
right-=1;↵
}↵
ans[query[i][2]] = total;↵
}↵
↵
for(ll i = 0;i<q;i++) cout << ans[i] << endl;↵
}↵
↵
int main()↵
{↵
// Shubham Kumar Jha↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
↵
#ifndef ONLINE_JUDGE↵
freopen("zinput.txt", "r", stdin);↵
freopen("zoutput.txt", "w", stdout);↵
#endif↵
↵
ll t = 1;↵
// cin >> t;↵
for(ll i = 1;i<=t;i++)↵
{↵
ok(i);↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
↵
↵
using namespace std;↵
↵
// shortcuts↵
#define M 1000000007↵
#define ll long long↵
#define lld long double↵
#define vi vector<int>↵
#define vll vector<ll>↵
#define mx 1e18↵
#define mn INT_MIN↵
↵
↵
//
↵
↵
~~~~~↵
static bool cmp(vector<ll> &a , vector<ll> &b)↵
{↵
if(a[0]/319 != b[0]/319) return a[0]/319 < b[0]/319;↵
else return a[1] < b[1];↵
}↵
↵
void ok(ll t)↵
{↵
ll n , q , k;↵
cin >> n >> q >> k;↵
vector<ll> vt(n+1) , prefix(n+1 , 0);↵
for(ll i = 1; i <= n; i++) cin >> vt[i];↵
for(ll i = 1; i <= n; i++) prefix[i] = prefix[i-1]^vt[i];↵
↵
ll mp[1000500] = {0};↵
vector<vector<ll>> query(q , vector<ll>(3));↵
for(ll i = 0; i < q; i++) ↵
{↵
cin >> query[i][0] >> query[i][1];↵
query[i][0]-=1;↵
query[i][2] =i;↵
}↵
sort(query.begin(), query.end() , cmp);↵
↵
ll total = 0;↵
vector<ll> ans(q , 0);↵
ll left = 0 , right = -1;↵
for(ll i = 0;i<q;i++)↵
{↵
// cout << query[i][0] << " " << query[i][1] << " " << query[i][2] << endl;↵
while(left > query[i][0]) // add↵
{↵
left-=1;↵
total += mp[k^prefix[left]];↵
mp[prefix[left]]+=1;↵
}↵
while(right < query[i][1]) // add↵
{↵
right+=1;↵
total += mp[k^prefix[right]];↵
mp[prefix[right]]+=1;↵
}↵
while(left < query[i][0]) // remove↵
{↵
mp[prefix[left]]-=1;↵
total -= mp[k^prefix[left]];↵
left+=1;↵
}↵
while(right > query[i][1]) // remove↵
{↵
mp[prefix[right]]-=1;↵
total -= mp[k^prefix[right]];↵
right-=1;↵
}↵
ans[query[i][2]] = total;↵
}↵
↵
for(ll i = 0;i<q;i++) cout << ans[i] << endl;↵
}↵
↵
int main()↵
{↵
// Shubham Kumar Jha↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
↵
freopen("zinput.txt", "r", stdin);↵
freopen("zoutput.txt", "w", stdout);↵
↵
ll t = 1;↵
// cin >> t;↵
for(ll i = 1;i<=t;i++)↵
{↵
ok(i);↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
