iic 深度图像 servlets woocommerce callback dns datepicker jestjs vue网页 vue特点 vue绑定点击事件 vue的优点 matlab 图像识别 mysql分页查询sql语句 linux获取当前时间 java上传图片 python配置环境 python连接mysql数据库 python的文件操作 java数组添加 java类方法 java列表 linux的安装 轮播图js代码 零基础学python workflow中文 vbs表白代码 飞猪ip 免费家谱制作软件 整站系统 backtrack3 polyworks 拼多多商家下载 驱动精灵绿色版 文件粉碎工具 软碟通u盘装系统教程 保留两位小数的函数 苹果8怎么截屏 cad拉伸命令 ae添加关键帧
当前位置: 首页 > 学习教程  > 编程语言

莫队经典例题

2020/9/19 14:34:01 文章标签:

传送门:[AHOI2013]作业

本题做法:莫队+分块(辅助).
1用莫队统计区间内每个数的个数以及所在块中数的个数和种类数.
2.分块按照值域分,整块直接加上处理后的区间的相关数据,碎块暴力枚举并统计在范围内的数.
具体看代码:

#include<bits/stdc++.h>
#define N 100005
#define in read()
#define re register
using namespace std;

int n,m,l,r,block;
int a[N],zhi,from[N],pos[N];
int num[N];
int ju[N];
int ans1[N],ans2[N];
struct zb{
int l,r,a,b,poi;}q[N];

inline int in{
	int i=0;char ch;
	while(!isdigit(ch)){ch=getchar();}
	while(isdigit(ch)){i=(i<<3)+(i<<1)+(ch-'0');ch=getchar();}
	return i;
}//读优.

inline bool cmp(zb a,zb b)
{
	return (from[a.l]!=from[b.l])?from[a.l]<from[b.l]:a.r<b.r;
}//用三目比if快一点.

inline void add(int x)
{
	num[x]++;//值为x的数的个数
	pos[from[x]]++;//x所在区间的数的个数
	if(num[x]==1)ju[from[x]]++;//x所在区间的数的种类数
	return;
}

inline void jian(int x)
{
	num[x]--;
	pos[from[x]]--;
	if(!num[x])ju[from[x]]--;
	return;
}

inline void getans(int a,int b,int id)
{
	for(int i=a;i<=min(b,from[a]*block);i++)//处理左碎块
	if(num[i])ans1[id]+=num[i],ans2[id]++;
	if(from[a]!=from[b])//若不在一个块
	{
		for(int i=(from[b]-1)*block+1;i<=b;i++)//处理右碎块
		if(num[i])ans1[id]+=num[i],ans2[id]++;
		for(int i=from[a]+1;i<=from[b]-1;i++)//处理整块
		{
			ans1[id]+=pos[i];
			ans2[id]+=ju[i];
		}
	}
	return;
}

int main()
{
	n=in,m=in;
	block=sqrt(n);
	for(re int i=1;i<=n;i++)
	a[i]=in,from[i]=(i-1)/block+1;//分块
	for(re int i=1;i<=m;i++)
	{
		q[i].l=in;
		q[i].r=in;
		q[i].a=in;
		q[i].b=in;
		q[i].poi=i;
	}
	sort(q+1,q+m+1,cmp);
	l=1,r=0;
	for(re int i=1;i<=m;i++)
	{
		while(l<q[i].l)jian(a[l++]);
		while(r<q[i].r)add(a[++r]);
		while(l>q[i].l)add(a[--l]);
		while(r>q[i].r)jian(a[r--]);//莫队基操.
		getans(q[i].a,q[i].b,q[i].poi);//分块统计ans
	}
	for(re int i=1;i<=m;i++)
	printf("%d %d\n",ans1[i],ans2[i]);
	return 0;
}

本文链接:
http://www.dtmao.cc/news_show_200125.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?