• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

P4396 [AHOI2013]作业 题解(分块+莫队)

开发技术 开发技术 6小时前 2次浏览

题目链接

题目大意

所有操作均为查询操作

(a[l],a[l+1]…a[r])中有多少个数在([a,b])

以及有多少个不同的数在([a,b])

题目思路

全为查询考虑莫队

莫队的修改为(O(nsqrt{m})) 查询为(O(m))

而分块的修改一次(O(1)) 查询一次为(O(sqrt n))

正好互补,最后的复杂度为(O(msqrt n+nsqrt m))

实在太妙了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef pair<int,int> pii;
#define fi first
#define se second
#define debug printf("aaaaaaaaaaan");
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1e9+7;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m,k,block;
int a[maxn];
int num[maxn],ans[maxn][2],sum[maxn][2];
struct node{
    int l,L,r,R,id;
}q[maxn];
bool cmp(node a,node b){
    return (a.r/block)==(b.r/block)?a.l<b.l:a.r<b.r;
}
void add(int x){
    num[x]++;
    if(num[x]==1){
        sum[x/block][0]++;
    }
    sum[x/block][1]++;
}
void del(int x){
    num[x]--;
    if(num[x]==0){
        sum[x/block][0]--;
    }
    sum[x/block][1]--;
}
int get(int r,int id){
    int x=r/block-1,ans=0;
    for(int i=0;i<=x;i++){
        ans+=sum[i][id];
    }
    for(int i=r/block*block;i<=r;i++){
        if(id==0){
            if(num[i]){
                ans++;
            }
        }else{
            ans+=num[i];
        }
    }
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    block=sqrt(n);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].L,&q[i].R);
        q[i].id=i;
    }
    sort(q+1,q+1+m,cmp);
    int l=1,r=1;
    add(a[1]);
    for(int i=1;i<=m;i++){
        while(l<q[i].l) del(a[l++]);
        while(l>q[i].l) add(a[--l]);
        while(r<q[i].r) add(a[++r]);
        while(r>q[i].r) del(a[r--]);
        ans[q[i].id][0]=get(q[i].R,0)-get(q[i].L-1,0);
        ans[q[i].id][1]=get(q[i].R,1)-get(q[i].L-1,1);
    }
    for(int i=1;i<=m;i++){
        printf("%d %dn",ans[i][1],ans[i][0]);
    }
    return 0;
}


程序员灯塔
转载请注明原文链接:P4396 [AHOI2013]作业 题解(分块+莫队)
喜欢 (0)