题解：P11754 [COCI 2024/2025 #5] 绘图 / Crtež
SunburstFan
·
·
题解
P11753 [COCI 2024/2025 #5] 绘图 / Crtež 题解
题目大意
给定一个长度为 n 的序列，初始全为 0。每次给定区间 [l,r]，将区间内的 0 和 -1 互相翻转。每次操作后，求出能够以当前序列为基础，进行若干次填数操作得到的互不等价序列数量。
解题思路
对于每个位置，我们只关心它是 0 还是 -1。用线段树维护区间翻转操作。
因此答案为 $3^{cnt0}$。
核心代码如下:
```cpp
// 线段树维护区间内0和-1的个数
namespace SGT{
int tree[N<<2][2],rev[N<<2]; // [0]存0的个数,[1]存-1的个数
void pushup(int rt){
tree[rt][0]=tree[rt<<1][0]+tree[rt<<1|1][0];
tree[rt][1]=tree[rt<<1][1]+tree[rt<<1|1][1];
}
void upd(int rt){
swap(tree[rt][0],tree[rt][1]); // 翻转0和-1
rev[rt]^=1;
}
void modify(int rt,int l,int r,int L,int R){
if(L<=l&&r<=R){
upd(rt);
return;
}
pushdown(rt);
int md=(l+r)>>1;
if(L<=md)modify(lson,L,R);
if(R>md)modify(rson,L,R);
pushup(rt);
}
}
// 每次查询时计算3^cnt0
printf("%lld\n",qpow(3,SGT::tree[1][0]));
```
时间复杂度 $O(q \log q)$。