Rabbit Kingdom HDU - 4777 (离线处理+树状数组)

2024-02-18 05:38

本文主要是介绍Rabbit Kingdom HDU - 4777 (离线处理+树状数组),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Rabbit Kingdom

 HDU - 4777 

题意:给定n个数a[i] ( 1=< i <=n) 现在给定m个询问,每个询问一个区间[l,r],问该区间有多少个数与其它所有的数互素。

1 =< n,m,a[i] <= 200000

思路:对于每个数a[i] 处理后可以得到一个区间[L,R]在这个区间里面,a[i]对所有包含i的[L,R]的子区间都能贡献一个结果。每个a[i] 得到一个三元组[L,i,R],每个询问[l,r]的结果其实就是问有多少个三元组满足 L <= l && l <= i && r >= i && r <= R;

考虑将询问按照右端点由小到大排序:考虑将 < r 的三元组信息更新过来,可是更新什么数据呢?考虑下面的情况。

对一个询问 [l,r] 和 三元组[L,i,R]的关系可能为:

L  l   r

l  L   r

L  i   l   r  

L  l   i   r        ***

l  L   i   r

只要R < r 都不用再考虑了,这样的三元组肯定不会再贡献结果。

综上看来只有***是能对结果更新的。

所以:

三元组的L来了暂时不必更新,因为没用啊,对结果无影响。

三元组的i来了我让i的数量在树状数组加1,L加1

三元组的R来了就消除对应的更新。

这样一来,每个询问的结果就应当是 [l,r]区间的i的数目 - (l,r]区间的L的数目啦。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+777;
const ll mod = 998244353LL;
vector <int> vc[maxn];
bitset <maxn> bt;
struct node{int l,m,r,x,t;node(){}node(int l,int m,int r,int x,int t):l(l),m(m),r(r),x(x),t(t){}bool operator < (const node nd) const{if(x != nd.x) return x < nd.x;return t < nd.t;}
}R[maxn],RC[maxn*2],q[maxn];
int a[maxn],last[maxn],ans[maxn];
int prime[maxn],cnt;
void get()
{prime[cnt++] = 2;prime[cnt++] = 3;for(ll i = 5,j = 2; i < maxn; i+=j,j=6-j){if(bt[i/3LL]) continue;prime[cnt++] = i;if(i > maxn/i) continue;for(ll l = i*i,v=j; l < maxn; l+=v*i,v=6-v) bt[l/3LL] = 1;}
}int sum[2][maxn];void add(int i,int x,int v)
{for(;x < maxn; x+=(x&(-x)))sum[i][x] += v;
}int getsum(int i,int x)
{int ans = 0;for(;x >= 1; x-=(x&(-x)))ans += sum[i][x];return ans;
}int main()
{get();for(int i = 0; i < cnt; i++){for(int j = prime[i];j < maxn; j+=prime[i]){vc[j].push_back(prime[i]);}}int n,m;while(scanf("%d%d",&n,&m)&&m+n){int k = 0;memset(sum,0,sizeof(sum));for(int i = 1; i < maxn; i++) last[i] = 0;for(int i = 1; i <= n; i++) scanf("%d",&a[i]);for(int i = 1; i <= n; i++){int pos = 1;for(int j = 0; j < vc[a[i]].size(); j++){pos = max(pos,last[vc[a[i]][j]]+1);last[vc[a[i]][j]] = i;}R[i].l = pos;R[i].m = i;}for(int i = 1; i <= maxn; i++) last[i] = n+1;for(int i = n; i >= 1; i--){int pos = n;for(int j = 0; j < vc[a[i]].size(); j++){pos = min(pos,last[vc[a[i]][j]]-1);last[vc[a[i]][j]] = i;}R[i].r = pos;RC[k++] = node(R[i].l,R[i].m,R[i].r,R[i].m,2);RC[k++] = node(R[i].l,R[i].m,R[i].r,R[i].r,3);//  cout << i << "l = " << R[i].l << "m = " << R[i].m << "r = " << R[i].r <<endl;}for(int i = 0; i < m; i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].x = q[i].r,q[i].t = i;sort(q,q+m);sort(RC,RC+k);int id = 0;for(int i = 0; i < m; i++){while(id < k && RC[id].x <= q[i].r){if(RC[id].x == q[i].r &&RC[id].t == 3) break;if(RC[id].t == 2){add(0,RC[id].l,1);add(1,RC[id].m,1);}else if(RC[id].t == 3){add(0,RC[id].l,-1);add(1,RC[id].m,-1);}id++;}ans[q[i].t] = getsum(1,q[i].r)-getsum(1,q[i].l-1)-(getsum(0,q[i].r)-getsum(0,q[i].l));}for(int i = 0; i < m; i++){printf("%d\n",ans[i]);}}return 0;
}

 

这篇关于Rabbit Kingdom HDU - 4777 (离线处理+树状数组)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/720209

相关文章

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没

使用C++将处理后的信号保存为PNG和TIFF格式

《使用C++将处理后的信号保存为PNG和TIFF格式》在信号处理领域,我们常常需要将处理结果以图像的形式保存下来,方便后续分析和展示,C++提供了多种库来处理图像数据,本文将介绍如何使用stb_ima... 目录1. PNG格式保存使用stb_imagephp_write库1.1 安装和包含库1.2 代码解

C#使用DeepSeek API实现自然语言处理,文本分类和情感分析

《C#使用DeepSeekAPI实现自然语言处理,文本分类和情感分析》在C#中使用DeepSeekAPI可以实现多种功能,例如自然语言处理、文本分类、情感分析等,本文主要为大家介绍了具体实现步骤,... 目录准备工作文本生成文本分类问答系统代码生成翻译功能文本摘要文本校对图像描述生成总结在C#中使用Deep

Spring Boot 整合 ShedLock 处理定时任务重复执行的问题小结

《SpringBoot整合ShedLock处理定时任务重复执行的问题小结》ShedLock是解决分布式系统中定时任务重复执行问题的Java库,通过在数据库中加锁,确保只有一个节点在指定时间执行... 目录前言什么是 ShedLock?ShedLock 的工作原理:定时任务重复执行China编程的问题使用 Shed

Redis如何使用zset处理排行榜和计数问题

《Redis如何使用zset处理排行榜和计数问题》Redis的ZSET数据结构非常适合处理排行榜和计数问题,它可以在高并发的点赞业务中高效地管理点赞的排名,并且由于ZSET的排序特性,可以轻松实现根据... 目录Redis使用zset处理排行榜和计数业务逻辑ZSET 数据结构优化高并发的点赞操作ZSET 结

微服务架构之使用RabbitMQ进行异步处理方式

《微服务架构之使用RabbitMQ进行异步处理方式》本文介绍了RabbitMQ的基本概念、异步调用处理逻辑、RabbitMQ的基本使用方法以及在SpringBoot项目中使用RabbitMQ解决高并发... 目录一.什么是RabbitMQ?二.异步调用处理逻辑:三.RabbitMQ的基本使用1.安装2.架构

一文详解Python中数据清洗与处理的常用方法

《一文详解Python中数据清洗与处理的常用方法》在数据处理与分析过程中,缺失值、重复值、异常值等问题是常见的挑战,本文总结了多种数据清洗与处理方法,文中的示例代码简洁易懂,有需要的小伙伴可以参考下... 目录缺失值处理重复值处理异常值处理数据类型转换文本清洗数据分组统计数据分箱数据标准化在数据处理与分析过

mysql外键创建不成功/失效如何处理

《mysql外键创建不成功/失效如何处理》文章介绍了在MySQL5.5.40版本中,创建带有外键约束的`stu`和`grade`表时遇到的问题,发现`grade`表的`id`字段没有随着`studen... 当前mysql版本:SELECT VERSION();结果为:5.5.40。在复习mysql外键约

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu