当前位置:网站首页>Codeforces 474 F. Ant colony
Codeforces 474 F. Ant colony
2022-07-07 20:47:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack .
The line segment tree seeks the GCD…..
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.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
const int maxn=100100;
typedef pair<int,int> pII;
pII b[maxn];
int n,s[maxn];
int g[maxn<<2];
int gcd(int x,int y)
{
if(x==0) return y;
return gcd(y%x,x);
}
void build(int l,int r,int rt)
{
if(l==r)
{
g[rt]=s[l];
return ;
}
int mid=(l+r)/2;
build(l,mid,rt<<1); build(mid+1,r,rt<<1|1);
g[rt]=gcd(g[rt<<1],g[rt<<1|1]);
}
int query(int L,int R,int l,int r,int rt)
{
if(r<L||l>R) return 0;
if(L<=l&&r<=R)
{
return g[rt];
}
int mid=(l+r)/2;
int u=query(L,R,l,mid,rt<<1);
int v=query(L,R,mid+1,r,rt<<1|1);
return gcd(u,v);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",s+i);
b[i]=(make_pair(s[i],i));
}
sort(b+1,b+1+n);
build(1,n,1);
int m;
scanf("%d",&m);
while(m--)
{
int Left,Right;
scanf("%d%d",&Left,&Right);
int G=query(Left,Right,1,n,1);
int from=lower_bound(b+1,b+n+1,make_pair(G,Left))-(b+1);
int to=lower_bound(b+1,b+1+n,make_pair(G,Right+1))-(b+1);
printf("%d\n",(Right-Left+1)-(to-from));
}
return 0;
}
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/116374.html Link to the original text :https://javaforall.cn
边栏推荐
- 华为CE交换机下载文件FTP步骤
- 神兵利器——敏感文件发现工具
- [concept of network principle]
- 恶魔奶爸 B2 突破语法,完成正统口语练习
- 写了个 Markdown 命令行小工具,希望能提高园友们发文的效率!
- Optimization cases of complex factor calculation: deep imbalance, buying and selling pressure index, volatility calculation
- Micro service remote debug, nocalhost + rainbow micro service development second bullet
- Small guide for rapid formation of manipulator (12): inverse kinematics analysis
- UVA 11080 – Place the Guards(二分图判定)
- Cantata9.0 | new features
猜你喜欢
如何满足医疗设备对安全性和保密性的双重需求?
使用camunda做工作流设计,驳回操作
C语言 整型 和 浮点型 数据在内存中存储详解(内含原码反码补码,大小端存储等详解)
Helix QAC 2020.2新版静态测试工具,最大限度扩展了标准合规性的覆盖范围
Optimization cases of complex factor calculation: deep imbalance, buying and selling pressure index, volatility calculation
Cantata9.0 | 全 新 功 能
Dachang classic pointer written test questions
The latest version of codesonar has improved functional security and supports Misra, c++ parsing and visualization
CodeSonar网络研讨会
Static analysis of software defects codesonar 5.2 release
随机推荐
取两个集合的交集
如何满足医疗设备对安全性和保密性的双重需求?
FTP steps for downloading files from Huawei CE switches
AADL inspector fault tree safety analysis module
H3C s7000/s7500e/10500 series post stack BFD detection configuration method
Postgresql数据库character varying和character的区别说明
Apifox interface integrated management new artifact
【OpenCV 例程200篇】223. 特征提取之多边形拟合(cv.approxPolyDP)
Airiot helps the urban pipe gallery project, and smart IOT guards the lifeline of the city
guava多线程,futurecallback线程调用不平均
Numerical method for solving optimal control problem (0) -- Definition
【网络原理的概念】
恶魔奶爸 B2 突破语法,完成正统口语练习
Introduction to referer and referer policy
Write a jump table
[paper reading] maps: Multi-Agent Reinforcement Learning Based Portfolio Management System
I wrote a markdown command line gadget, hoping to improve the efficiency of sending documents by garden friends!
Measure the height of the building
How to meet the dual needs of security and confidentiality of medical devices?
Cantata9.0 | new features