每日一题: 小阳的贝壳(线段树维护差分数组)
小阳的贝壳
https://ac.nowcoder.com/acm/problem/26255
假设只有操作一和操作三
操作一普通线段树可以完成,操作三普通线段树也能完成
做法是维护一个数组表示节点表示区间的
由于具有传递性,所以很容易维护。
假如只有操作一和操作三
操作一普通线段树可以轻松完成,操作二的话....势必要维护一个差分数组
也就是令
在线段树上维护这个数组的关系
比如在区间内加,只需要在加以及在位置减
那么求最大的绝对值的数组,只需要维护一个表示的绝对值即可
有了和,思路就出来了
建立两颗线段树,一颗维护原数组,一颗维护差分数组
第一棵树解决区间问题,第二棵树解决区间最大差值问题
但是我没有写代码因为还有T_4
其实只需要维护差分数组的线段树就能解决区间问题
因为有定理
所以的就是原数组的和差分数组区间的
那么就好办了。
#include <bits/stdc++.h> using namespace std; #define mid (l+r>>1) #define ls (rt<<1) #define rs (rt<<1|1) #define lson ls,l,mid #define rson rs,mid+1,r const int maxn = 1e5+10; int a[maxn],b[maxn],n,m; int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } int sum[maxn<<2],cd[maxn<<2],mx[maxn<<2],laz[maxn<<2]; void pushup(int rt,int l,int r) { sum[rt] = sum[ls]+sum[rs]; cd[rt] = gcd( cd[ls],cd[rs] );//gcd mx[rt] = max( mx[ls],mx[rs] );//最大的颜色差绝对值 } void build(int rt,int l,int r)//维护区间gcd,相邻绝对值最大,区间和 { if( l==r ){ sum[rt]=b[l],cd[rt]=mx[rt]=abs(b[l]); return; } build(lson); build(rson); pushup(rt,l,r); } void update(int rt,int l,int r,int index,int val) { if( l>index||r<index ) return; if( l==r ){ sum[rt]+=val,cd[rt]=mx[rt]=abs(sum[rt]); return; } update(lson,index,val); update(rson,index,val); pushup(rt,l,r); } int asksum(int rt,int l,int r,int L,int R)//群问区间和 { if( l>R||r<L ) return 0; if( l>=L&&r<=R ) return sum[rt]; return asksum(lson,L,R)+asksum(rson,L,R); } int askgcd(int rt,int l,int r,int L,int R) { if( l>R||r<L ) return 0; if( l>=L&&r<=R ) return cd[rt]; return gcd( askgcd(lson,L,R),askgcd(rson,L,R) ); } int askmax(int rt,int l,int r,int L,int R) { if( l>R||r<L ) return 0; if( l>=L&&r<=R ) return mx[rt]; return max( askmax(lson,L,R),askmax(rson,L,R) ); } int main() { cin >> n >> m; for(int i=1;i<=n;i++) scanf("%d",&a[i] ); for(int i=1;i<=n;i++) b[i] = a[i]-a[i-1]; build(1,1,n); while( m-- ) { int type,l,r,x; scanf("%d%d%d",&type,&l,&r); if( type==1 ) { scanf("%d",&x); update(1,1,n,l,x); update(1,1,n,r+1,-x); } else if( type==2 ) { if( l==r ) printf("0\n"); else printf("%d\n",askmax(1,1,n,l+1,r) ); } else { if( l==r ) printf("%d\n",asksum(1,1,n,1,l) ); else printf("%d\n",gcd( askgcd(1,1,n,l+1,r),asksum(1,1,n,1,l) ) ); } } }