为什么删掉初始化就过了
查看原帖
为什么删掉初始化就过了
625671
Zmk2009楼主2023/10/4 15:11

原代码:

#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了。 可是题解里说一定要加上这一句,所以为什么,删掉能过啊

2023/10/4 15:11
加载中...