洛谷 P5057 [CQOI2006]简单题(树状数组)

时间:2022-11-12 03:30:49

嗯...

题目链接:https://www.luogu.org/problem/P5057

首先发现这道题中只有0和1,所以肯定与二进制有关。然后发现这道题需要支持区间更改和单点查询操作,所以首先想到的是异或意义下的差分数组,于是自己便写了一个差分数组,确实好写,但很慢(可能我写的不优),下面是五十分的异或意义下的差分的代码:

 #include<cstdio>
#include<iostream> using namespace std; int a[], b[]; int main(){
int n, m, t, l, r, x;
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) b[i] = a[i] ^ a[i - ];
for(int i = ; i <= m; i++){
scanf("%d", &t);
if(t == ){
scanf("%d%d", &l, &r);
b[l] ^= ;
b[r + ] ^= ;
for(int i = ; i <= n; i++)
a[i] = a[i - ] ^ b[i];
}
else{
scanf("%d", &x);
printf("%d\n", a[x]);
}
}
return ;
}

50分-差分

很明显,我写的差分时间复杂度在O(mn)左右,所以超时...

而正解是用树状数组来维护,因为树状数组支持区间更改和单点查询。注意单点查询之后,也是本题最神奇的地方,将查询的10进制%2,即可得它的二进制的最后一位即为答案(也可以理解为进行奇数次操作会改变,进行偶数次操作不会改变)

AC代码:

#include<cstdio>
#include<iostream> using namespace std; int n, t[]; inline int lowbit(int x){
return x & -x;
}//lowbit inline void change(int x, int k){
while(x <= n){
t[x] += k;
x += lowbit(x);
}
return;
}//区间更改 inline int check(int x){
int ans = ;
while(x > ){
ans += t[x];
x -= lowbit(x);
}
return ans;
}//单点查询 int main(){
int m, l, r, f, d;
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++){
scanf("%d", &f);
if(f == ){
scanf("%d%d", &l, &r);
change(l, );
change(r + , -);
}
else{
scanf("%d", &d);
printf("%d\n", check(d) % );//核心
}
}
return ;
}

AC代码