Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum - dblank

Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum

很容易发现其实区间的出现偶数次数的异或和其实是这个区间所有的数的异或和和这个区间所有的不同的数的或和,因为奇数个数的数再异或这个数就会变成0,而偶数个数的数异或他本身就变成他本身。

区间所有数异或和很好查找,用一个树状数组就可以了,然后要怎么查找区间不同数的异或和呢,离线+树状数组。

我们可以把所有的查询区间按照r排序,先记录每个数第一次出现的位置,然后我们设置一个起点,这个起点是到p[i].r,更新完一个区间后,起点变为这个区间的右端点。对于遍历过程遇到的一个数a[j] 如果last[a[j]] != j说明他之前已经出现过了,然后我们把它更新树状数组里面,其实就是把它消除。然后把last[a[j]] = j。重复操作就好了,不同数的异或和直接查询树状数组就好了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1000000 + 10, Mod = 110119;
typedef long long  LL;
int ans[N], a[N], f[N], s[N];
int lowbit(int x)
{
    return x & (-x);
}
int n;
int sum(int x)
{
    int res = 0;
    while(x >= 1)
    {
        res ^= ans[x];
        x -= lowbit(x);
    }
    return res;
}
void update(int x, int c)
{
    while(x <= n)
    {
        ans[x] ^= c;
        x += lowbit(x);

    }
}
struct node
{
    int l, r, id;
}p[N];
int cmp(node x, node y)
{
    return x.r < y.r;
}
int main()
{
    int m;
    while(cin>>n)
    {
        map<int, int> last;
        memset(ans, 0, sizeof(ans));
        for(int i = 1; i<=n; i++)
        {
            scanf("%d", &a[i]);
            if(!last[a[i]]) last[a[i]] = i;
            update(i, a[i]);
        }
        cin>>m;
        for(int i = 1; i<=m; i++)
        {
            scanf("%d%d", &p[i].l, &p[i].r);
            p[i].id = i;
            f[i] = sum(p[i].r) ^ sum(p[i].l-1);
        }
        sort(p+1, p+1+m, cmp);
        int temp = 1;
        for(int i = 1; i<=m; i++)
        {
            for(int j = temp; j<= p[i].r; j++)
            {
                int id = last[a[j]];
                if(id != j)
                {
                    update(id, a[j]);
                }
                last[a[j]] = j;
            }
            temp = p[i].r;
            s[p[i].id] = sum(p[i].r) ^ sum(p[i].l-1);
        }
        for(int i = 1; i<=m; i++)
        {
            printf("%d\n", f[i] ^ s[i]);
        }
    }
    return 0;
}

相关文章

发表新评论