Sequence-蒲公英云

Sequence

题目链接：https://nanti.jisuanke.com/t/40258

打这场现场赛的时候，真的就是无悔了。毕竟字典树和taijan都没学过，现在觉得这场比赛应该能拿银的。不过正式赛肯定不一样。以现在的水平也许能拿个铜吧。

将公式展开，我们可以发现每个数会被异或多少次。我们会发现，如果（l,r）之间的个数是偶数个，那么每个数就是会被异或偶数次，那答案就是0.如果之间的个数是奇数个，那么我们会发现把所有奇数位的数异或起来就是答案了。
所以建两颗线段树即可

#include"stdio.h"
#include"string.h"
#include"algorithm"
using namespace std;
const int N = 100100;
typedef struct Node
{
    int l,r;
    int val;
}Node;
Node tree[2][N * 4];
int n,m;
void Build_Tree(int p,int id,int l,int r)
{
    tree[p][id].l = l; tree[p][id].r = r;
    tree[p][id].val = 0;
    if(l == r)  return ;
    int mid = (l + r) >> 1;
    Build_Tree(p,id * 2,l,mid);
    Build_Tree(p,id * 2 + 1,mid + 1,r);
}
void change(int p,int id,int x,int v)
{
    if(tree[p][id].l == tree[p][id].r) {tree[p][id].val = v; return ;}
    int mid = (tree[p][id].l + tree[p][id].r) >> 1;
    if(x <= mid) change(p,id * 2,x,v);
    else change(p,id * 2 + 1,x,v);
    tree[p][id].val = tree[p][id * 2].val ^ tree[p][id * 2 + 1].val;
}
int ask(int p,int id,int l,int r)
{
    if(l <= tree[p][id].l && r >= tree[p][id].r)  return tree[p][id].val;
    int mid = (tree[p][id].l + tree[p][id].r) >> 1;
    int val = 0;
    if(l <= mid) val ^= ask(p,id * 2,l,r);
    if(r > mid) val ^= ask(p,id * 2 + 1,l,r);
    return val;
}
int main()
{
    int T;
    scanf("%d",&T);
    int cont = 1;
    while(T --)
    {
        scanf("%d%d",&n,&m);
        printf("Case #%d:\n",cont ++);
        Build_Tree(0,1,1,n);
        Build_Tree(1,1,1,n);
        for(int i = 1; i<= n; i ++)
        {
            int x; scanf("%d",&x);
            if(i % 2 == 1) change(1,1,(i + 1)/2,x);
            else change(0,1,i/2,x);
        }
        while(m --)
        {
            int op,l,r;
            scanf("%d%d%d",&op,&l,&r);
            if(op == 0)
            {
                if(l % 2 == 1) change(1,1,(l + 1)/2,r);
                else change(0,1,l/2,r);
            }
            else
            {
                if((r - l + 1) % 2 == 0) printf("0\n");
                else
                {
                    int x;
                    if(l % 2 == 1) x = ask(1,1,(l + 1)/2,(r + 1)/2);
                    else x = ask(0,1,l/2,r/2);
                    printf("%d\n",x);
                }
            }
        }
    }
}