基础线段树 (辣鸡的不行)
发现自己线段树除了会维护加法和乘法就啥也不会了 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
来源: https://www.cnblogs.com/Jackpei/p/10668114.html