简单题

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 781 字

树状数组差分区间翻转

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1539
// 题意：n 长度数组初值 0，m 条指令：t=1 翻转区间 [L,R] 每个数（0↔1）；t=2 询问下标 i 的值。n≤1e5，m≤5e5。
// 思路：区间翻转用差分数组思想：在 L 与 R+1 处各异或 1，则点 i 的值 = 前缀异或和。树状数组维护异或差分数组，单点查询即前缀异或。
// 复杂度：O((n+m) log n) 时间 / O(n) 空间
// 易错点：翻转是异或不是加减；R+1 可能越界，数组开到 n+2；查询输出 0/1。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int bit[MAXN];
void add(int i){ for(;i<MAXN;i+=i&-i) bit[i]^=1; }
int sum(int i){ int s=0; for(;i>0;i-=i&-i) s^=bit[i]; return s; }
int main(){
    int n,m;
    if(!(cin>>n>>m)) return 0;
    while(m--){
        int t;
        cin>>t;
        if(t==1){
            int L,R;
            cin>>L>>R;
            add(L); add(R+1);
        }else{
            int i;
            cin>>i;
            cout<<sum(i)<<"\n";
        }
    }
    return 0;
}

简单题

正文

一本通·提高篇的其它内容