a048 - 函数增减性
題目描述
題目描述了 N 個函數，初始時都為增函數。接著有 Q 個操作，操作分為兩種：
- 修改函數的增減性：將第 i 個函數的增減性反轉。
- 查詢複合函數的增減性：給定 L 和 R，查詢 F(x) = fL(fL+1(...fR(x)...)) 的增減性，輸出 0 表示增函數，輸出 1 表示減函數。
解題思路
這題的核心在於如何有效地追蹤每個函數的增減性，並快速計算複合函數的增減性。由於函數的增減性只會在修改操作時改變，因此可以使用二進位索引樹 (Binary Indexed Tree, BIT) 來儲存每個函數的增減性狀態。BIT 的每個節點儲存一個區間的函數增減性狀態的異或值。
對於修改操作，只需要將對應函數的 BIT 節點的值進行異或操作即可。對於查詢操作，需要計算從 L 到 R 的函數增減性狀態的異或值。如果異或結果為 0，則表示複合函數是增函數；如果異或結果為 1，則表示複合函數是減函數。
BIT 的使用簡化了區間查詢和單點更新的操作，使得程式碼能夠在較短的時間內完成。
複雜度分析
- 時間複雜度: O(Q log N)，其中 Q 是操作次數，N 是函數的數量。BIT 的更新和查詢操作的時間複雜度都是 O(log N)。
- 空間複雜度: O(N)，用於儲存 BIT 陣列。
程式碼
#include <bits/stdc++.h>
#define ll long long
#define mxn 200005
#define MAXN 200005
using namespace std;
ll n,m,is,cx,cy;
struct _BIT{
ll N;
ll C[MAXN],C2[MAXN];
ll lowbit(ll x){return x&(-x);}
void init(ll n){
N=n;
memset(C,0,sizeof(C));
memset(C2,0,sizeof(C2));
}
void add(ll pos,ll val){
for(ll i=pos;i<=N;i+=lowbit(i)) C[i]+=val,C2[i]+=val*pos;
}
void range_add(ll l,ll r,ll x){
add(l,x);
add(r+1,-x);
}
ll ask(ll pos){
ll ret=0;
for(ll i=pos;i>0;i-=lowbit(i)) ret+=(pos+1)*C[i]-C2[i];
return ret;
}
ll range_ask(ll l,ll r){
return ask(r)-ask(l-1);
}
}BIT;
int main(){
cin.tie(0);cout.tie(0); ios::sync_with_stdio(0);
cin >> n >> m;
BIT.init(n+1);
for(ll ca=1;ca<=m;++ca){
cin >> is;
if(is==1){
cin >> cx;
BIT.add(cx,1);
BIT.add(cx+1,-1);
}
else{
cin >> cx >> cy;
cout << BIT.range_ask(cx,cy)%2 << "\n";
}
}
return 0;
}