【题解】Luogu P1972 BZOJ P1878 【[SDOI2009]HH的项链】

背景

首先我觉得某谷的某素质管理员加强数据卡掉莫队是一个很不道德的行为,$BZOJ$上没有加强数据,莫队可以$AC$。

截图


分析

这里就直接套莫队就好了,莫队可谓区间神器,优化的大暴力。
算法核心是通过先将问询区间总长度平方分块、然后将所有的问询区间按照左端点所在的块编号排序、在同一块内的则按右端点升序

然后设置左右两个下标指针、每次都移动两个指针指向问询块的左右端点、在移动的过程中不断维护答案。

可以证明原本只通过两个下标指针移动来处理问询的方法最坏可达 $O(N*Q)$ 经过莫队算法排序后可降为$O((N+Q)\times \sqrt N)$

所以莫队算法其实就是排个序
具体请点击这里

代码

当然是经过压行处理的,尽力优化了,尽管还是没有卡进Luogu

#include<cstdio>
#include<cmath>
#include<algorithm>

inline int read(){int op = 1,ans = 0;char s = getchar();while(s < '0' || s > '9'){if(s == '-'){op = -1;}s = getchar();}while(s >= '0' && s <='9'){ans = ans * 10 + s - '0';s = getchar();}return ans *= op;;}
void print(int x){if(x < 0) putchar('-'),x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');}
void println(int x){print(x);putchar('\n');}

const int MAXN = 1000000 + 6;
int A[MAXN],LEFT[MAXN],RIGHT[MAXN],pos[MAXN],num[MAXN],ans;

class Query{
    public:int l,r,id,ans;
};Query Q[MAXN];

inline char cmp(Query q1,Query q2){return pos[q1.l] == pos[q2.l] ? q1.r < q2.r : q1.l < q2.l;}
inline char cmp1(Query q1,Query q2){return q1.id < q2.id;}
inline void add(int x){if(++num[A[x]] == 1) ++ans;}
inline void sub(int x){if(--num[A[x]] == 0) --ans;}

int main(){ 
    int n = read(),s0 = 0,s1 = 0;
    for(register int i = 1;i <= n;i++) A[i] = read();

    int sqr = sqrt(n);
    if(RIGHT[sqr] < n){sqr++;LEFT[sqr] = RIGHT[sqr - 1] + 1;RIGHT[sqr] = n;}
    for(register int i = 1;i <= sqr;i++){
        LEFT[i] = (i - 1) * sqr + 1;RIGHT[i] = i * sqr;
        for(register int j = LEFT[i];j <= RIGHT[i];j++) pos[j] = i;
    }

    int m = read();
    for(register int i = 1;i <= m;i++) Q[i].l = read(),Q[i].r = read(),Q[i].id = i;
    std::sort(Q + 1,Q + 1 + m,cmp);
    register int l = 0,r = 0;
    for(register int i = 1;i <= m;i++){
        while(r < Q[i].r) add(++r);
        while(r > Q[i].r) sub(r--);
        while(l < Q[i].l) sub(l++);
        while(l > Q[i].l) add(--l);
        Q[i].ans = ans;
    }

    std::sort(Q + 1,Q + 1 + m,cmp1);
    for(register int i = 1;i <= m;i++) println(Q[i].ans);

    return 0;
}

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

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