NC50438. 简单题
描述
输入描述
第一行包含两个整数n,m，表示数组的长度和指令的条数；
以下m行，每行的第一个数t表示操作的种类：
若t=1，则接下来有两个数L,R，表示区间[L,R]的每个数均反转；
若t=2，则接下来只有一个数i，表示询问的下标。
输出描述
每个操作2输出一行（非0即1），表示每次操作2的回答。
示例1
输入:
20 10 1 1 10 2 6 2 12 1 5 12 2 6 2 15 1 6 16 1 11 17 2 12 2 6
输出:
1 0 0 0 1 1
C++ 解法, 执行用时: 710ms, 内存消耗: 960K, 提交时间: 2021-12-12 16:40:34
#include<bits/stdc++.h>
using namespace std;
int n,m;
bool c[100001];
void a(int i){
while (i <= n){
c[i] ^= 1;
i += i & -i;
}
}
bool g(int i){
bool ans = 0;
while (i){
ans ^= c[i];
i &= i - 1;
}
return ans;
}
int main(){
cin>>n>>m;
int t,l,r;
while (m--){
cin>>t>>l;
if (t == 1){
cin>>r;
a(l);
a(r + 1);
}else cout<<g(l)<<endl;
}
return 0;
}
C 解法, 执行用时: 127ms, 内存消耗: 980K, 提交时间: 2022-12-07 21:15:48
#include <stdio.h>
int N, M, B[100001];
inline void A(int i) { for (; i <= N; i += i & -i) B[i] ^= 1; }
inline int Q(int i) { int A = 0; for (; i; i -= i & -i) A ^= B[i]; return A; }
int main() {
scanf("%d%d", &N, &M);
while (M--) {
int opt, l, r;
scanf("%d%d", &opt, &l);
if (opt == 1) A(l), scanf("%d", &r), A(r + 1);
else printf("%d\n", Q(l));
}
return 0;
}