BZOJ 3809 Gty的二逼妹子序列(莫队+分块)

发布时间:2017-7-1 11:46:35编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"BZOJ 3809 Gty的二逼妹子序列(莫队+分块) ",主要涉及到BZOJ 3809 Gty的二逼妹子序列(莫队+分块) 方面的内容,对于BZOJ 3809 Gty的二逼妹子序列(莫队+分块) 感兴趣的同学可以参考一下。

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

【题目大意】

  给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n),
  对于m(1<=m<=1000000)次询问“l,r,a,b”,
  每次输出sl...sr中,权值∈[a,b]的权值的种类数。

【题解】

  用莫队维护,对于修改操作用树状数组,
  发现复杂度为O(msqrtnlogn),难以接受,
  考虑用分块处理整数序列,修改操作O(1),查询操作O(sqrt(n))
  总复杂度O(msqrt(n)+mlog(m))

【代码】

#include <cstdio>
#include <algorithm>
#include <cmath>
const int N=100001,M=1000001;
using namespace std;
typedef long long LL;
int size[N],ans[M],pos[N],color[N],c[400],n,m,limit,bl[400],br[400];
struct Q{
    int l,r,id,a,b;
    friend bool operator < (const Q &a,const Q &b){
        return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&a.r<b.r);
    }
}ask[M];
bool cmp(const Q &a,const Q &b){return a.id<b.id;}
void read(int&a){
    char ch;while(!((ch=getchar())>='0')&&(ch<='9'));
    a=ch-'0';while(((ch=getchar())>='0')&&(ch<='9'))a*=10,a+=ch-'0';
}
int query(int x,int y){
    int res=0;
    int L=pos[x],R=pos[y];
    for(int i=L+1;i<R;i++)res+=c[i];
    if(L==R){for(int i=x;i<=y;i++)if(size[i])res++;}
    else{
        for(int i=x;i<=br[L];i++)if(size[i])res++;
        for(int i=bl[R];i<=y;i++)if(size[i])res++;
    }return res;
}
void modify(int u,int x){
    if(size[color[u]]==1&&x==-1)c[pos[color[u]]]--;
    if(size[color[u]]==0&&x==1)c[pos[color[u]]]++;
    size[color[u]]+=x;
}
int main(){
    read(n);read(m);
    limit=(int)sqrt(n+0.5);
    for(int i=1;i<=n;i++){read(color[i]);pos[i]=(i-1)/limit+1;}
    for(int i=1;i<=n;i++){br[pos[i]]=i;if(!bl[pos[i]])bl[pos[i]]=i;}
    for(int i=1;i<=m;i++){read(ask[i].l);read(ask[i].r);read(ask[i].a);read(ask[i].b);ask[i].id=i;}
    sort(ask+1,ask+m+1);
    for(int i=1,l=1,r=0;i<=m;i++){
        while(r<ask[i].r)modify(++r,1);  
        while(r>ask[i].r)modify(r--,-1);  
        while(l<ask[i].l)modify(l++,-1);  
        while(l>ask[i].l)modify(--l,1);
        ans[ask[i].id]=query(ask[i].a,ask[i].b);
    }for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;


上一篇:Jmeter代理服务器设置
下一篇:Efficient C++ 阅读笔记

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款