BZOJ 3781 小B的盘问 序列莫队算法

题意:链接

方法:序列莫队算法

解析:为什么用莫队？

就是高级一点的暴力。

对于这道题，让我们简单的想想复杂度。

如果是暴力淦的话那么直接N^2,T死。

所以来优化暴力。

如果我们排序一下l,r的话可能会好一点？

不过这样的话还是T，因为这明明就是赌数据的行为。

我们观察数据范围，50000，先考虑用高级点的暴力—莫队能不能过，算一下复杂度O(n√n)。差不多？

再看看每一次更改答案：O1

那直接上莫队，淦！

我们离线所有询问，对所有的询问按照左端点所在的块为第一关键字，右端点为第二关键字排序。

这样的话，每一次更新的时候，对于左端点在同一块中的询问，右端点显然是递增的，也就是说我们最多是枚举n次右端点，而同时块的大小是√n，所以右指针最多枚举了n√n次，而对于左端点来说，在块中移动是√n级别的,询问m与n同阶，所以左端点的枚举也是n√n级别的，那么总的复杂度显然是n√n级别的，这样的话直接过。

再说对于此题的更新部分，先减掉原来的，然后更新下数量，之后加上现在的。O1

代码:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 50010 
using namespace std;
int c[N];
int s[N];
int print[N]; 
int n,m,k;
int ans;
struct node
{
    int blockl,l,r,no;
}que[N];
int cmp(node a,node b)
{
    if(a.blockl==b.blockl)return a.r<b.r;
    else return a.blockl<b.blockl;
}
void update(int v,int co)
{
    ans-=s[co]*s[co];
    s[co]+=v;
    ans+=s[co]*s[co]; 
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    int sqrn=(int)sqrt(n);
    for(int i=1;i<=n;i++)scanf("%d",&c[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&que[i].l,&que[i].r);
        int tmp=0;
        tmp+=que[i].l/sqrn;
        if(que[i].l%sqrn!=0)tmp++;
        que[i].blockl=tmp;
        que[i].no=i;
    }
    sort(que+1,que+m+1,cmp);
    int tl=que[1].l,tr=que[1].r;
    for(int i=tl;i<=tr;i++)
    {
        update(1,c[i]);
    }
    print[que[1].no]=ans;
    for(int i=2;i<=m;i++)
    {
        while(que[i].l<tl)tl--,update(1,c[tl]);
        while(que[i].l>tl)update(-1,c[tl]),tl++;
        while(que[i].r<tr)update(-1,c[tr]),tr--;
        while(que[i].r>tr)tr++,update(1,c[tr]);
        print[que[i].no]=ans;
    }
    for(int i=1;i<=m;i++)printf("%d\n",print[i]);
}