NOI.AC CSP-S全国模拟赛第四场子段与子段

题目描述

对于一个序列a1,a2,…,an，子段是指它的一个连续部分，即al,al+1,…,ar
容易发现，一个长度为n的序列有$\frac{n(n+1)}{2} $
个子段。例如序列3,7,4有下列子段：

(3),(3,7),(3,7,4),(7),(7,4),(4)

Mia希望分别求出这些子段的异或和，再将它们异或起来。但是Cierra觉得这太简单了，所以她提出了q个询问，每次给出一个区间[L,R]，希望你将这个下标区间对应的子段截取出来，回答上面的询问。

具体来说，对询问[L,R]，你需要回答aL,aL+1,…,aR的所有子段异或和的异或和。

输入格式

第一行包含两个用空格隔开的整数n,q
第二行包含n个用空格隔开的整数a1,a2,…,an
之后q行，每行包含两个用空格隔开的整数L,R，依次代表q组询问

输出格式

对每个询问输出一行，包含一个整数，为该区间所有子段异或和的异或和

样例输入

样例输出

2
6
0

数据限制

对于30%的数据，n,q≤500

对于60%的数据，n,q≤5000

对于100%的数据，1≤n,q≤200000,0≤ai≤109，每一组L,R均满足1≤L≤R≤n

时空限制

1000ms, 512MB

推式子的题目

我们这里用$\sum$表示区间异或（即用^代替+）。

题目让我们求的是$\sum_{i=l}^{r} \sum_{j=i}^{r} \sum_{k=i}^{j}a_i$.

首先我们先预处理一下前缀亦或和$s[]$，那么就是$\sum_{i=l}^{r} \sum_{j=i}^{r} s_{j}$ ^ $s_{i-1}$,发现$s_{i-1}$和 $j$无关，我们提出来之后就是

$
\sum_{i=l}^{r} s_{i-1} \times$ ( (r - i + 1 )&1) ^
$\sum_{j=i}^{r} s_{j}$

我们再对s[]数组做一次前缀和设为t[],进一步就能把式子化为
$
\sum_{i=l}^{r} s_{i-1} \times$ ( (r - i + 1 )&1) ^
$ t_{r}$ ^ $t_{i-1}$

这时就有了60分了。

我们发现前半部分s的取与不取和（r-i+1）的奇偶性有关，我们分别做一下前缀和，后半部分对$t$做一个前缀和就行了。

while (m--)
{
   l = read(); r = read(); ans = 0;
   if ((r - l + 1) & 1)ans = t[r];
   else ans = 0;

   ans ^= (p[r - 1] ^ p[l - 2]);

   if (!(r & 1))ans ^= ji[r - 1] ^ ji[max(l - 2, 0)];
   else ans ^= ou[r - 1] ^ ou[max(l - 2, 0)];
   printf("%d\n", ans);
}

这样每次就能做到$O(1)$询问了。

最后献上我的代码

#include <iostream>
#include <cstdio>
using namespace std;
int n, m, l, r, ans;
const int N = 200010;
int a[N], s[N], t[N], p[N], ji[N], ou[N];
inline int read()
{
    int res = 0; char ch = getchar(); bool XX = false;
    for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
    for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
    return XX ? -res : res;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)a[i] = read();
    for (int i = 1; i <= n; ++i)s[i] = a[i] ^ s[i - 1];
    for (int i = 1; i <= n; ++i)t[i] = s[i] ^ t[i - 1];
    for (int i = 1; i <= n; ++i)p[i] = t[i] ^ p[i - 1];

    for (int i = 1; i <= n; ++i)
        if (i & 1)ji[i] = ji[i - 1] ^ s[i];
        else ji[i] = ji[i - 1];

    for (int i = 1; i <= n; ++i)
        if (!(i & 1))ou[i] = ou[i - 1] ^ s[i];
        else ou[i] = ou[i - 1];

    while (m--)
    {
        l = read(); r = read(); ans = 0;
        if ((r - l + 1) & 1)ans = t[r];
        else ans = 0;

        ans ^= (p[r - 1] ^ p[l - 2]);

        if (!(r & 1))ans ^= ji[r - 1] ^ ji[max(l - 2, 0)];
        else ans ^= ou[r - 1] ^ ou[max(l - 2, 0)];
        printf("%d\n", ans);
    }
    return 0;
}

子段