Codeforces Round #271(Div. 2) F 세그먼트 트리 +pair

링크:여기 찌르기
F. Ant colony
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard 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].
Examples
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.
제목:
n개의 수를 주다.T그룹 질문 l, r
그룹마다 [l, r]를 물어보면 출력 구간 길이를 구간에서 모든 구간에서 제거할 수 있는 개수를 줄여야 한다(한 개는 전체 구간에서 제거할 수 있다)
사고방식: 두 가지 기교, 투어리스트를 보면 정말 좋은 기교
나의 사고방식: 라인 트리 유지 보수 세 가지 권한, 한 구간 gcd값, 구간min값, 구간min값이 나타난 개수
그리고 모든 질문에 대해 전체 구간을 정제할 수 있는 것은 구간의 최소값이 구간의 gcd값이다.최소치의 개수를 빼면 됩니다.
코드:

#include
#include
#include
#include
#include
#include
#include 
#include
#include
#include
#include
#include
#include
#include
#define mst(ss,b) memset((ss),(b),sizeof(ss))
///#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
#define INF (1ll<<60)-1
#define Max 1e10
using namespace std;
int n;
int a[100100];
int mn[500100],g[500100],num[500100];
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
void pushup(int root){
    g[root]=gcd(g[root*2],g[root*2+1]);
    if(mn[root*2]mn[root*2+1]){
        mn[root]=mn[root*2+1];
        num[root]=num[root*2+1];
    } else if(mn[root*2]==mn[root*2+1]){
        mn[root]=mn[root*2];
        num[root]=num[root*2]+num[root*2+1];
    }
}
void build(int root,int l,int r){
    if(l==r){
        num[root]=1;
        mn[root]=a[l];
        g[root]=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build(root*2,l,mid);
    build(root*2+1,mid+1,r);
    pushup(root);
}
int query1(int root,int l,int r,int x,int y){
    if(x<=l && y>=r){
        return g[root];
    }
    int mid=(l+r)/2;
    if(y<=mid) return query1(root*2,l,mid,x,y);
    else if(x>mid) return query1(root*2+1,mid+1,r,x,y);
    else {
        return gcd(query1(root*2,l,mid,x,mid),query1(root*2+1,mid+1,r,mid+1,y));
    }
}
int Num,Mn;
void query3(int root,int l,int r,int x,int y){
    if(x<=l && y>=r){
        if(Mn>mn[root]){
            Mn=mn[root];
            Num=num[root];
        } else if(Mn==mn[root]){
            Num+=num[root];
        }
        return ;
    }
    int mid=(l+r)/2;
    if(x<=mid) query3(root*2,l,mid,x,y);
    if(y>mid) query3(root*2+1,mid+1,r,x,y);
}
int main(){
    int T;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    scanf("%d",&T);
    while(T--){
        int l,r;
        scanf("%d%d",&l,&r);
        int Gcd=query1(1,1,n,l,r);
        Num=0;Mn=Max;
        query3(1,1,n,l,r);
        ///printf("%d %d %d
",Gcd,Mn,Num);
        if(Gcd==Mn){
            printf("%d
",r-l+1-Num);
        } else printf("%d
",r-l+1);
    }
    return 0;
}

다음은tourist의: 라인 트리 유지보수 구간의 gcd값입니다.
pair는 현재 i개수에 대응하는 값으로 gcd값과 위치번호를 표시합니다.
그리고 순서를 정하십시오. 여기pair는 기본적으로 첫 번째 키워드에 따라 순서를 정합니다.첫 번째 키워드가 같으면 두 번째 키워드로 정렬을 할게요.
각 그룹에 대해 [l, r]를 묻고 알 수 있는 구간의 gcd 값을 묻습니다.
2분은 이 gcd값이pair안에 대응하는 위치를 찾아내고pair안에 gcd가 여러 개 나타날 때 첫 번째>=현재 문의하는 l과 r+1을 찾아낸다.
각각 x와 y이다
그리고 공헌은 r-l+1-(y-x)
코드:

#include
#include
#include
#include
#include
#include
#include 
#include
#include
#include
#include
#include
#include
#include
#define mst(ss,b) memset((ss),(b),sizeof(ss))
///#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
#define INF (1ll<<60)-1
#define Max 1e10
using namespace std;
int n;
int a[100100];
int g[500100];
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
void pushup(int root){
    g[root]=gcd(g[root*2],g[root*2+1]);
}
void build(int root,int l,int r){
    if(l==r){
        g[root]=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build(root*2,l,mid);
    build(root*2+1,mid+1,r);
    pushup(root);
}
int query1(int root,int l,int r,int x,int y){
    if(x<=l && y>=r){
        return g[root];
    }
    int mid=(l+r)/2;
    if(y<=mid) return query1(root*2,l,mid,x,y);
    else if(x>mid) return query1(root*2+1,mid+1,r,x,y);
    else {
        return gcd(query1(root*2,l,mid,x,mid),query1(root*2+1,mid+1,r,mid+1,y));
    }
}
pair p[100100];
int main(){
    int T;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        p[i]=make_pair(a[i],i);
    }
    sort(p+1,p+n+1);
    build(1,1,n);
    scanf("%d",&T);
    while(T--){
        int l,r;
        scanf("%d%d",&l,&r);
        int Gcd=query1(1,1,n,l,r);
        int x=lower_bound(p+1,p+n+1,make_pair(Gcd,l))-p;
        int y=lower_bound(p+1,p+n+1,make_pair(Gcd,r+1))-p;
        printf("%d
",r-l+1-(y-x));
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

백준 알고리즘 14427번 : 수열과 쿼리 15

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Codeforces Round #271(Div. 2) F 세그먼트 트리 +pair

좋은 웹페이지 즐겨찾기