BZOJ3236：[AHOI2013]作业—

BZOJ3236：[AHOI2013]作业——题解

本文主要是介绍BZOJ3236：[AHOI2013]作业——题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.lydsy.com/JudgeOnline/problem.php?id=3236

第一种做法：

建两棵主席树分别处理两个问题。

第一个问题水，第二个问题参考SPOJ3267/DQUERY：D-query

但是代码量巨大，显然不能写。

第二种做法：

参考：https://blog.csdn.net/clover_hxy/article/details/56288794

对询问离线莫队，然后莫队里面套值域分块。

……值域分块还是很好写的就不讲了。

可以看出代码量巨短。

（emmm果然数据结构学傻了想的第一种做法敲了十分钟果断弃了查题解。）

（莫队还是太菜了要多练。）

#include<stack>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e5+5;
const int M=1e6+5;
inline int read(){int x=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*w;
}
struct data{int pos,l,r,a,b;
}q[M];
int a[N],cnt[N],ans[M][2],v[N],num[N],s,n,m;
inline int bel(int x){return (x-1)/s+1;}
inline bool cmp(data a,data b){return bel(a.l)==bel(b.l)?a.r<b.r:a.l<b.l;
}
inline void add(int k){if(!cnt[k])v[bel(k)]++;cnt[k]++;num[bel(k)]++;
}
inline void del(int k){cnt[k]--;num[bel(k)]--;if(!cnt[k])v[bel(k)]--;
}
void query(int pos,int l,int r){if(bel(l)==bel(r)){for(int i=l;i<=r;i++){if(cnt[i])ans[pos][1]++,ans[pos][0]+=cnt[i];}return;}for(int i=l;i<=bel(l)*s;i++)if(cnt[i])ans[pos][1]++,ans[pos][0]+=cnt[i];for(int i=(bel(r)-1)*s+1;i<=r;i++)if(cnt[i])ans[pos][1]++,ans[pos][0]+=cnt[i];for(int i=bel(l)+1;i<=bel(r)-1;i++)ans[pos][1]+=v[i],ans[pos][0]+=num[i];
}
int main(){n=read(),m=read();s=sqrt(n);for(int i=1;i<=n;i++)a[i]=read();for(int i=1;i<=m;i++){q[i].pos=i,q[i].l=read(),q[i].r=read();q[i].a=read(),q[i].b=read();}sort(q+1,q+m+1,cmp);int ql=1,qr=0;for(int i=1;i<=m;i++){while(ql<q[i].l)del(a[ql++]);while(ql>q[i].l)add(a[--ql]);while(qr<q[i].r)add(a[++qr]);while(qr>q[i].r)del(a[qr--]);query(q[i].pos,q[i].a,q[i].b);}for(int i=1;i<=m;i++){printf("%d %d\n",ans[i][0],ans[i][1]);}return 0;
}