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

相关文章

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Python使用getopt处理命令行参数示例解析(最佳实践)

《Python使用getopt处理命令行参数示例解析(最佳实践)》getopt模块是Python标准库中一个简单但强大的命令行参数处理工具,它特别适合那些需要快速实现基本命令行参数解析的场景,或者需要... 目录为什么需要处理命令行参数?getopt模块基础实际应用示例与其他参数处理方式的比较常见问http

Java Response返回值的最佳处理方案

《JavaResponse返回值的最佳处理方案》在开发Web应用程序时,我们经常需要通过HTTP请求从服务器获取响应数据,这些数据可以是JSON、XML、甚至是文件,本篇文章将详细解析Java中处理... 目录摘要概述核心问题:关键技术点:源码解析示例 1:使用HttpURLConnection获取Resp

Java中Switch Case多个条件处理方法举例

《Java中SwitchCase多个条件处理方法举例》Java中switch语句用于根据变量值执行不同代码块,适用于多个条件的处理,:本文主要介绍Java中SwitchCase多个条件处理的相... 目录前言基本语法处理多个条件示例1:合并相同代码的多个case示例2:通过字符串合并多个case进阶用法使用

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

Python处理函数调用超时的四种方法

《Python处理函数调用超时的四种方法》在实际开发过程中,我们可能会遇到一些场景,需要对函数的执行时间进行限制,例如,当一个函数执行时间过长时,可能会导致程序卡顿、资源占用过高,因此,在某些情况下,... 目录前言func-timeout1. 安装 func-timeout2. 基本用法自定义进程subp

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

浅析Java中如何优雅地处理null值

《浅析Java中如何优雅地处理null值》这篇文章主要为大家详细介绍了如何结合Lambda表达式和Optional,让Java更优雅地处理null值,感兴趣的小伙伴可以跟随小编一起学习一下... 目录场景 1:不为 null 则执行场景 2:不为 null 则返回,为 null 则返回特定值或抛出异常场景