牛客小白月試合16-小陽の貝殻(線分樹差分+隣接最大値+区間gcd)

リンク:https://ac.nowcoder.com/acm/contest/949/H出典:牛客網
タイトルの説明
小陽の手には全部でn個の貝殻があり、各貝殻には色があり、最初のi番目の貝殻の色はcoliであった.現在、小陽には3つの操作があります.
1 l r x:[l,r]区間のすべての貝殻の色値にxxxを加える.
2 l r:[l,r]区間のすべての隣接貝殻の色値の差(絶対値をとる)の最大値を尋ねる(l=rl=rl=r出力0の場合).
3 l r:[l,r]区間のすべての貝殻の色値の最大公約数を尋ねる.
説明を入力:
1行目には、2つの正の整数n,mn,mn,mが入力され、それぞれ貝殻個数と操作個数を表す.2行目nnn個数colicol_を入力icoliは、貝殻ごとの初期色を表します.3行目からm+2 m+2 m+2行目、各行の最初の数はoptoptoptoptで、操作番号を表します.次に入力する変数は、操作番号に対応します.出力記述:共m行で、各問合せ(操作2および操作3)に対して対応する結果を出力する.例1入力5 6 2 2 3 3 3 3 1 3 3 2 4 3 3 5 1 4 2 3 3 3 3 3 5出力3 3 3 1≦n,m≦100000
1≤coli≤1000
1≤opt≤3,1≤l≤r≤n
テーマ:
セグメントツリー操作集合問題では,第1の区間更新,l−r区間の各数の値+x第2の隣接最大値,すなわち区間の各数の間に隣接する最大値の絶対値,第3の区間のgcdを求める3つの操作があることが分かった.
問題解決の考え方:
初めてこのような問題にぶつかって、いつもの区間更新はlazy配列を借りて完成したが、この問題には隣接間の距離の最大値があり、区間gcdがあることを考えると、明らかにlazyではだめだと思い、この問題を通じて差分グループの思想を学んだ.差分グループ:すなわち、配列に格納されているのは元の値ではなく、現在の数と前の数の差です.例を挙げると、元の配列1 3 5 10 8-->差分グループ1 2 2 5-2では、差分グループに接頭辞と元のn番目の項を求める法則も発見できます.差分グループの値が隣接する値であることは容易にわかりますが、差分グループの絶対値の最大値はセグメントツリーで維持できます.区間更新について:差分グループではこのように実現できるが、例を挙げると、【3,5】この区間内の各数は+2であり、差分グループには1つの差分値が格納されているので、3という位置+2で、6という位置-2で【3,5】各数が+2になる(自分で1組のデータを持ってやってみることができる).さらにgcd問題gcd(a,b)=gcd(a,b−a)も同様に差分群で実現できるので,他は変わらず,元のツリーを構築した通常の配列を差分群に変更すればよいだけで,その他の操作はセグメントツリーで実現できる.ACコード:

#include 
#include 
#include 
using namespace std;
const int _max = 1e5+50;
int a[_max];
struct node//        
{
    int sum,mx,gd;
}tree[_max<<2];
int gcd(int a,int b)//     gcd
{
    return b==0?a:gcd(b,a%b);
}
void pushup(int k)//         
{
    tree[k].mx=max(tree[k<<1].mx,tree[k<<1|1].mx);
    tree[k].gd=gcd(tree[k<<1].gd,tree[k<<1|1].gd);
    tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}
void build(int node,int l,int r)
{
    if(l==r)
    {
        tree[node].mx=abs(a[l]);//         ，           。
        tree[node].gd=abs(a[l]);//gcd        
        tree[node].sum=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    pushup(node);
}
void update(int node,int l,int r,int idx,int val)//    
{
    if(l==r)
    {
        tree[node].sum+=val;
        tree[node].mx=tree[node].gd=abs(tree[node].sum);
        return;
    }
    int mid=(l+r)>>1;
    if(idx<=mid)
      update(node<<1,l,mid,idx,val);
    else
      update(node<<1|1,mid+1,r,idx,val);
    pushup(node);
}
int query_sum(int node,int l,int r,int start,int end)//    ，    L==R   
{
    if(l>=start&&r<=end)
      return tree[node].sum;
    int mid=(l+r)>>1;
    int ans=0;
    if(start<=mid)
      ans+=query_sum(node<<1,l,mid,start,end);
    if(end>mid)
      ans+=query_sum(node<<1|1,mid+1,r,start,end);
    return ans;  
}
int query_max(int node,int l,int r,int start,int end)//     
{
    if(l>=start&&r<=end)
      return tree[node].mx;
    int mid=(l+r)>>1;
    int ans=-1;
    if(start<=mid)
      ans=max(query_max(node<<1,l,mid,start,end),ans);
    if(end>mid)
      ans=max(query_max(node<<1|1,mid+1,r,start,end),ans);
    return ans;
}
int query_gcd(int node,int l,int r,int start,int end)//  gcd
{
    if(l>=start&&r<=end)
      return tree[node].gd;
    int mid=(l+r)>>1;
    int ans=0;
    if(start<=mid)
      ans=gcd(query_gcd(node<<1,l,mid,start,end),ans);
    if(end>mid)
      ans=gcd(query_gcd(node<<1|1,mid+1,r,start,end),ans);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
      cin>>a[i];
    a[0]=0;
    for(int i=n;i>=1;i--)
      a[i]-=a[i-1];
    build(1,1,n);
    while(m--)
    {
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1)
        {
            int x;
            cin>>x;
            update(1,1,n,l,x);//l  +x    r+1  -x
            if(r<n)
              update(1,1,n,r+1,-x);
        }
        else if(op==2)
        {
            if(l==r)
              cout<<0<<endl;
            else
            {
                int ans=query_max(1,1,n,l+1,r);
                cout<<ans<<endl;
            }
        }
        else
        {
            int ans=abs(query_sum(1,1,n,1,l));
            if(l==r)
               cout<<ans<<endl;
            else
            {
                ans=gcd(ans,query_gcd(1,1,n,l+1,r));
                cout<<ans<<endl;
            }
        }
    }
    //system("pause");
    return 0;
}