什么叫下标为 1
by LgxTpre @ 2023-09-24 18:44:41
@[LgxTpre](/user/66709) 对不起,表述有误,应当是多少个数字为1
by sunfish @ 2023-09-24 19:18:23
@[sunfish](/user/852650) 那不是区间和就行了么,树状数组也能维护啊
by LgxTpre @ 2023-09-24 19:44:46
@[LgxTpre](/user/66709) 但是这样的话不能进行异或修改吧...
我的思路是差分,树状数组维护异或,写出来大致是这个样子:
```cpp
int sum(int x)
{
int ret=0,i,j;
for(i=x;i>0;i-=(i&-i))
{
ret^=c[i];
}
return ret;
}
void add(int x,int d)
{
int i;
for(i=x;i<=N;i+=(i&-i))
{
c[i]=(c[i]^d);
}
}
```
这样可以用差分的方法,每次操作只需要add(l,1),add(r+1,1)来差分,此时sum(i)就能求对应下标为i的灯是0还是1,进而判断是熄灯还是亮灯;
差分实现了快速的区间修改,但这样的话没办法求区间和了。。。
之前做到过加法的区间和,是用了两个差分数组,但改成异或之后不知道应该怎么处理了
by sunfish @ 2023-09-24 19:59:39
@[sunfish](/user/852650) 哦我测,不好好读题造成的。那应该是不行,至少我不会/kk。
by LgxTpre @ 2023-09-24 20:24:04
@[LgxTpre](/user/66709) 那估计是不行了,还得老老实实搓线段树(
by sunfish @ 2023-09-24 20:33:37