frankchenfu 的博客

frankchenfu 的博客

题解 P1890 【gcd区间】

posted on 2019-07-18 11:09:19 | under 题解 |

不得不说,这是一道线段树好题

一看到这道题就想到了线段树——但是询问有$10^6$,怎么办?

哈!zkw线段树,满足您的的各种卡常需求

实测zkw线段树在只有区间加、区间max/min的时候可以跑过$1.8\times 10^7$次操作(包括区间查询和单点修改);

而如果加上一些$\log$级别的询问,一般也可以过$5\times 10^6$的数据。

等一下……这道题不需要修改?那么预处理是$n=1000$的$n\log_2 n$,查询是$m\log_2 n\times \ln n$(gcd复杂度)。

因此这道题就可以zkw线段树快速解决。

顺带提醒一下楼下的几位dalao:你们都知道可以用线段树了还不写zkw,难道你准备被noip的老爷机卡常吗???

#include<cstdio>
#include<cstring>
const int MAXN=4010;

int d[MAXN];
int n,m,bit;

int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}

void build(int n){
    for(bit=1;bit<=n+1;bit<<=1);
    for(int i=bit+1;i<=bit+n;i++)
        scanf("%d",&d[i]);
    for(int i=bit-1;i;i--)
        d[i]=gcd(d[i<<1],d[i<<1|1]);
}
void update(int x,int y){
    for(d[x+=bit]=y,x>>=1;x;x>>=1)
        d[x]=gcd(d[x<<1],d[x<<1|1]);
}
int query(int s,int t){
    int ans=d[s+bit];
    for(s+=bit-1,t+=bit+1;s^t^1;s>>=1,t>>=1){
        if(~s&1)
            ans=gcd(ans,d[s^1]);
        if(t&1)
            ans=gcd(ans,d[t^1]);
    }
    return ans;
}

int main(){
    scanf("%d%d",&n,&m);
    build(n);
    for(int i=1;i<=m;i++){
        int l,r;scanf("%d%d",&l,&r);
        printf("%d\n",query(l,r));
    }
    return 0;
}