[Acwing] 区间最大公约数 线段树

前言

传送门: 总体思路很流畅,就是代码不怎么好写

思路

题目要求两个操作 :

• 区间更新 : 懒标记 (难写啊！
• 区间查询 : 查询 g c d gcd gcd更不好写!

区间更新的优化 :

区间 + + + 或者 − - − 一个数 可以用 差分 变成单点操作

区间查询优化 :

根据 g c d ( a , b ) = g c d ( a , b − a ) . . . . . g c d ( a , b , c , d . . . ) = g c d ( a , b − a , c − b , . . . ) gcd(a,b) = gcd(a,b-a)..... gcd(a,b,c,d...) = gcd(a,b-a,c-b,...) gcd(a,b)=gcd(a,b−a).....gcd(a,b,c,d...)=gcd(a,b−a,c−b,...)

公式请拐弯到y总视频

因此我们只需要特殊处理 第一个点 和 后面用 差分处理 即可

CODE

#include 
using namespace std;
#define ll long long
#define ned '\n'
const int N = 5e5+10;
int n,m;
ll w[N];

struct node
{
    int l,r;
    ll sum,d;
} tr[N*4];
void pushup(node &u,node &l,node &r)
{
    u.sum = l.sum + r.sum;
    u.d = __gcd(l.d,r.d);
}

void pushup(int u)
{
    pushup(tr[u],tr[u