学步园

题目大意：给出一段序列，求一段区间内的出现次数为正偶数的数的个数。

思路：50000，分块。主要的事情是处理出来两个数组，一个是整块的答案，空间复杂度为O(√n*√n)，还有一个是前缀和每一块的数字出现的次数，空间复杂度O(n*√n)。之后就是暴力了。代码很乱，要根据for来分析时间复杂度。

这个题大概不用读入优化也可以吧，就是空间比较卡。。

（要打时间戳啊！

CODE：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 320
#define _MAX 100010
using namespace std;
 
inline int getc() {
    static const int L = 1 << 15;
    static char buf[L], *S = buf, *T = buf;
    if (S == T) {
        T = (S = buf) + fread(buf, 1, L, stdin);
        if (S == T)
            return EOF;
    }
    return *S++;
}
inline int getint() {
    int c;
    while(!isdigit(c = getc()) && c != '-');
    bool sign = c == '-';
    int tmp = sign ? 0 : c - '0';
    while(isdigit(c = getc()))
        tmp = (tmp << 1) + (tmp << 3) + c - '0';
    return sign ? -tmp : tmp;
}
 
int cnt,cols,asks;
int block_size,blocks;
int src[_MAX],belong[_MAX],begin[_MAX];
int ans_block[MAX][MAX];
int cnt_block[MAX][_MAX];
 
int temp[_MAX],v[_MAX],T;
int stack[_MAX],top;
 
int main()
{
    cin >> cnt >> cols >> asks;
    block_size = sqrt(cnt);
    for(int i = 1; i <= cnt; ++i) {
        src[i] = getint();
        //scanf("%d",&src[i]);
        belong[i] = i / block_size + 1;
        if(!begin[belong[i]])   begin[belong[i]] = i;
        ++cnt_block[belong[i]][src[i]];
    }
    blocks = belong[cnt];
     
    //Making cnt_block[][](preSum
    for(int i = 2; i <= blocks; ++i)
        for(int j = 1; j <= cols; ++j)
            cnt_block[i][j] += cnt_block[i - 1][j];
     
    //Making ans_block[][];
    int now;
    for(int i = 1; i <= blocks; ++i) {
        now = 0;
        ++T;
        for(int j = begin[i]; j <= cnt + 1; ++j) {
            if(belong[j] != belong[j - 1])
                ans_block[i][belong[j - 1]] = now;
            if(v[src[j]] != T)
                v[src[j]] = T,temp[src[j]] = 0;
            if(temp[src[j]] > 0) {
                if(temp[src[j]]&1)  ++now;
                else            --now;
            }
            ++temp[src[j]];
        }
    }
    //Asking    
    int last_ans = 0;
    for(int x,y,i = 1; i <= asks; ++i) {
        x = getint(),y = getint();
        //scanf("%d%d",&x,&y);
        x = (x + last_ans) % cnt + 1;
        y = (y + last_ans) % cnt + 1;
        if(x > y)    swap(x,y);
        int st = belong[x] + 1,ed = belong[y] - 1,ans = 0;
        ++T;
        if(st > ed) {
            for(int j = x; j <= y; ++j) {
                if(v[src[j]] != T)
                    v[src[j]] = T,temp[src[j]] = 0;
                if(temp[src[j]] > 0) {
                    if(temp[src[j]]&1)  ++ans;
                    else                --ans;
                }
                ++temp[src[j]];
            }
            printf("%d\n",last_ans = ans);
            continue;
        }
        ans = ans_block[st][ed];
        top = 0;
        for(int k = x; belong[k] == belong[x]; ++k)
            stack[++top] = src[k];
        for(int k = y; belong[k] == belong[y]; --k)
            stack[++top] = src[k];
        sort(stack + 1,stack + top + 1);
        stack[top + 1] = 0;
        int num = 0;
        for(int j = 1; j <= top + 1; ++j) {
            ++num;
            if(stack[j] != stack[j + 1]) {
                int temp = cnt_block[ed][stack[j]] - cnt_block[st - 1][stack[j]];
                if(!temp)   ans += !(num&1);
                else if(num&1) {
                    if(temp&1)  ++ans;
                    else    --ans;
                }
                num = 0;
            }
        }
        printf("%d\n",last_ans = ans);
    }
    return 0;
}