原代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = 2e6 + 5;
typedef long long ll;
ll a[N],belong[N],cnt[M];
inline bool isdig(char c){return '0' <= c && c <= '9';}
inline int read(){
int x = 0;
char c = getchar();
while (!isdig(c)) c = getchar();
while (isdig(c)) {
x = x * 10 + c - '0';
c = getchar();
}
return x;
}
inline void write(int x){
if (x / 10) write(x / 10);
putchar(x % 10 + '0');
}
struct query{
int l,r,id,ans;
bool operator < (const query & A)const{
return (belong[l] != belong[A.l] ? belong[l] < belong[A.l] : (belong[l] & 1 ? r < A.r : r > A.r));
}
}q[N];
int n , m , k;
ll now;
ll ans[N];
inline void add(int p){
now += cnt[a[p] ^ k];
++ cnt[a[p]];
}
inline void del(int p){
cnt[a[p]] --;
now -= 1ll *cnt[a[p] ^ k];
}
int main(){
n = read(),m = read(),k = read();
int siz = sqrt(n),block = ceil((double) n / siz);
for (int i = 1 ; i <= block ; i ++){
for (int j = (i - 1) * siz + 1; j <= i * siz ; j ++){
belong[j] = i;
}
}
for (int i = 1 ; i <= n ;i ++) a[i] = read(),a[i] ^= a[i - 1];
for (int i = 1 ; i <= m ; i ++){
q[i].l = read() , q[i].r = read();
q[i].l --;
q[i].id = i;
}
sort(q + 1 , q + m + 1);
int l = 1, r = 0;
cnt[0] = 1;
for (int i = 1; i <= m ; i++){
int ql = q[i].l , qr = q[i].r;
while (l < ql) {del(l ++);}
while (l > ql) {add(-- l);}
while (r < qr) {add(++ r);}
while (r > qr) {del(r --);}
// cout << now << endl;
ans[q[i].id] = now;
}
// for (int i = 1 ; i <= m ; i++) printf("%d " , q[i].ans);
for (int i = 1 ; i <= m ; i ++){
cout << ans[i] << endl;
}
return 0;
}
第一个样例输出:
10
7
将 cnt[0] = 1 删除后,AC了。
可是题解里说一定要加上这一句,所以为什么,删掉能过啊