bzoj P5016[Snoi2017]一个简单的询问——solution
2024-08-29 03:00:59
Description
给你一个长度为N的序列ai,1≤i≤N和q组询问,每组询问读入l1,r1,l2,r2,需输出
get(l,r,x)表示计算区间[l,r]中,数字x出现了多少次。
Input
第一行,一个数字N,表示序列长度。
第二行,N个数字,表示a1~aN
第三行,一个数字Q,表示询问个数。
第4~Q+3行,每行四个数字l1,r1,l2,r2,表示询问。
N,Q≤50000
N1≤ai≤N
1≤l1≤r1≤N
1≤l2≤r2≤N
注意:答案有可能超过int的最大值
-by bzoj
http://www.lydsy.com/JudgeOnline/problem.php?id=5016
一开始看错了题,以为是每次询问一个x,
然后想直接主席树;
然后很快发现题不会这么简单;
询问两个区间对应颜色出现次数相乘再求和;
两个区间,颜色;
想到离线
把一个有两个区间的询问变成两个有一个区间和一个前缀的询问作差,
然后按前缀端点排序,逐渐右移端点,维护更长的前缀,以更新询问,
这样每次前缀的端点右移时,前缀里只有一个颜色的数量增加了1,
相应的,以后要询问的区间只有这个颜色对答案的贡献增加了区间中这个颜色的个数,
然而这个颜色对答案的贡献取决于询问的区间中有多少这个颜色,
换言之取决于询问哪个区间,
一开始想用什么主席树之类的维护,死活不会,
然后一看时限3S想到分块暴力,
然后发现很科学;
然后就有了这个做法
把询问(l1,r1,l2,r2)拆成(l1,r1,pos=l2-1,-),(l1,r1,pos=r2,+)
表示
询问[l1,r1]与l2-1前缀的结果,并在原询问中减去它
询问[l1,r1]与r2前缀的结果,并在原询问中加上它
将拆成来的询问按pos从小到大排序,
按这样的顺序处理询问可以通过单向右移端点来依次维护所有询问的前缀
查询的时候,采用分块,
被整块查询的块可以直接使用一个块在当前前缀下的答案
维护方法是
在读入数列时对每个块建一个颜色桶MP[]
每右移前缀端点,使颜色col(x)个数在前缀中增加时,把每个块的答案都增加MP[col(x)]
被查询的散点,每个散点对答案的贡献是当前前缀中与这个散点颜色相同的点的个数
可以开个桶,在前缀变长时逐渐更新即可,
复杂度为$O((N+M)\sqrt{N})$
代码:
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
int sz,N,Q,num;
int a[];
LL MAP[][],inlineMAP[];
LL ANS[];
struct ss{
int L,R,pos,id;
LL flag;
}qrr[];
LL ans[];
bool cmp(ss a,ss b){
return a.pos<b.pos;
}
LL get(int ,int );
int main()
{
int i,j,k;
scanf("%d",&N);
sz=sqrt(N);
for(i=num=;i<=N;i+=sz,num++){
for(j=i;j<i+sz&&j<=N;j++){
scanf("%d",&a[j]);
MAP[num][a[j]]++;
}
}
num--;
scanf("%d",&Q);
for(i=;i<=Q;i++){
scanf("%d%d%d%d",&qrr[i].L,&qrr[i].R,&qrr[i].pos,&qrr[i+Q].pos);
qrr[i+Q].L=qrr[i].L,qrr[i+Q].R=qrr[i].R;
qrr[i+Q].id=qrr[i].id=i;
qrr[i].flag=-,qrr[i+Q].flag=;
qrr[i].pos--;
}
sort(qrr+,qrr+Q+Q+,cmp);
j=;
for(i=;i<=Q<<;i++){
while(j<qrr[i].pos){
j++;
inlineMAP[a[j]]++;
for(k=;k<=num;k++)
ANS[k]+=MAP[k][a[j]];
}
ans[qrr[i].id]+=qrr[i].flag*get(qrr[i].L,qrr[i].R);
}
for(i=;i<=Q;i++)
printf("%lld\n",ans[i]);
return ;
}
LL get(int L,int R){
LL ret=;
int i,j,k;
int l,r;
if(R-L+<=sz){
for(i=L;i<=R;i++)
ret+=inlineMAP[a[i]];
return ret;
}
for(i=j=;i<L;i+=sz,j++);
l=i-;
for(;i+sz<=R+&&i<=N;j++,i+=sz)
ret+=ANS[j];
r=i;
for(i=L;i<=l;i++)
ret+=inlineMAP[a[i]];
for(i=r;i<=R;i++)
ret+=inlineMAP[a[i]];
return ret;
}
或许有树套树的做法?
最新文章
- MLlib决策树与集成树
- 做图表统计你需要掌握SQL Server 行转列和列转行
- Express知识整理
- Windows7下安装MongoDB
- GBDT基本理论及利用GBDT组合特征的具体方法(收集的资料)
- 循环多少次?[HDU1799]
- 初步掌握Yarn的架构及原理
- ThreadPoolExecutor参数解析
- 用sqlserver处理excel表格
- HDU 1269 迷宫城堡(强连通)
- mybatis 参数为list时,校验list是否为空, mybatis ${}与#{}的区别,Mybatis sql in
- MIT6.828课程JOS在macOS下的环境配置
- [Jenkins][git]构建时提示Caused by: hudson.plugins.git.GitException: Command ";/usr/bin/git reset --hard"; returned status code 128:
- gulp和grunt 分享ppt
- python+selenium安装方法
- iOSUIWebView---快停下啦,你的愚蠢的行为
- 使用 vux 框架
- OpenCL 归约 1
- JUC——ThreadFactory线程工厂类(四)
- Linq------错误:EntityType: EntitySet &#39;Products&#39; is based on type &#39;Product&#39; that has no keys defined.
热门文章
- activemq在一台服务器上启动多个Broker
- CentOS 安装Weblogic并配置 domain
- fastjson 反序列化漏洞笔记,比较乱
- Go指南练习 rot13Reader
- golang 切片和数组在for...range中的区别
- kindEditor 使用
- 课程一(Neural Networks and Deep Learning)总结——1、Logistic Regression
- 再谈C#委托与事件
- 【从0到1学Web前端】CSS定位问题三(相对定位,绝对定位) 分类: HTML+CSS 2015-05-29 23:01 842人阅读 评论(0) 收藏
- Linux 中计划任务-at-cron