BZOJ2821 作诗(Poetize) 分块

- 题意
- 算法
- 经验总结
- 代码

题意

不带修改,查询数列[1,n]中[l,r]内的出现正偶数次的数的个数, 数列中的数 <= 1e5, n <= 1e5, 强制在线

算法

查询的内容: 区间内出现正偶数次的数的个数.
这个内容不具有可合并性, 像区间众数一样…. (知道[l,mid]和[mid+1,r]中的答案, 不能知道[l,r]中的答案)

主席树没有想法….看来只能暴力了???

对!! 我们可以写一个 $O (n \sqrt{n})$ 的暴力—分块!!!

具体说, 我们可以先暴力开个桶预处理每两块中间的答案, 复杂度 $O (n \sqrt{n})$

(当然不能把桶扫一遍啦…因为每次指针移动桶内计数器只改变1, 所以我们可以根据前一块的答案略加修改得出后一块的答案….这个在大佬看来就是暴力?? ~~但是我没有想到~~)

对于块外的情况, 我们只需统计块外数对块内的影响. 由于块外数字最多只有 $2 \sqrt{n}$ 个, 所以我们只需要知道块内数字出现的次数(通过前缀和得到), 然后开桶暴力统计块外数字即可算出影响.

经验总结

这道题出题人真毒瘤, 卡掉了 $O (n \sqrt{n} l o g (n))$ 的算法, 只让 $O (n \sqrt{n})$ 的算法过.

一开始, 我查询时开桶扫描, 但是每次都把桶清空一遍….TLE了

之后 , 我放弃了开桶, 改为排序后统计次数.. 被卡了

但是我没想到一点… 将桶初始化时不要memset啊…只需要把这 $2 \sqrt{n}$ 个数在桶内位置清零就好了…这样我才写出了正解….

最后 , 这道题卡内存, 但是BZOJ 会把MLE 显示为TLE….太坑了….

代码

#include<bits/stdc++.h>
using namespace std;

int read(){int f = 1; char c = getchar();int ans = 0;while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}while( isdigit(c)){ans = ans*10 + c - '0';c = getchar();}ans *= f; return ans;}
//templates

const int maxn = 100005, mxsiz = 265;
int f[mxsiz][mxsiz], g[mxsiz][maxn];
int a[maxn], n, q, c, sizB, cntB;
int bl[maxn], st[maxn], ed[maxn];
int bucket[maxn];

void precalc(int curB){
    for(int i = 1; i <= c; i++) g[curB][i] = g[curB - 1][i];
    for(int i = curB*sizB - sizB + 1; i <= min(curB*sizB, n); i++){
        //if(curB == 317)printf("%d
", a[i]);
        g[curB][ a[i] ]++;
    }

    memset(bucket, 0, sizeof bucket);
    int ans = 0;
    for(int i = curB*sizB - sizB + 1; i <= n; i++){
        bucket[a[i]]++;
        if(bucket[a[i]] != 1){
            ans += (bucket[ a[i] ] & 1) ? -1 : 1;
        }

        if(ed[ i ] == i) f[curB][ bl[i] ] = ans;
    }
}

void init(){
    n = read(), c = read(), q = read();
    for(int i = 1; i <= n; i++)
        a[i] = read();
    cntB = pow(n, 0.5), cntB = min(cntB, 255);
    if(n % cntB == 0) sizB = n/cntB;
    else sizB = n / cntB + 1;
    for(int i = 1; i <= n; i++) bl[i] = (i-1) / sizB + 1;
    for(int i = 1; i <= n; i++) st[i] = (bl[i] - 1)*sizB + 1, ed[i] = min(bl[i]*sizB, n);

    for(int i = 1; i <= cntB; i++) precalc(i);
}

void solve(){
    int ans = 0;
    while(q--){
        int l = read(), r = read();
        l = (l + ans)%n + 1, r = (r+ans)%n+1;
        if(l > r) swap(l, r);

        ans = 0;
        if(r - l <= 2*sizB){
            for(int i = l; i <= r; i++) bucket[ a[i] ] = 0;
            for(int i = l; i <= r; i++){
                bucket[a[i]]++;
                if(bucket[a[i]] != 1)
                    ans += (bucket[ a[i] ] & 1) ? -1 : 1;   
            }

            printf("%d
", ans);
        } else {
            int lbl = bl[l], rbl = bl[r];
            if(l != st[l]) lbl++;
            if(r != ed[r]) rbl--;
            for(int i = l; i < lbl*sizB - sizB + 1; i++)  bucket[a[i]] = g[rbl][a[i] ] - g[lbl -1][a[i] ];
            for(int i = rbl*sizB + 1; i <= r; i++) bucket[a[i]] = g[rbl][a[i] ] - g[lbl -1][a[i] ];

            ans = f[lbl][rbl];

            for(int i = l; i < lbl*sizB - sizB + 1; i++) {
                bucket[a[i]]++;
                if(bucket[a[i]] != 1)
                    ans += (bucket[ a[i] ] & 1) ? -1 : 1;
            }
            for(int i = rbl*sizB + 1; i <= r; i++) {
                bucket[a[i]]++;
                if(bucket[a[i]] != 1)
                    ans += (bucket[ a[i] ] & 1) ? -1 : 1;
            }

            printf("%d
", ans);
        }

    }
}
signed main(){

    init();
    solve();

    return 0;
}