P4396 [AHOI2013]作业
题目描述
此时己是凌晨两点，刚刚做了 (Codeforces) 的小 A 掏出了英语试卷。英语作业其实不算多，一个小时刚好可以做完。然后是一个小时可以做完的数学作业，接下来是分别都是一个小时可以做完的化学，物理，语文……小 A 压力巨大。
这时小 A 碰见了一道非常恶心的数学题，给定了一个长度为 (n) 的数列和若干个询问，每个询问是关于数列的区间表示数列的第 (l) 个数到第 (r) 个数)，首先你要统计该区间内大于等于 (a)，小于等于 (b) 的数的个数，其次是所有大于等于 (a)，小于等于 (b) 的，且在该区间中出现过的数值的个数。
小 A 望着那数万的数据规模几乎绝望，只能向大神您求救，请您帮帮他吧。
输入格式
第一行两个整数 (n,m)
接下来 (n) 个不超过 (10^5) 的正整数表示数列
接下来 (m) 行，每行四个整数 (l,r,a,b)，具体含义参见题意。
输出格式
输出 (m) 行，分别对应每个询问，输出两个数，分别为在 (l) 到 (r) 这段区间中大小在 ([a,b]) 中的数的个数，以及大于等于 (a)，小于等于 (b) 的，且在该区间中出现过的数值的个数（具体可以参考样例）。
输入输出样例
输入 #1
3 4
1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3
输出 #1
2 2
1 1
3 2
2 1
说明/提示
(Nleq 100000,Mleq 100000，读入的数字均为 [1,10^5]) 内的正整数。
Solution
心心念念的 值域分块(+)莫队 来了
可以发现如果没有取值在([a,b])这个限制,这道题就是 P1972 [SDOI2009]HH的项链,那么就是莫队的裸题了
那么现在虽然有了这个范围,我们依然可以用莫队的思想,先计算出出([l,r])区间内的不同值的个数和种类(裸的莫队板子),再去统计满足([a,b])值域的答案
不会莫队可以去看看博主的这篇博客(嘻~)
如果当前加入这个值之后,(cnt[])数组为1,说明这个值是第一次加入,我们把种类数(+1)
同样的,如果删除这个数之后,(cnt[])数组变为了0,说明当前区间内已经没有这个值了,我们把种类数(-1)
void add(int x) {
if((++cnt[a[x]])==1) kind[belong[a[x]]]++;
sum[belong[a[x]]]++;
}
void remove(int x) {
if(!(--cnt[a[x]])) kind[belong[a[x]]]--;
sum[belong[a[x]]]--;
}
怎么统计呢? 那么值域分块就来了
一般的分块是对序列操作,是一种优美的暴力,可以在(O(sqrt n))的时间复杂度内统计出答案.再回过头来看一看,本次的问题是不是非常的类似,因此我们就可以对值域进行分块
将询问中出现的最大值设为(maxn),我们将([0,maxn])分为(sqrt {maxn})个块
在询问中,我们把([a,b])分成([a,belong[a]*block]),([belong[a]+1,belong[b]-1]),([(belong[b]-1)*block+1,b])进行统计,和常规分块询问操作一样
这一段代码里的([l,r])就是值域([a,b]),(tot)代表总数,(cal)代表种类,大块直接统计,小块(不完整的块)暴力统计,最后返回答案(因为懒得写两个函数所以开了个结构体)
Q query(int l,int r) {
int tot=0,cal=0;
for (int i=l;i<=min(belong[l]*block,r);i++) {
if(cnt[i]) cal++;
tot+=cnt[i];
}
if(belong[l]!=belong[r]) {
for (int i=(belong[r]-1)*block+1;i<=r;i++) {
if(cnt[i]) cal++;
tot+=cnt[i];
}
}
for (int i=belong[l]+1;i<=belong[r]-1;i++) {
tot+=sum[i];
cal+=kind[i];
}
return Q{tot,cal};
}
下面是总代码
其实如果学过分块和莫队的话,应该还是比较好理解的
Code
#include<bits/stdc++.h>
#define lol long long
#define mid (l+r>>1)
#define ll(i) (i<<1)
#define rr(i) (i<<1|1)
#define in(i) (i=read())
using namespace std;
const int N=1e5+10,mod=1e9+7;
int read() {
int ans=0,f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+(i^48),i=getchar();
return ans*f;
}
int n,m,block,maxn,a[N];
int cnt[N],belong[N];
int sum[N],kind[N];
int ans1[N],ans2[N];
struct query{
int l,r,qa,qb,id,pos;
bool operator < (const query &a) const {
return pos==a.pos?r<a.r:pos<a.pos;
}
}t[N];
struct Q {int sum,cnt;};
void add(int x) {
if((++cnt[a[x]])==1) kind[belong[a[x]]]++;
sum[belong[a[x]]]++;
}
void remove(int x) {
if(!(--cnt[a[x]])) kind[belong[a[x]]]--;
sum[belong[a[x]]]--;
}
Q query(int l,int r) {
int tot=0,cal=0;
for (int i=l;i<=min(belong[l]*block,r);i++) {
if(cnt[i]) cal++;
tot+=cnt[i];
}
if(belong[l]!=belong[r]) {
for (int i=(belong[r]-1)*block+1;i<=r;i++) {
if(cnt[i]) cal++;
tot+=cnt[i];
}
}
for (int i=belong[l]+1;i<=belong[r]-1;i++) {
tot+=sum[i];
cal+=kind[i];
}
return Q{tot,cal};
}
int main() {
in(n), in(m), block=sqrt(n);
for (int i=1;i<=n;i++) in(a[i]);
for (int i=1;i<=m;i++) {
in(t[i].l), in(t[i].r);
in(t[i].qa), in(t[i].qb);
t[i].id=i, t[i].pos=(t[i].l-1)/block+1;
maxn=max(maxn,t[i].qb);
}
sort(t+1,t+1+m);
block=sqrt(maxn);
for (int i=1;i<=maxn;i++) belong[i]=(i-1)/block+1;
for (int i=1,curl=1,curr=0;i<=m;i++) {
int l=t[i].l,r=t[i].r,qa=t[i].qa,qb=t[i].qb;
while(curl<l) remove(curl++);
while(curl>l) add(--curl);
while(curr<r) add(++curr);
while(curr>r) remove(curr--);
Q ans=query(qa,qb);
ans1[t[i].id]=ans.sum;
ans2[t[i].id]=ans.cnt;
}
for (int i=1;i<=m;i++) cout<<ans1[i]<<" "<<ans2[i]<<endl;
}