P10401 「XSOI-R1」区间操作 题解

· · 题解

一道很有意思的预处理题目。

先将所有数据读入，然后处理出 a 数组的前缀和 sum，其中 sum_i=a_1+a_2+a_3+\cdots+a_i，接下来递推求出询问的答案：双重循环顺序遍历出所有可能的询问，循环变量为 i,j(1\le n\le10^4)，用 temp 记录 l=i 且 r=j 的询问的答案，则 l=i 且 r=j+1 的询问的答案为 temp\oplus(sum_{j+1}-sum_i)，若 j=1，则 temp 为 a_i，若测试数据中有 l=i 且 r=j 的询问，则将当前的 temp 计入答案，具体实现见代码。代码如下：

#include <cstdio>
#include <cctype>
#include <utility>
#include <map>

namespace quick_output { //快速输出
    int len = 0;
    char out[(1 << 24) + 1];
    inline void putc(char ch) {
        out[len] = ch;
        ++len;
    }
    template <typename T> inline void write(T x) {
        if (x < 0) {
            putc('-');
            x = -x;
        }
        if (x > 9)
            write(x / 10);
        out[len] = x % 10 + 48;
        ++len;
    }
    inline void flush() {
        fwrite(out, 1, len, stdout);
        len = 0;
    }
}

using namespace std;
using namespace quick_output;

bool q[10005][10005]; //q[i][j] 表示是否存在 l=i 且 r=j 的询问
int n, Q, l[1000005], r[1000005];
long long temp;
long long a[10005], sum[10005];
map<pair<int, int>, long long> ans; //ans[{i,j}] 记录 l=i 且 r=j 的询问的答案

int main() {
    scanf("%d%d", &n, &Q);
    for (register int i = 1; i <= n; ++i)
        scanf("%lld", a + i);
    for (register int i = 1; i <= Q; ++i) {
        scanf("%d%d", l + i, r + i);
        q[l[i]][r[i]] = true;
    }
    for (register int i = 1; i <= n; ++i) //求 a 数组的前缀和
        sum[i] = sum[i - 1] + a[i];
    for (register int i = 1; i <= n; ++i) {
        temp = a[i];
        if (q[i][i]) //不要忽略 l=i 且 r=i 的询问
            ans[make_pair(i, i)] = temp;
        for (register int j = i + 1; j <= n; ++j) {
            temp ^= (sum[j] - sum[i - 1]); //更新 temp
            if (q[i][j]) //如果有询问 i,j
                ans[make_pair(i, j)] = temp; //记录答案
        }
    }
    for (register int i = 1; i <= Q; ++i) {
        write(ans[make_pair(l[i], r[i])]);
        putc('\n');
    }
    flush();
    return 0;
}

时间复杂度为 O(n^2\log_2n+q)，但实际上，其语句频度为 T(n\times2+q\times2+\dfrac{n^2\log_2n}{2})，带入极限数据为 T(10^4\times2+10^6\times2+\dfrac{(10^4)^2\times\log_2(10^4)}{2})\approx T(6.66405619\times10^8)，由于计算机性能不可避免地提升，所以略微卡卡常是可以过的。AC 链接