2019 ICPC 南昌邀请赛 F.Sequence

发表于 更新于 分类于 本文字数： 3k 阅读时长 ≈ 3 分钟

题目描述

Oldjang has a sequence $A$ of length $n$, the $i_{th}$ number in which is $A_i$. He defined a function $f(l,r) = a_l \oplus a_{l+1} \oplus \cdots \oplus a_r$. It is simple for the cleverest boy oldjang to calculate the function, so he wants to make the problem more difficult for fun. He will perform two operations:

  1. The operation expressed as “$0 \ x \ y$”, which means he changes the $x_{th}$ number to $y$;

  2. The operation expressed as “$1 \ l \ r$”, which means he wants to calculate the function $F(l,r)$. $F(l,r) = f(l,l) \oplus f(l,l +1) \oplus \cdots \oplus f(l,r)\oplus f(l + 1,l +1) \oplus \cdots f(l + 1,r) \oplus \cdots \oplus f(r,r)$.That means $F(l,r)$ equals to the x or sum of all $f(i,j)$ satisfied $l \le i \le j \le r$.

Oldjang thinks the problem is still too simple for him, so he gives this task to you.

输入描述

The first line contains a integers $T(1 \le T \le 10)$ — the number of test cases .

The second line contains two integers $n,m(1 \le n,m \le 10^5)$, which means the sequence has $n$ numbers and oldjang has $m$ operations.

The next line contains $n$ integers — the sequence $A$.

In the following $m$ lines, each line contains three integers “$0 \ x \ y$” or “$1 \ l \ r$” ,descriping a operation.

输出描述

For each test case, print one line containing “Case # $x$: “ first, where $x$ is the test case number (starting from $1$).

Then output the answer after each the operations of second type.

样例输入

1
2
3
4
5
6
1 
3 3 
1 2 3 
1 1 3 
0 1 2 
1 1 1

样例输出

1
2
3
Case #1:  
2
2

思路

由题意和亦或的性质可得，当区间长度为奇数时
$$
F(l,r)=a_l \oplus a_{l+2} \oplus \cdots \oplus a_r
$$
当区间长度为偶数时
$$
F(l,r)=0
$$
题目是对区间的点更新和区间查询，考虑到更新和查询都是在线的，数据规模是$1e5$，需要$O(n\log_2n)$的时间复杂度才能通过。

当区间长度为奇数时，我们需要计算$a_l \oplus a_{l+2} \oplus \cdots \oplus a_r$，由于奇数项的求和与偶数项的求和互不相关，所以采用建两个树状数组的方式，分别维护奇数项和偶数项的更新和查询。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>
using namespace std;

long long a[1000002],c1[1000002],c2[1000002],tt,n,m;
long long lowbit(long long x)
{return x&(-x);}
void add1(long long i,long long x)
{
    while(i<=n)
    {
        c1[i]^=x;
        i+=lowbit(i);
    }
}
long long sum1(long long x)
{
    long long ans=0;
    while(x>0)
    {
        ans^=c1[x];
        x-=lowbit(x);
    }
    return ans;
}
void add2(long long i,long long x)
{
    while(i<=n)
    {
        c2[i]^=x;
        i+=lowbit(i);
    }
}
long long sum2(long long x)
{
    long long ans=0;
    while(x>0)
    {
        ans^=c2[x];
        x-=lowbit(x);
    }
    return ans;
}

int main(){
    scanf("%lld",&tt);
    for(long long ii=1;ii<=tt;++ii){
        scanf("%lld%lld",&n,&m);
        for(long long i=1;i<=n;++i){
            c1[i]=0;
            c2[i]=0;
        }
        for(long long i=1;i<=n;++i){
            scanf("%lld",&a[i]);
            if(i%2){
                add1((i+1)/2,a[i]);
            }
            else{
                add2((i)/2,a[i]);
            }
        }
        long long x,y,z;
        printf("Case #%lld:\n",ii);
        for(long long i=1;i<=m;++i){
            scanf("%lld%lld%lld",&x,&y,&z);
            if(x==1){
                if((z-y+1)%2){
                    if(y%2){
                        printf("%lld\n",sum1((z+1)/2)^sum1((y+1)/2-1));
                    }
                    else{
                        printf("%lld\n",sum2(z/2)^sum2(y/2-1));
                    }
                }
                else{
                    printf("0\n");
                }
            }
            else{
                if(y%2){
                    add1((y+1)/2,a[y]^z);
                }
                else{
                    add2(y/2,a[y]^z);
                }
                a[y]=z;
            }
        }
    }
    return 0;
}