P1001的线段树解法

· · 个人记录

那么难的题目怎么可以少得了线段树呢（我的挚爱

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mul[400005],ans[400005],add[400005],a[100005],mod,n,m,opt,l,r,x;
void build(ll p,ll l,ll r)
{
    mul[p]=1;
    if(l==r)
    {
        ans[p]=a[l]%mod;
        return;
    }
    ll mid=(l+r)/2;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    ans[p]=ans[p<<1]+ans[p<<1|1];
}
void push_down(ll p,ll l,ll r)
{
    ll mid=(l+r)/2;
    ans[p<<1]=(ans[p<<1]*mul[p]+add[p]*(mid-l+1))%mod;
    ans[p<<1|1]=(ans[p<<1|1]*mul[p]+add[p]*(r-mid))%mod;
    mul[p<<1]=(mul[p<<1]*mul[p])%mod;
    mul[p<<1|1]=(mul[p<<1|1]*mul[p])%mod;
    add[p<<1]=(add[p<<1]*mul[p]+add[p])%mod;
    add[p<<1|1]=(add[p<<1|1]*mul[p]+add[p])%mod;
    add[p]=0,mul[p]=1;
}
void update1(ll p,ll l,ll r,ll ql,ll qr,ll k)
{
    if(ql<=l&&r<=qr)
    {
        ans[p]=(ans[p]*k)%mod;
        mul[p]=(mul[p]*k)%mod;
        add[p]=(add[p]*k)%mod;
        return;
    }
    push_down(p,l,r);
    ll mid=(l+r)/2;
    if(ql<=mid)
      update1(p<<1,l,mid,ql,qr,k);
    if(qr>mid)
      update1(p<<1|1,mid+1,r,ql,qr,k);
    ans[p]=ans[p<<1]+ans[p<<1|1];
}
void update2(ll p,ll l,ll r,ll ql,ll qr,ll k)
{
    if(ql<=l&&r<=qr)
    {
        ans[p]=(ans[p]+k*(r-l+1))%mod;
        add[p]=(add[p]+k)%mod;
        return;
    }
    push_down(p,l,r);
    ll mid=(l+r)/2;
    if(ql<=mid)
      update2(p<<1,l,mid,ql,qr,k);
    if(qr>mid)
      update2(p<<1|1,mid+1,r,ql,qr,k);
    ans[p]=ans[p<<1]+ans[p<<1|1];
}
ll query(ll p,ll l,ll r,ll ql,ll qr)
{
    if(ql<=l&&r<=qr)
      return ans[p];
    push_down(p,l,r); 
    ll mid=(l+r)/2;
    ll ans=0; 
    if(ql<=mid)
      ans+=query(p<<1,l,mid,ql,qr);
    if(qr>mid)
      ans+=query(p<<1|1,mid+1,r,ql,qr);
    return ans%mod;
}
int main()
{
    ios::sync_with_stdio(0);
    mod=1e18;
    n=2;
    for(int i=1;i<n;++i)
      cin>>a[i];
    build(1,1,n);
    int x;
    cin>>x;
    update2(1,1,n,2,2,x);
    update1(1,1,n,1,2,1);
    cout<<query(1,1,n,1,n);
    return 0;
}

提交记录链接

PS:加上乘法，使用区间修改以示我对lazy_tag的尊重