BZOJ 3236 [Ahoi2013]作业

题目链接http://www.lydsy.com/JudgeOnline/problem.php?id=3236

题意:略。

思路:莫队,对值域进行分块,块内维护数字出现次数和种类,则每次查询的复杂度为O(\sqrt n)的,一共n次查询,则复杂度为O(n\sqrt n),修改的时候由于是O(1)的,所以修改的总时间复杂度为O(n\sqrt n),最后时间复杂度即为O(n\sqrt n)

#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9')f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
const int N=100000+10;
const int M=1000000+10;
int n,m,sz,i,l,r,a,b,s[N],block[N],cnt[N],res[N],res2[N];
struct Query{
    int l,r,a,b,id;
    bool operator<(const Query&rhs)const{
        return block[l]^block[rhs.l]?block[l]<block[rhs.l]:block[l]&1?r<rhs.r:r>rhs.r;
    }
}q[M];
pair<int,int>ans[M];
void ins(int x){if(++cnt[x]==1)res[block[x]]++;res2[block[x]]++;}
void dec(int x){if(--cnt[x]==0)res[block[x]]--;res2[block[x]]--;}
#define umin(a,b) (a>b?b:a)
pair<int,int> query(int a,int b){
    int ret=0,ret2=0,i;
    for (i=a;i<=umin(block[a]*sz,b);i++) ret2+=(cnt[i]>0),ret+=cnt[i];
    if (block[a]!=block[b]){
        for (i=(block[b]-1)*sz+1;i<=b;i++) ret2+=(cnt[i]>0),ret+=cnt[i];
    }
    for (i=block[a]+1;i<=block[b]-1;i++) ret2+=res[i],ret+=res2[i];
    return make_pair(ret,ret2);
}
int main(){
    read(n),read(m);
    sz=sqrt(n+0.5);
    for (i=1;i<=n;i++) read(s[i]),block[i]=(i-1)/sz+1;
    for (i=1;i<=m;i++){
        read(q[i].l),read(q[i].r),read(q[i].a),read(q[i].b);
        q[i].id=i;
    }
    sort(q+1,q+1+m);
    for (l=i=1,r=0;i<=m;i++){
        int L=q[i].l,R=q[i].r;
        while (r<R) ins(s[++r]);
        while (l>L) ins(s[--l]);
        while (r>R) dec(s[r--]);
        while (l<L) dec(s[l++]);
        ans[q[i].id]=query(q[i].a,q[i].b);
    }
    for (i=1;i<=m;i++) printf("%d %d\n",ans[i].first,ans[i].second);
    return 0;
}

发表评论

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