acwing-246. 区间最大公约数(线段树+gcd)[通俗易懂]

acwing-246. 区间最大公约数(线段树+gcd)[通俗易懂]给定一个长度为 N 的数列 A,以及 M 条指令,每条指令可能是以下两种之一:C l r d,表示把 A[l],A[l+1],…,A[r] 都加上 d。Q l r,表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。对于每个询问,输出一个整数表示答案。输入格式第一行两个整数 N,M。第二行 N 个整数 A[i]。接下来 M 行表示 M 条指令,每条指令的格式如题目描述所示。输出格式对于每个询问,输出一个整数表示答案。每个答案占一行。数据范围N≤500000,M≤1

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给定一个长度为 N 的数列 A,以及 M 条指令,每条指令可能是以下两种之一:

C l r d,表示把 A[l],A[l+1],…,A[r] 都加上 d。
Q l r,表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。
对于每个询问,输出一个整数表示答案。

输入格式
第一行两个整数 N,M。

第二行 N 个整数 A[i]。

接下来 M 行表示 M 条指令,每条指令的格式如题目描述所示。

输出格式
对于每个询问,输出一个整数表示答案。

每个答案占一行。

数据范围
N≤500000,M≤100000,
1≤A[i]≤1018,
|d|≤1018

输入样例:
5 5
1 3 5 7 9
Q 1 5
C 1 5 1
Q 1 5
C 3 3 6
Q 2 4
输出样例:
1
2
4
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
#define lson u << 1
#define rson u << 1 | 1
struct Node{ 
   
    int l,r;
    ll gcd,sum;
}trie[N * 4];
ll a[N],d[N];
int gcd(int a,int b){ 
   
    return b == 0 ? a : gcd(b, a % b);
}
void pushup(int u){ 
   
    trie[u].sum = trie[lson].sum + trie[rson].sum;
    trie[u].gcd = gcd(trie[lson].gcd,trie[rson].gcd);
}
void build(int u,int l,int r){ 
   
    if(l == r)trie[u] = { 
   l,r,d[l],d[l]};
    else{ 
   
        trie[u] = { 
   l,r};
        int mid = (l + r) >> 1;
        build(lson,l,mid);
        build(rson,mid + 1,r);
        pushup(u);
    }
}
void modify(int u,int x,ll y){ 
   
    if(trie[u].l == x && trie[u].r == x)trie[u].sum += y,trie[u].gcd += y;
    else{ 
   
        int mid = (trie[u].l + trie[u].r) >> 1;
        if(x <= mid)modify(lson,x,y);
        else modify(rson,x,y);
        pushup(u);
    }
}
Node query(int u,int l,int r){ 
   
    if(trie[u].l >= l && trie[u].r <= r){ 
   
        Node t;
        t.sum = trie[u].sum;
        t.gcd = trie[u].gcd;
    
        return t;
    }
    int mid = (trie[u].l + trie[u].r) >> 1;
    if(r <= mid)return query(lson,l,r);
    else if(l > mid)return query(rson,l,r);
    else{ 
   
        auto left = query(lson,l,r),right = query(rson,l,r);
        Node t;
        t.sum = left.sum + right.sum;
        t.gcd = gcd(left.gcd,right.gcd);
        return t;
    }
}

int main(){ 
   
    int n,m;
    cin>>n>>m;
    ios::sync_with_stdio(false);
    for(int i = 1;i <= n;i ++){ 
   
        cin>>a[i];
        d[i] = a[i] - a[i - 1];
    }
    build(1,1,n + 1);
    char t;
    ll x,y,dd;
    for(int i = 0;i < m;i ++){ 
   
        cin>>t>>x>>y;
        if(t == 'C')cin>>dd;
        if(x > y)swap(x,y);
        if(t == 'C'){ 
   
            modify(1,x,dd);
            modify(1,y + 1,-dd);
        }
        else{ 
   
            auto left = query(1,1,x),right = query(1,x + 1,y);
            cout<<gcd(left.sum,right.gcd)<<endl;
        }
    }
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168603.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • CSV文件编辑器——Modern CSV for mac

    CSV文件编辑器——Modern CSV for mac在编辑CSV文档时,大多数人都在寻找一种高度专业的工具来帮助他们做他们想做或实际需要做的任何事情。现代CSV正是这种类型的工具。它提供了大量的选项和功能,同时快速且易于使用。考虑到这一点,当涉及到CSV文档时,这个小程序可以做正确的事情。点击安装》ModernCSVformac快速编辑多单元格编辑复制行、列和单元格。移动行、列和单元格。插入行和列。删除行和列。大文件处理加载数十亿行的文件。只读模式,可实现更高效的文件处理。加载文件的速度比Excel快1

  • 矩阵范数的等价性(原创)[通俗易懂]

    矩阵范数的等价性(原创)[通俗易懂]矩阵范数的等价设F=R”role=”presentation”>F=RF=R\mathbbF=\mathbbR或C,”role=”presentation”>C,C,\mathbbC,对于任意两个Fn×n”role=”presentation”>Fn×nFn×n\mathbbF^{n\timesn}上的范数‖⋅&#x

  • qt realease版本运行错误(qt发布release版本)

    1、在QtCreator下用release跑一遍程序,生成相应的EXE文件;2、在QtCreator下编译好的release下的ImageProcesser.exe拷贝到一个文件夹下面;3、在 ImageProcesser.exe文件路径下,输入cmd可弹出命令行窗口;4、在命令行模式下输入windeployqtImageProcessor.exe,按下回车键后会将…

  • 多态性_dna多态性的四个类型

    多态性_dna多态性的四个类型多态性的重要性:多态性是面向对象程序设计的一个强大机制:为名称相同的方法提供不同的实现方式,继承自同一基类的不同派生类可以为同名方法定义不同的功能,统一方法作用于不同类的对象,可以有不同的解释,产生

  • 一篇教会你写90%的shell脚本_flash动画脚本怎么写

    一篇教会你写90%的shell脚本_flash动画脚本怎么写如果将运维比作手链,将珍珠比作服务,那么将珍珠串起来的线就是Shell,作为实现Linux系统自动管理以及自动化运维所必备的Shell脚本,其重要性便不言而喻。每一位合格的Linux系统管理员或运维工程师,都应该将熟练编写Shell脚本视为基本技能之一,只有这样才能减少不必要的劳动。但是新人在编写脚本时却只会:#!/bin/bash,所以今天就给大家分享100个经典实用的脚本范例,手把手教你写Shell脚本。这100个脚本范例从基础到进阶均涵盖,有侧重地提高编写能力,结构清晰准确,PDF格式,可

  • 2016年TLC闪存发展趋势 美光、东芝、Intel有何策略

    2016年TLC闪存发展趋势 美光、东芝、Intel有何策略

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号