BZOJ2809 Gty的二逼妹子序列

2014.12.23 08:22 Tue| 15 visits oi_2015| 2015_刷题日常| Text

在这个莫队泛滥成灾的年代,我们能做的还有什么?

Solution

这种莫队其实就是分块套分块而已(什么逻辑?)

看起来时间复杂度并不是很乐观的说,但是事实告诉我:时间复杂度 $\mathcal O(m\sqrt n)$ 。好像可以卡时过 23333。

Code

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define M 1000005

int s[N],sum[N],cnt[N];
int n,m,block,belong[N],ans[M];

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

struct O_o
{
    int p,l,r,a,b;
    O_o(){}
    O_o(int _p):p(_p)
    {
        l=read(), r=read(), a=read(), b=read();
    }
    inline bool operator <(const O_o &x) const
    {
        return belong[l]==belong[x.l]?r<x.r:belong[l]<belong[x.l];
    }
}q[M];

inline void modify(int x,int v)
{
    if(!cnt[x]) sum[belong[x]]++;
    cnt[x]+=v;
    if(!cnt[x]) sum[belong[x]]--;
}

inline int query(int x,int y)
{
    int re=0;
    if(belong[x]==belong[y])
    {
        for(int i=x;i<=y;i++)
            if(cnt[i]) re++;
    }
    else
    {
        for(int i=x;i<=block*belong[x];i++)
            if(cnt[i]) re++;
        for(int i=belong[x]+1;i<belong[y];i++)
            re+=sum[i];
        for(int i=block*(belong[y]-1)+1;i<=y;i++)
            if(cnt[i]) re++;
    }
    return re;
}

int main()
{
    cin>>n>>m;
    block=sqrt(n);
    for(int i=1;i<=n;i++) s[i]=read(), belong[i]=(i-1)/block+1;
    for(int i=1;i<=m;i++) q[i]=O_o(i);
    sort(q+1,q+m+1);
    int l=1,r=0;
    for(int i=1;i<=m;i++)
    {
        while(l>q[i].l) modify(s[--l],1);
        while(r<q[i].r) modify(s[++r],1);
        while(l<q[i].l) modify(s[l++],-1);
        while(r>q[i].r) modify(s[r--],-1);
        ans[q[i].p]=query(q[i].a,q[i].b);
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
}