P4135 作诗

P4135 作诗

题意：

给定 n 个不大于 c 的正整数 a1...an 和 m 组询问，每次问 [l,r] 中有多少个数出现正偶数次。
对于每次询问：
设上一个询问的答案为 ans（第一个询问时 ans=0），令L=(l+ans)mod n+1，R=(r+ans)mod n+1，若L>R，交换 L 和 R，则本次询问为[L,R]。

题解：

第一反应是莫队，但是题目明确说了是强制在线
当这种区间问题想不到什么好方法时，分块暴力就是最好的方法
首先预处理前i块内颜色为j的出现几次sum[i][j]
ans[i][j]表示第i块到第j块内有多少数出现了偶数次
cnt[i]表示i颜色出现次数（cnt每次用完都会清空）
对于每次询问，我们先求出大块内的数据以及每个数字出现个数，然后加入左侧小块，更新答案，再加入右侧小块，更新答案
其实就是很暴力很暴力的想法和做法，只是利用分块优化了复杂度
更新cnt不要用memset，直接for清空就行，不然会超时
时间复杂度 n * sqrt(n)
空间复杂度 n * sqrt(n)

代码：

这种题真正的写几遍才算明白（我写了三四遍）

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100010;
const int MAX_M = 330;
int n, m, siz, Ans;
int a[MAX_N], belong[MAX_N], cnt[MAX_N], sum[MAX_M][MAX_N], ans[MAX_M][MAX_M];

//const int Size = 1 << 16;

int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
int query(int x, int y)
{
    x = (x + Ans) % n + 1, y = (y + Ans) % n + 1;
    if (x > y) swap(x, y);
    int l = belong[x], r = belong[y];
    Ans = 0;
    if (r <= l + 1)//在一个块或者相邻两个块内，直接暴力 
    {
        for (int i = x; i <= y; ++i)
        {
            ++cnt[a[i]];
            if (!(cnt[a[i]] & 1)) ++Ans;
            else if (cnt[a[i]] > 2) --Ans;
        }
        for (int i = x; i <= y; ++i) --cnt[a[i]];
        return Ans;
    }
    Ans = ans[l + 1][r - 1];//大块内有多少数出现了偶数次
    for (int i = x; i <= l * siz; ++i)//左侧小块 
    {//加上左侧小块内的数据，看有多少数出现了偶数次 
        ++cnt[a[i]];
        if (!((cnt[a[i]] + sum[r - 1][a[i]] - sum[l][a[i]]) & 1)) ++Ans;
        else if (cnt[a[i]] + sum[r - 1][a[i]] - sum[l][a[i]] > 2) --Ans;
    }
    for (int i = (r - 1) * siz + 1; i <= y; ++i)//右侧小块 
    {//同上 
        ++cnt[a[i]];
        if (!((cnt[a[i]] + sum[r - 1][a[i]] - sum[l][a[i]]) & 1)) ++Ans;
        else if (cnt[a[i]] + sum[r - 1][a[i]] - sum[l][a[i]] > 2) --Ans;
    }
    //---清零cnt数组 
    for (int i = x; i <= l * siz; ++i) --cnt[a[i]];
    for (int i = (r - 1) * siz + 1; i <= y; ++i) --cnt[a[i]];
    return Ans;
}
int main()
{
    n = read(), read(), m = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    siz = sqrt(n) + 1;
    for (int i = 1; i <= n; ++i)
    {
        belong[i] = (i - 1) / siz + 1;
        sum[belong[i]][a[i]]++; 
    }
    for (int i = 1; i < MAX_N; ++i)
        for (int j = 1; j <= belong[n]; ++j)
            sum[j][i] += sum[j - 1][i];//前缀和 
    //sum[i][a[i]]前i个块内a[i]出现了几次 
    for (int i = 1; i <= belong[n]; ++i)//第i块内 
    {
        int now = 0;
        for (int j = (i - 1) * siz + 1; j <= n; ++j)//从第i块到最后内所有数的出现次数 
        {
            ++cnt[a[j]];
            if (!(cnt[a[j]] & 1)) ++now;//出现偶数次 
            else if (cnt[a[j]] > 2) --now;//出现奇数次就撤回 
            ans[i][belong[j]] = now;//记录i到j块内有多少数出现了偶数次 
        }
        for (int j = (i - 1) * siz + 1; j <= n; ++j)//清空cnt，不要用memset 
            --cnt[a[j]]; 
    }
    while (m--)
    {
        int x = read(), y = read();
        printf("%d\n", query(x, y));
    }
    return 0;
}