Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum (離線樹狀數組+前綴xor)

題目鏈接：http://codeforces.com/contest/703/problem/D

給你n個數，m次查詢，每次查詢問你l到r之間出現偶數次的數字xor和是多少。

我們可以先預處理前綴和Xor[i]，表示1~i的xor和。因為num^num=0，所以Xor[r] ^ Xor[l - 1]求的是l~r之間出現奇數次的數字xor和。

那怎么求偶數次的呢，那我們可以先求l到r之間不重復出現數字的xor（比如1 1 2 求的是1 ^ 2），然后再xor以上求出的Xor[r] ^ Xor[l - 1]，奇奇消掉 就得出答案了。

那求不重復的話，我們用樹狀數組來處理。先把詢問按照r從小到大排序，以便后面的離線處理。map存的是a[i]數字最近出現的位置i，然后用樹狀數組i位置插入a[i]并且消掉a[i]之前出現的位置i'，這樣保證查詢不重復xor和最優。

具體看代碼，應該能看懂。

//#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int, int> P;
const int N = 1e6 + 5;
int bit[N], Xor[N], a[N], ans[N], n;
map <int, int> mp; //a[i]最近出現的位置
struct Query {
    int l, r, id;
    bool operator <(const Query& cmp) const {
        return r < cmp.r;
    }
}q[N];

void update(int i, int val) {
    for(; i <= n; i += (i&-i))
        bit[i] ^= val;
}

int sum(int i) {
    int s = 0;
    for(; i >= 1; i -= (i&-i))
        s ^= bit[i];
    return s;
}

int main()
{
    int m;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        Xor[i] = Xor[i - 1] ^ a[i]; //前綴xor
    }
    scanf("%d", &m);
    for(int i = 1; i <= m; ++i) {
        scanf("%d %d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    sort(q + 1, q + m + 1);
    int j = 1; //詢問的結構體下標
    for(int i = 1; i <= n; ++i) {
        int &temp = mp[a[i]]; //引用
        if(temp) { //要是不是第一次出現，那就消掉a[i]之前出現的位置
            update(temp, a[i]);
        }
        temp = i;
        update(temp, a[i]); //插入最近的位置
        while(j <= m && i == q[j].r) {
            int l = q[j].l - 1, r = q[j].r;
            ans[q[j].id] = sum(r) ^ sum(l) ^ Xor[r] ^ Xor[l];
            ++j;
        }
    }
    for(int i = 1; i <= m; ++i) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

上面是正確的代碼，下面是TLE的。

之前用莫隊寫的，數據小一點應該可以過。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
const int MAXN = 1e6 + 5;
typedef __int64 LL;
int a[MAXN] , u, ans[MAXN];
struct que {
    int l , r , id;
}q[MAXN];
map <int, int> mp;

bool cmp(que x , que y) {
    if(x.l / u == y.l / u) 
        return x.r < y.r;
    return x.l / u < y.l / u;
}

int main()
{
    int n , m;
    while(~scanf("%d" , &n)) {
        for(int i = 1 ; i <= n ; i++) {
            scanf("%d" , a + i);
        }
        scanf("%d", &m);
        for(int i = 1 ; i <= m ; i++) {
            scanf("%d %d" , &q[i].l , &q[i].r);
            q[i].id = i;
        }
        u = (int)sqrt(n*1.0);
        sort(q + 1 , q + m + 1 , cmp);
        int L = 1 , R = 0 , num;
        int temp = 0;
        for(int i = 1 ; i <= m ; i++) {
            while(R > q[i].r) {
                num = --mp[a[R]];
                if(num) {
                    temp ^= a[R];
                }
                R--;
            }
            while(R < q[i].r) {
                R++;
                num = ++mp[a[R]];
                if(num > 1) {
                    temp ^= a[R];
                }
            }
            while(L < q[i].l) {
                num = --mp[a[L]];
                if(num) {
                    temp ^= a[L];
                }
                L++;
            }
            while(L > q[i].l) {  //前面的還沒算
                L--;
                num = ++mp[a[L]];
                if(num > 1) {
                    temp ^= a[L];
                }
            }
            ans[q[i].id] = temp;
        }
        for(int i = 1 ; i <= m ; i++) {
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}

?