BZOJ 1878: [SDOI2009]HH的项链 – [莫队]


题目传送门(BZOJ)
>原文链接<

题解 :

莫队算法主要解决的是

区间询问, 可离线,

并且在知道[L, R]答案的情况下, 可以快速的(一般是O(1)O(\log n))求出

[L-1, R]/[L, R-1]/[L+1, R]/[L, R+1]的问题.

从一个知道一个询问的答案, 到求出另一个询问的答案, 我们只需要让它的LR一位一位挪就可以了.

秘诀就在求出答案的顺序上, 由于采用了分块的思想, 从一个询问到另一个询问, 指针跳跃的次数不会超过一个什么值(然鹅我并不会证明莫队的复杂度)

我们维护一个代表当前状态的颜色桶,

如果区间扩大, 且之前没有这个颜色, 那么当前ans++ ,

如果区间缩小, 且缩小之后该位置的颜色在桶里就没有了, 那么ans —

然后把当前ans赋给当前的询问即可

代码 :

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 510000;
const int M = 1010100;
int bkt[M], pos[N], a[N];
int n, m, nl, nr, na, ans[N<<1];
inline char nc() {
    static char buf[100000], *p1, *p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++;
}
int rd() {
    int x = 0;char c = nc();
    while(!isdigit(c)) c = nc();
    while(isdigit(c)) x=x*10+c-48, c=nc();
    return x;
}
struct Query {
    int l, r, id;
    bool operator < (const Query x) const {
        if(pos[l] == pos[x.l])
            return pos[l]&1?rx.r;
        return lq[i].l) na += (bkt[a[--nl]]++ == 0);
        while(nrq[i].r) na -= (--bkt[a[nr--]] == 0);
        ans[q[i].id] = na;
    }
    for(int i = 1; i <= m; i ++ ) write(ans[i]), *pp++='\n';
    fwrite(pbuf, 1, pp-pbuf, stdout);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注