Luogu 4135 作诗

lyd大神犇的狗粮题……

终于填掉了这个大坑，之前由于有一些事情一直没有想清楚，一直没有动手写此题，就记录一下那些“有一些事情”
1、对于对答案的贡献问题
若要统计[l, r]中所有颜色的贡献：
在扫描的过程中记录出现的次数cnt，若cnt第一次变到2的时候，把当前答案加一，如果当前cnt大于二，答案应当减一

**简单分析：**当一个数第一次到达出现2次的时候，应当显然地对答案产生了贡献，当这个数在第三次出现的时候，它之前产生的贡献就被消除了，第四次出现的时候就又会被累加回来，所以这样是对的

2、复杂度分析，对于这样的块大小在块内不套log的情况下应当是取sqrt(n) 最优（然而可能我太蒟了，跑得很卡）

3、一开始犯了一个脑残的错误

pos[x] + 1 <= pos[y]

分分钟跑成暴力……

Code：

#include <cstdio>
#include <cmath>
using namespace std;

const int N = 1e5 + 5;
const int B = 320;

int n, m, c, bnum, a[N], l[B], r[B], pos[N];
int sum[B][N], ans[B][B], cnt[N];

inline void read(int &X) {
    X = 0;
    char ch = 0;
    int op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

inline void prework() {
    bnum = sqrt(n);
    for(int i = 1; i <= bnum; i++) {
        l[i] = (i - 1) * bnum + 1;
        r[i] = i * bnum;
    }
    if(r[bnum] < n) {
        bnum++;
        l[bnum] = r[bnum - 1] + 1;
        r[bnum] = n;
    }

    for(int i = 1; i <= bnum; i++)
        for(int j = l[i]; j <= r[i]; j++) {
            pos[j] = i;
            sum[i][a[j]]++;
        }
    for(int i = 1; i <= c; i++)
        for(int j = 1; j <= bnum; j++)
            sum[j][i] += sum[j - 1][i];

    for(int i = 1; i <= bnum; i++) {
        int res = 0;
        for(int j = l[i]; j <= n; j++) {
            cnt[a[j]]++;
            if(cnt[a[j]] > 0 && cnt[a[j]] % 2 == 0) res++;
            else if(cnt[a[j]] > 2) res--;
            ans[i][pos[j]] = res;
        }
        for(int j = l[i]; j <= n; j++)
            cnt[a[j]]--;
    }
}

inline void swap(int &x, int &y) {
    int t = x; 
    x = y;
    y = t;
}

int query(int x, int y) {
    int res = 0;
    if(pos[x] + 1 >= pos[y]) {
        for(int i = x; i <= y; i++) {
            cnt[a[i]]++;
            if(cnt[a[i]] > 0 && cnt[a[i]] % 2 == 0) res++;
            else if(cnt[a[i]] > 2) res--;
        }
        for(int i = x; i <= y; i++)
            cnt[a[i]]--;
    } else {
/*        for(int i = x; i <= r[pos[x]]; i++)
            cnt[a[i]]++;
        for(int i = l[pos[y]]; i <= y; i++)
            cnt[a[i]]++; */

        res = ans[pos[x] + 1][pos[y] - 1];
        for(int i = x; i <= r[pos[x]]; i++) {
            cnt[a[i]]++;
            int tmp = sum[pos[y] - 1][a[i]] - sum[pos[x]][a[i]] + cnt[a[i]]; 
/*            if(tmp > 0) {
                if(tmp % 2 == 0) {
                    if(cnt[a[i]] % 2 != 0) res--;
                } else {
                    if(cnt[a[i]] % 2 != 0) res++;
                    else res--;
                }
            } else {
                if(cnt[a[i]] > 0 && cnt[a[i]] % 2 == 0)
                    res++;
            } */
            
            if(tmp > 0 && tmp % 2 == 0) res++;
            else if(tmp > 2) res--;
        }
        for(int i = l[pos[y]]; i <= y; i++) {
            cnt[a[i]]++;
            int tmp = cnt[a[i]] + sum[pos[y] - 1][a[i]] - sum[pos[x]][a[i]]; 
/*            if(tmp > 0) {
                if(tmp % 2 == 0) {
                    if(cnt[a[i]] % 2 != 0) res--;
                } else {
                    if(cnt[a[i]] % 2 != 0) res++;
                    else res--;
                }
            } else {
                if(cnt[a[i]] > 0 && cnt[a[i]] % 2 == 0)
                    res++;
            } */

            if(tmp > 0 && tmp % 2 == 0) res++;
            else if(tmp > 2) res--;

        }

        for(int i = x; i <= r[pos[x]]; i++)
            cnt[a[i]]--;
        for(int i = l[pos[y]]; i <= y; i++)
            cnt[a[i]]--;
    }
    return res;
}

int main() {
    read(n), read(c), read(m);
    for(int i = 1; i <= n; i++)
        read(a[i]);
    prework();
    
    for(int lastAns = 0, x, y; m--; ) {
        read(x), read(y);
        x = (x + lastAns) % n + 1, y = (y + lastAns) % n + 1;
        if(x > y) swap(x, y);
        printf("%d\n", lastAns = query(x, y));
    }

    return 0;
}

优质内容筛选与推荐>>
1、网络通信 --> CRC校验
2、Codeforces Round #289 (Div. 2, ACM ICPC Rules) A. Maximum in Table【递推】
3、64_a2
4、PHP笔记02变量的作用域
5、html框架

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看