[AHOI2013]作业

输入格式

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

接下来 \(n\) 个不超过 \(10^5\) 的正整数表示数列

接下来 \(m\) 行，每行四个整数 \(l,r,a,b\)，具体含义参见题意。

输出格式

输出 \(m\) 行，分别对应每个询问，输出两个数，分别为在 \(l\) 到 \(r\) 这段区间中大小在 \([a,b]\) 中的数的个数，以及大于等于 \(a\)，小于等于 \(b\) 的，且在该区间中出现过的数值的个数（具体可以参考样例）。

提示

\(n\leq 100000,m\leq 100000\)，读入的数字均为 \([1,10^5]\) 内的正整数。

分析

\(\text{题目分为两个问题。}\)

\(\text{一. 在}[a,b]\text{中数的个数。}\)

\(\text{二. 在}[a,b]\text{中不同数的个数。}\)

\(\text{我们先求出询问区间内有多少个数和不同数的个数。(普通莫队)}\)

\(\text{再求在}[a,b]\text{中的个数与不同的数。(值域分块)}\)

\(\text{我们将整个值域分块，块长为B，每一块开两个桶}\ num[\ ],val[\ ]\)

\(num[\ ]\text{为这一块有多少数出现在询问区间内。}\)

\(val[\ ]\text{为这一块有多少不同数出现在询问区间内。}\)

\(\text{加上莫队维护这两个桶，最后小段暴力，大段直接加。}\)

Code：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define Ld long double
const int N = 100010,SQ=500;

LL n,m,bel[N],a[N],num[SQ],val[SQ],cnt[N],sq,l=1,r=0,now=0,kind=0,ans[N][2];
struct node{
    LL l,r,id,st,ed;
}t[N];

inline LL read(){
    LL s=0,w=1;char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-'){w=-1;}ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
    return s*w;
}

void print(LL x){
    char F[200];LL cnt=0;
    if(x<0) {x=-x;putchar('-');}
    if(x==0){putchar('0');putchar(' ');return ;}
    while(x){F[++cnt]=x%10;x/=10;}
    while(cnt){putchar(F[cnt--]+'0');}
    putchar(' ');
    return ;
}

bool cmp(node a,node b){
    return bel[a.l]^bel[b.l]?a.l<b.l:((bel[a.l]&1)?a.r<b.r:a.r>b.r);
}

void add(LL pos){
    ++num[bel[a[pos]]];
    ++cnt[a[pos]];
    if(cnt[a[pos]]==1) ++val[bel[a[pos]]];
    return ;
}

void del(LL pos){
    --num[bel[a[pos]]];
    --cnt[a[pos]];
    if(!cnt[a[pos]]) --val[bel[a[pos]]];
    return ;
}

void work(LL l,LL r){//分块
    //小段暴力
    for(int i=l;i<=min(r,bel[l]*sq);i++){
        now+=cnt[i],kind+=cnt[i]>0;
    }
    if(bel[l]!=bel[r]){
        //大段直接加
        for(int i=bel[l]+1;i<bel[r];i++){
            now+=num[i],kind+=val[i];
        }
        for(int i=(bel[r]-1)*sq+1;i<=r;i++){
            now+=cnt[i],kind+=cnt[i]>0;
        }
    }
    return ;
}

int main(){
    n=read(),m=read();
    sq=sqrt(n);
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    //值域分块
    for(int i=1;i<=N-5;i++){//直接1e5分块，防止出现 a>n 的情况 
        bel[i]=(i-1)/sq+1;
    }
    for(int i=1;i<=m;i++){
        t[i].l=read(),t[i].r=read(),t[i].st=read(),t[i].ed=read();
        t[i].id=i;
    }
    //普通莫队
    sort(t+1,t+1+m,cmp);
    for(int i=1;i<=m;i++){
        LL lt=t[i].l,rt=t[i].r;
        while(l>lt) add(--l);
        while(r<rt) add(++r);
        while(r>rt) del(r--);
        while(l<lt) del(l++);
        now=0,kind=0;
        work(t[i].st,t[i].ed);
        ans[t[i].id][0]=now;
        ans[t[i].id][1]=kind;
    }
    for(int i=1;i<=m;i++){
        print(ans[i][0]);
        print(ans[i][1]);
        putchar('\n');
    }
    return 0;
}

发布时间：2022-06-14 22:54