【題目鏈接】

ybt 1539：簡單題
洛谷 P5057 [CQOI2006] 簡單題

【題目考點】

1. 樹狀數組

模板題及講解：洛谷 P3374 【模板】樹狀數組

【解題思路】

解法1：樹狀數組

該有01構成數組初值都為0。
某位置的元素被修改奇數次后值為1，被修改偶數次后值為0。
因此只需要求出某位置元素被修改的次數，即可得到該位置的數值。
每次修改是讓連續的一段序列翻轉，也就是選擇數組的一段區間，將該區間中的元素取反（0變為1，1變為0）。
求某元素被修改的次數，就是求有多少個區間覆蓋的該元素。
假想存在數組：cL，cR
$c{L}_i$表示區間左端點為i的區間數。
$c{R}_i$表示區間右端點為i的區間數。
$sum{L}_i$：$cL$的前綴和，即左端點L在[1,i]范圍內的區間數
$sum{R}_i$：$cR$的前綴和，右端點R在[1,i]范圍內的區間數
分別對cL、cR數組建立樹狀數組，借助樹狀數組可以在有單點修改的情況下，以$O(\log n)$時間復雜度求出序列的前綴和。

如果區間[L, R]包含x，則區間左端點L一定小于等于x。
如果區間[L, R]的右端點R小于x，這樣的區間的左端點L也一定小于x。
考察左端點$L\le x$的區間，有兩類：

• 右端點$R<x$的區間
• 右端點$R\ge x$的區間，即包含x的區間。

左端點$L\le x$的區間數量為$sum{L}_x$。
右端點$R<x$的區間數量為$sum{R}_{x?1}$。
設包含x的區間的數量為$an{s}_x$
有:$sum{L}_x=sum{R}_{x?1}+an{s}_x$
即$an{s}_x=sum{L}_x?sum{R}_{x?1}$

具體做法：

1. 如果需要將區間[l, r]中的元素取反，則存在一個區間$[l,r]$，使$c{L}_l$增加1， $c{R}_r$增加1。樹狀數組進行相應的單點修改操作。
2. 如果需要查詢第x元素的值，則通過$an{s}_x=sum{L}_x?sum{R}_{x?1}$求出x被區間修改的次數$an{s}_x$，如果$an{s}_x$為奇數，第x元素值為1，否則第x元素值為0。

解法2：線段樹 維護區間的異或值

考慮對原數字序列進行區間修改、區間查詢。
區間修改的操作為對某區間中每個元素都進行01取反，對于由01構成的序列，01取反操作即為xor 1（異或1）操作。
因為$0xor1=1$， $1xor1=0$
區間標記tag設為本段區間中的元素需要被異或的值，即本段區間每個元素實際的值為當前值$xortag$。
注意進行區間修改、單點查詢前需要進行標記下傳。

【題解代碼】

解法1：樹狀數組

• 寫法1：為treeL、treeR設置兩套樹狀數組處理函數

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n, m, treeL[N], treeR[N];//cL[i]：左端點為i的區間數，treeL：cL的樹狀數組
int lowbit(int x)
{return x & -x;
}
void updateL(int i)//cL[i]++
{for(int x = i; x <= n; x += lowbit(x))treeL[x]++;
}
void updateR(int i)//cR[i]++
{for(int x = i; x <= n; x += lowbit(x))treeR[x]++;
}
int sumL(int i)//cL的前綴和
{int s = 0;for(int x = i; x > 0; x -= lowbit(x))s += treeL[x];return s;
}
int sumR(int i)//cR的前綴和
{int s = 0;for(int x = i; x > 0; x -= lowbit(x))s += treeR[x];return s;
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t, l, r, x;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> t;if(t == 1){cin >> l >> r;updateL(l);updateR(r);}else{cin >> x;cout << (sumL(x)-sumR(x-1))%2 << '\n';//初值為0，修改偶數次為0，修改奇數次為1 }}return 0;
}

• 寫法2：只設一套樹狀數組處理函數，傳入數組地址

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n, m, treeL[N], treeR[N];//cL[i]：左端點為i的區間數，treeL：cL的樹狀數組 cR[i]：右端點為i的區間數，treeR：cR的樹狀數組
int lowbit(int x)
{return x & -x;
}
void update(int i, int *tree)//cL[i]++，或cR[i]++。
{//傳入數組名treeL或treeR，可以修改對應傳入的tree數組for(int x = i; x <= n; x += lowbit(x))tree[x]++;
}
int sum(int i, int *tree)//求cL或cR的前綴和
{int s = 0;for(int x = i; x > 0; x -= lowbit(x))s += tree[x];return s;
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t, l, r, x;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> t;if(t == 1){cin >> l >> r;update(l, treeL);update(r, treeR);}else{cin >> x;//x為題目中的i，求x位置的值 cout << (sum(x, treeL)-sum(x-1, treeR))%2 << '\n';//初值為0，修改偶數次為0，修改奇數次為1 }}return 0;
}

解法2：線段樹 維護區間異或值

#include<bits/stdc++.h>
using namespace std;
#define N 100005
struct Node
{int val, l, r, tag;
} tree[4*N];
int n, m;
void addTag(int i)
{tree[i].tag ^= 1;tree[i].val ^= 1;
}
void pushDown(int i)
{if(tree[i].tag == 0)return;addTag(2*i);addTag(2*i+1);tree[i].tag = 0;
}
void build(int i, int l, int r)
{tree[i].l = l, tree[i].r = r;if(l == r)//tree[i].val初值都為0 return;int mid = (l+r)/2;build(2*i, l, mid);build(2*i+1, mid+1, r);
}
void update(int i, int l, int r)//a[l]~a[r]取反 
{if(tree[i].r < l || tree[i].l > r)return;if(l <= tree[i].l && tree[i].r <= r)return addTag(i);pushDown(i);update(2*i, l, r);update(2*i+1, l, r);
}
int query(int i, int x)//a[x]
{if(tree[i].l == tree[i].r)return tree[i].val;pushDown(i); if(x <= tree[2*i].r)return query(2*i, x);else//x >= tree[2*i+1].l return query(2*i+1, x);
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t, l, r, x;cin >> n >> m;build(1, 1, n);while(m--){cin >> t;if(t == 1){cin >> l >> r;update(1, l, r); }else//t == 2{cin >> x;cout << query(1, x) << '\n';}}return 0;
}