【分块，莫队】【P4396】【AHOI2013】作业

Description

此时己是凌晨两点，刚刚做了Codeforces的小A掏出了英语试卷。英语作业其实不算多，一个小时刚好可以做完。然后是一个小时可以做完的数学作业，接下来是分别都是一个小时可以做完的化学，物理，语文......小A压力巨大。

这是小A碰见了一道非常恶心的数学题，给定了一个长度为n的数列和若干个询问，每个询问是关于数列的区间表示数列的第\(l\)个数到第\(r\)个数)，首先你要统计该区间内大于等于\(a\)，小于等于\(b\)的数的个数，其次是所有大于等于\(a\)，小于等于\(b\)的，且在该区间中出现过的数值的个数。

小A望着那数万的数据规模几乎绝望，只能向大神您求救，请您帮帮他吧。

Input

第一行是两个正整数\(n,m\)

第二行\(n\)个数代表序列

接下来\(m\)行询问，每行四个整数\(l,r,a,b\)

Output

对每个询问输出一行两个用空格隔开的整数，分别代表答案

Hint

\(Forall:\)

\(1~\leq~n,m~\leq100000\)

Solution

多次查询没有修改，于是考虑莫队

一个非常显然的想法是对每个值的出现次数开桶，对第二问开权值桶，然后用树状数组维护前缀和，就可以做到单点修改区间查询了。复杂度\(O(n~\sqrt{n}~logm+mlogm)\)，其中\(O(n~\sqrt{n}~logm)\)是修改复杂度，\(O(mlogm)\)是查询复杂度。于是发现前面一项复杂度过高，而后面一项完全不需要做到这样的复杂度。在一个操作复杂度过高，另一个操作复杂度压缩过度时，可以考虑将其中一个的复杂度降低，提升另一个的复杂度。比如这里考虑使用分块维护桶，单次修改复杂度\(O(1)\)，查询复杂度\(O(\sqrt{n})\)，总复杂度\(~O(~(n+m)~\sqrt{n}~)~\)，可以通过本题

Code

#include<cmath>

#include<cstdio>

#include<algorithm>

#ifdef ONLINE_JUDGE

#define freopen(a,b,c)

#endif

#define rg register

#define ci const int

#define cl const long long

typedef long long int ll;

template <typename T>

inline void qr(T &x) {

    rg char ch=getchar(),lst=' ';

    while((ch > '9') || (ch < '0')) lst=ch,ch=getchar();

    while((ch >= '0') && (ch <= '9')) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

    if(lst == '-') x=-x;

}

namespace IO {

    char buf[120];

}

template <typename T>

inline void qw(T x,const char aft,const bool pt) {

    if(x < 0) {x=-x,putchar('-');}

    rg int top=0;

    do {IO::buf[++top]=x%10+'0';} while(x/=10);

    while(top) putchar(IO::buf[top--]);

    if(pt) putchar(aft);

}

const int maxn = 100010;

int n,m;

int MU[maxn],belong[maxn],sa[maxn],bsa[maxn],sb[maxn],bsb[maxn];

struct Ask {

    int l,r,a,b,num;

    ll ans1,ans2;

    inline bool operator<(const Ask &_others) const {

        if(belong[this->l] != belong[_others.l]) return this->l < _others.l;

        if(belong[this->l] & 1) return this->r < _others.r;

        return this->r > _others.r;

    }

};

Ask ask[maxn];

inline bool cmp(const Ask &_a,const Ask &_b) {

    return _a.num < _b.num;

}

int main() {

    qr(n);qr(m);

    for(rg int i=1;i<=n;++i) qr(MU[i]);

    for(rg int i=1;i<=m;++i) {

        qr(ask[i].l);qr(ask[i].r);qr(ask[i].a);qr(ask[i].b);ask[i].num=i;

    }

    for(rg int i=1,sn=sqrt(n);i<=n;++i) belong[i]=i/sn;

    std::sort(ask+1,ask+1+m);

    int prel=ask[1].l,prer=ask[1].l-1;

    for(rg int i=1;i<=m;++i) {

        int l=ask[i].l,r=ask[i].r;

        while(prel < l) {

            if(!(--sa[MU[prel]])) --sb[MU[prel]],--bsb[belong[MU[prel]]];

            --bsa[belong[MU[prel]]];

            ++prel;

        }

        while(prel > l) {

            --prel;

            if(!sa[MU[prel]]) ++sb[MU[prel]],++bsb[belong[MU[prel]]];

            ++bsa[belong[MU[prel]]];++sa[MU[prel]];

        }

        while(prer < r) {

            ++prer;

            if(!sa[MU[prer]]) ++sb[MU[prer]],++bsb[belong[MU[prer]]];

            ++bsa[belong[MU[prer]]];++sa[MU[prer]];

        }

        while(prer > r) {

            if(!(--sa[MU[prer]])) --sb[MU[prer]],--bsb[belong[MU[prer]]];

            --bsa[belong[MU[prer]]];

            --prer;

        }

        ll &ans1=ask[i].ans1,&ans2=ask[i].ans2;

        int &a=ask[i].a,&b=ask[i].b;

        int bl=belong[ask[i].a],br=belong[ask[i].b];

        if(bl == br) {

            for(rg int i=a;i<=b;++i) ans1+=sa[i],ans2+=sb[i];

            continue;

        }

        for(rg int i=bl+1;i<br;++i) ans1+=bsa[i],ans2+=bsb[i];

        for(rg int i=a;belong[i] == bl;++i) ans1+=sa[i],ans2+=sb[i];

        for(rg int i=b;belong[i] == br;--i) ans1+=sa[i],ans2+=sb[i];

    }

    std::sort(ask+1,ask+1+m,cmp);

    for(rg int i=1;i<=m;++i) {

        qw(ask[i].ans1,' ',true);

        qw(ask[i].ans2,'\n',true);

    }

    return 0;

}

Summary

修改复杂度过高，查询复杂度压缩过度时，考虑使用分块平衡复杂度。

巴特西