維護gcd的線段樹 補發一波。。。
摘要：
基礎線段樹（辣雞的不行）
發現自己線段樹除了會維護加法和乘法就啥也不會了QWQ太菜了
瞎寫了一個維護gcd的
首先，gcd(x,y)= gcd(x,y-x) 並且很容易推廣到n個數，所以我們可以把原陣列差分一下，
find時就左右子樹大力合併gcd，最後和左端點元素本身取...
基礎線段樹（辣雞的不行）
發現自己線段樹除了會維護加法和乘法就啥也不會了QWQ太菜了
瞎寫了一個維護gcd的
首先，gcd(x,y)= gcd(x,y-x) 並且很容易推廣到n個數，所以我們可以把原陣列差分一下，
find時就左右子樹大力合併gcd，最後和左端點元素本身取gcd；
upd時就直接修改差分陣列的端點，同時用樹狀陣列維護原陣列變化量；輕鬆加愉悅。
#include<cstdio>
#include<iostream>
#include<cmath>
#define ll long long
#define R register ll
#define ls tr<<1
#define rs tr<<1|1
using namespace std;
const int N=500050;
ll w[N<<2],c[N],a[N],n,m;
inline ll g() {
R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
}
inline ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
inline void build(int tr,int l,int r) {
if(l==r) {w[tr]=a[l]-a[l-1]; return;}
R md=(l+r)>>1;
build(ls,l,md),build(rs,md+1,r);
w[tr]=gcd(w[ls],w[rs]);
}
inline ll find(int tr,int l,int r,int LL,int RR) {
if(l==LL&&r==RR) return abs(w[tr]);
R md=(l+r)>>1;
if(RR<=md) return find(ls,l,md,LL,RR);
else if(LL>md) return find(rs,md+1,r,LL,RR);
else return abs(gcd(find(ls,l,md,LL,md),find(rs,md+1,r,md+1,RR)));
}
inline void upd(int tr,int l,int r,int pos,ll inc) {
if(l==r) {w[tr]+=inc; return ;}
R md=(l+r)>>1;
if(pos<=md) upd(ls,l,md,pos,inc);
else upd(rs,md+1,r,pos,inc);
w[tr]=gcd(w[ls],w[rs]);
}
inline int lbt(int x) {return x&-x;}
inline ll ask(int pos) {R ret=0; for(;pos;pos-=lbt(pos)) ret+=c[pos]; return ret;}
inline void add(int pos,ll inc) {for(;pos<=n;pos+=lbt(pos)) c[pos]+=inc;}
signed main() {
n=g(),m=g();
for(R i=1;i<=n;++i) a[i]=g();
build(1,1,n);
while(m--) { register char ch;
while(!isalpha(ch=getchar())); register int l=g(),r=g(); R inc;
if(ch=='Q') printf("%lld\n",gcd(a[l]+ask(l),find(1,1,n,l+1,r)));
else {
inc=g();add(l,inc);upd(1,1,n,l,inc),add(r+1,-inc);
if(r<n) upd(1,1,n,r+1,-inc);
}
}
}
2019.04.07