Codeforces Round #271 (Div. 2) F. Ant colony

news/2024/6/19 11:08:22
F. Ant colony
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mole is hungry again. He found one ant colony, consisting of n ants, ordered in a row. Each ant i (1 ≤ i ≤ n) has a strength si.

In order to make his dinner more interesting, Mole organizes a version of «Hunger Games» for the ants. He chooses two numbers l and r(1 ≤ l ≤ r ≤ n) and each pair of ants with indices between l and r (inclusively) will fight. When two ants i and j fight, ant i gets one battle point only if si divides sj (also, ant j gets one battle point only if sj divides si).

After all fights have been finished, Mole makes the ranking. An ant i, with vi battle points obtained, is going to be freed only if vi = r - l, or in other words only if it took a point in every fight it participated. After that, Mole eats the rest of the ants. Note that there can be many ants freed or even none.

In order to choose the best sequence, Mole gives you t segments [li, ri] and asks for each of them how many ants is he going to eat if those ants fight.

Input

The first line contains one integer n (1 ≤ n ≤ 105), the size of the ant colony.

The second line contains n integers s1, s2, ..., sn (1 ≤ si ≤ 109), the strengths of the ants.

The third line contains one integer t (1 ≤ t ≤ 105), the number of test cases.

Each of the next t lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n), describing one query.

Output

Print to the standard output t lines. The i-th line contains number of ants that Mole eats from the segment [li, ri].

Sample test(s)
input
5
1 3 2 4 2
4
1 5
2 5
3 5
4 5
output
4
4
1
1
Note

In the first test battle points for each ant are v = [4, 0, 2, 0, 2], so ant number 1 is freed. Mole eats the ants 2, 3, 4, 5.

In the second test case battle points are v = [0, 2, 0, 2], so no ant is freed and all of them are eaten by Mole.

In the third test case battle points are v = [2, 0, 2], so ants number 3 and 5 are freed. Mole eats only the ant 4.

In the fourth test case battle points are v = [0, 1], so ant number 5 is freed. Mole eats the ant 4.

思路:我们用L[i]表示a[i],能向左被整除的最远,R[i],向右被整除的最远,

这个直接搞是会超时的,我们用pre[a[i]]表示,前一次出现a[i]出现的位置,如果R[pre[a[i]]] >= i ,就不用求 L[i],R[i] 了

然后用线段树维护区间最小值,最小值的个数,最小值出现的id(记录一个就好)

对于 ql,qr询问,查找 区间最小值的下标id,如果 L[id] <= ql && R[id] >= qr,说明这个最小值可以整除区间所有数

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<map>
#include<ctime>
#include<bitset>
#define LL long long
#define INF 89898989
#define mod 1000000007
#define maxn 100010
#define pi acos(-1.0)
#define eps 1e-6
using namespace std;struct node
{int Min,num,id;
}tree[maxn*3] ;
int a[maxn],ql,qr ;
int L[maxn],R[maxn] ;
map<int,int>pre;
void build(int L,int R,int o )
{if(L==R){tree[o].Min = a[L] ;tree[o].num = 1 ;tree[o].id = L ;return ;}int mid=(L+R)>>1;build(L,mid,o<<1) ;build(mid+1,R,o<<1|1);if(tree[o<<1].Min<tree[o<<1|1].Min){tree[o] = tree[o<<1] ;}else if(tree[o<<1].Min > tree[o<<1|1].Min){tree[o] = tree[o<<1|1] ;}else{tree[o].Min = tree[o<<1].Min ;tree[o].num = tree[o<<1].num+tree[o<<1|1].num ;tree[o].id = tree[o<<1].id ;}
}
node find(int L,int R,int o)
{if(ql <= L && qr >=R){return tree[o] ;}int mid=(L+R)>>1 ;if(qr<= mid) return find(L,mid,o<<1) ;if(ql > mid) return find(mid+1,R,o<<1|1) ;node a = find(L,mid,o<<1) ;node b = find(mid+1,R,o<<1|1) ;if(a.Min < b.Min) return a ;else if(a.Min > b.Min) return b ;a.num += b.num ;return a ;
}
int main()
{int i,j,k,n,m;int x,y;while(scanf("%d",&n) != EOF){for( i = 1 ; i <= n ;i++)scanf("%d",&a[i]) ;build(1,n,1) ;pre.clear();for(i = 1 ; i <= n ;i++){if(pre[a[i]]){j = pre[a[i]] ;if(R[j]>=i){L[i] = L[j] ;R[i] = R[j] ;   pre[a[i]] = i ;continue ;}}j = i+1;while(j<=n && a[j]%a[i]==0)j++;R[i] = j-1;j = i-1;while(j>=1&&a[j]%a[i]==0)j--;L[i] = j+1;pre[a[i]] = i ;}node ans;int num ;cin >> m ;for( i = 1 ; i <= m;i++){scanf("%d%d",&ql,&qr) ;ans=find(1,n,1) ;x = L[ans.id] ;y = R[ans.id] ;if(x <= ql && y >= qr){num = qr-ql+1-ans.num;}else num = qr-ql+1;printf("%d\n",num);}}return 0 ;
}

  

转载于:https://www.cnblogs.com/20120125llcai/p/4009084.html


https://dhexx.cn/news/show-17202.html

相关文章

离散化+BFS HDOJ 4444 Walk

题目传送门 1 /*2 题意&#xff1a;问一个点到另一个点的最少转向次数。3 坐标离散化BFS&#xff1a;因为数据很大&#xff0c;先对坐标离散化后&#xff0c;三维(有方向的)BFS4 关键理解坐标离散化&#xff0c;BFS部分可参考HDOJ_17285 */6 #include <cstd…

jenkins持续集成入门5 - Maven项目 编译和打包-方式2

前提&#xff1a; jenkins中配置maven,jdk环境变量信息 jenkins持续集成入门4 - MAVEN&#xff0c;jdk等环境配置_小哇-CSDN博客 1 安装插件 Maven Integration 2 创建项目&#xff0c;项目类型为maven类型 3 配置拉取代码&#xff0c;再配置如下的

SQL Server 内存压力解决方案

外部压力&#xff1a; 表现形式&#xff1a; 1、total server memory ↓ 2、avilable Mbyte 平衡 3、working set ↓ 如果说SQL server的内存压库来自于外部、我们是去满足SQL server 的内存使用还是去满足外部的内存使用。 如果想SQL server省着点用的…

APP端和PHP端进行数据互通

昨天给APP端提供了一个查询用户收获地址的接口 这个接口是参考了原有其他APP接口文件写出来的&#xff0c;测试的时候总是通不过我的验证(验证手机端COOKIE与PHPCOOKIE的比对。) 百思不得其解&#xff0c;发现COOKIE获取不到&#xff0c;请教大神&#xff0c;而后看APP请求文件…

jenkins持续集成入门6 - 后缀名为.WAR的项目(tomcat运行的) 编译和打包

前提&#xff1a;配置好tomcat的项目管理权限&#xff0c;如下配置tomcat的web项目管理界面_小哇-CSDN博客 1 安装 Deploy to container插件 Jenkins本身无法实现远程部署到Tomcat的功能&#xff0c;需要安装Deploy to container插件实现 2 jenkins 添加一个用户名&#xff0c…

vb.net WPF webbrowser window.close 关闭后不触发 WindowClosing 事件 WNDPROC解决方式

&#xfeff;&#xfeff;vb.net WPF webbrowser window.close 关闭后不触发 WindowClosing 事件 WNDPROC解决方式 #Region "WPF 当浏览器窗体关闭时触发 Quit事件 "#If OnSourceInitialized ThenProtected Overrides Sub OnSourceInitialized(e As EventArgs) onloa…

优先队列运用 TOJ 4123 Job Scheduling

链接&#xff1a;http://acm.tju.edu.cn/toj/showp4123.html4123. Job SchedulingTime Limit: 1.0 Seconds Memory Limit: 65536KTotal Runs: 130 Accepted Runs: 29Given N jobs, each denoted by a 2-tuples integer (pi, ri) where pi is the processing time and ri …

jenkins持续集成入门7 - Pipeline流水线项目 两种语法方式Demo讲解

1 声明式写法 pipeline {agent anystages {stage(拉取代码) {steps {echo 拉取代码}}stage(编译构建) {steps {echo 编译构建}}stage(项目部署) {steps {echo 项目部署}}} } stages&#xff1a;代表整个流水线的所有执行阶段。通常stages只有1个&#xff0c;里面包含多个stag…

Leetcode: Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.For example, Given the following matrix:[[ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ] ] You should return [1,2,3,6,9,8,7,4,5]. 难度&#xff1a;87&#xff0c;这道…

Composite Pattern

1.将对象组合成树形结构以表示“部分--整体”的层次结构。组合模式使得用户对单个对象和组合对象的使用具有一致性。 2.Composite 模式结构图 3.实现 1 #ifndef _COMPONENT_H_ 2 #define _COMPONENT_H_3 4 class Component 5 { 6 public: 7 Component();8 virtual ~Com…