链接:
题目大意:
给定 (n) 个数的序列 (a)。(m) 次操作,操作有两种:
- 求 (sumlimits_{i=l}^{r}a_i)。
- 把 (a_lsim a_r) 异或上 (x)。
(1le nle 10^5),(1le mle 5 imes 10^4),(0le a_ile 10^6),(1le xle 10^6)。
正文:
异或和加法的混合操作导致不能直接使用线段树,所以考虑将每个数二进制拆位。
假设 (a=(110100)_2) 要异或 (xin[0,1]):
[left{egin{matrix}aoplus 0=(110100)_2oplus (0)_2=(110100)_2&(x=0)\
aoplus 1=(110100)_2oplus (1)_2=(001011)_2&(x=1)end{matrix}
ight.]
可以发现,异或 (0) 时数不变,异或 (1) 时数取反。那我们把数根据二进制拆位,用线段树维护区间中第 (i) 位的 (1) 的个数,异或操作时 (t_x=(r-l+1)-t_x)。
代码:
const int N = 100010;
int n, t;
ll ans;
ll a[N];
struct Segment
{
struct Seg
{
ll val; int lzy;
}t[N << 2][25];
void build(int x, int l, int r)
{
if (l > r) return ;
if (l == r)
{
for (int i = 0; i <= 20; ++i)
if((a[l] >> i) & 1) t[x][i].val = 1;
return ;
}
int mid = l + r >> 1;
build (x << 1, l, mid);
build (x << 1 | 1, mid + 1, r);
for (int i = 0; i <= 20; ++i)
t[x][i].val = t[x << 1][i].val + t[x << 1 | 1][i].val;
return ;
}
void pushdown(int x, int l, int r, int i)
{
if (t[x][i].lzy)
{
t[x][i].val = (r - l + 1) - t[x][i].val;
if (l != r)
{
t[x << 1][i].lzy ^= 1;
t[x << 1 | 1][i].lzy ^= 1;
}
t[x][i].lzy = 0;
}
}
void modify(int x, int l, int r, int i, int L, int R)
{
pushdown(x, l, r, i);
if (r < L || R < l) return;
if(L <= l && r <= R)
{
t[x][i].lzy = 1;
pushdown(x, l, r, i);
return ;
}
int mid = l + r >> 1;
modify (x << 1, l, mid, i, L, R);
modify (x << 1 | 1, mid + 1, r, i, L, R);
t[x][i].val = t[x << 1][i].val + t[x << 1 | 1][i].val;
return ;
}
void query(int x, int l, int r, int L, int R)
{
for (int i = 0; i <= 20; ++i)
pushdown(x, l, r, i);
if (r < L || R < l) return;
if(L <= l && r <= R)
{
for (int i = 0; i <= 20; ++i) ans += t[x][i].val * (1ll << i);
return ;
}
int mid = l + r >> 1;
query (x << 1, l, mid, L, R);
query (x << 1 | 1, mid + 1, r, L, R);
return ;
}
}b;
int main()
{
scanf ("%d", &n);
for (int i = 1; i <= n; i++)
scanf ("%d", &a[i]);
b.build(1, 1, n);
for (scanf ("%d", &t); t--; )
{
int opt; scanf ("%d", &opt);
if (opt == 1)
{
int l, r; ans = 0;
scanf ("%d%d", &l, &r);
b.query(1, 1, n, l, r);
printf ("%lld
", ans);
}
else
{
int l, r, x;
scanf ("%d%d%d", &l, &r, &x);
for (int i = 0; i <= 20; ++i)
if ((x >> i) & 1) b.modify(1, 1, n, i, l, r);
}
}
return 0;
}