Luogu P2590 [ZJOI2008]树的统计

P2590 [ZJOI2008]树的统计

三种操作：

I. CHANGE u t : 把结点u的权值改为t

II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值

III. QSUM u v: 询问从点u到点v的路径上的节点的权值和

简单树剖w（天天刷水的\(1e3+7\)）

其实就是树剖板子多配一个线段树维护区间最值

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#define ll long long
#define MAXN 200002<<1
#define leftson cur<<1
#define rightson (cur<<1|1)
#define mid ((l+r)>>1)
#define push_up ans[cur]=(ans[leftson]+ans[rightson])%mod 
//#define push_down downmul(cur); downadd(cur,l,r)
#define push_down pushdown(cur);
using namespace std;
ll ans[MAXN],add[MAXN]={},mul[MAXN],lefts[MAXN],rights[MAXN];
ll n,m,mod;
ll a,b,c;
void build(ll cur,ll l,ll r)
{
    mul[cur]=1;
    add[cur]=0;
    lefts[cur]=l;
    rights[cur]=r;
    if (l==r)
    {
        scanf("%lld",&ans[cur]);
        ans[cur]%=mod;
        return;
    }
    build(leftson,l,mid);
    build(rightson,mid+1,r);
    push_up;
}
inline void downmul(ll cur)
{
    if (mul[cur]!=1)
    {
        ans[leftson]=(ans[leftson]*mul[cur])%mod;
        ans[rightson]=(ans[rightson]*mul[cur])%mod;
        mul[leftson]=(mul[leftson]*mul[cur])%mod;
        mul[rightson]=(mul[rightson]*mul[cur])%mod;
        add[leftson]=(add[leftson]*mul[cur])%mod;
        add[rightson]=(add[rightson]*mul[cur])%mod;
        mul[cur]=1;
    }
}
inline void downadd(ll cur,ll l,ll r)
{
    ll ln=(mid-l+1),rn=(r-mid);
    if (add[cur]!=0)
    {
        ans[leftson]=(ans[leftson]+add[cur]*ln)%mod;
        ans[rightson]=(ans[rightson]+add[cur]*rn)%mod;
        add[cur]=0;
    }
}
inline void pushdown(ll cur)
{
    ans[leftson]=(ans[leftson]*mul[cur]+add[cur]*(rights[leftson]-lefts[leftson]+1))%mod;
    ans[rightson]=(ans[rightson]*mul[cur]+add[cur]*(rights[rightson]-lefts[rightson]+1))%mod;
    mul[leftson]=(mul[leftson]*mul[cur])%mod;
    mul[rightson]=(mul[rightson]*mul[cur])%mod;
    add[leftson]=(add[leftson]*mul[cur]+add[cur])%mod;
    add[rightson]=(add[rightson]*mul[cur]+add[cur])%mod;
    mul[cur]=1;
    add[cur]=0;
}
inline void mulchange(ll mu,ll mur,ll cur,ll l,ll r,ll delta)
{
    if (mu<=l&&r<=mur)
    {
        ans[cur]=ans[cur]*delta%mod;
        mul[cur]=mul[cur]*delta%mod;
        add[cur]=add[cur]*delta%mod;
        return;
    }
    push_down;
    if (mu<=mid) mulchange(mu,mur,leftson,l,mid,delta);
    if (mur>mid) mulchange(mu,mur,rightson,mid+1,r,delta);
    push_up;
}
inline void addchange(ll adl,ll adr,ll cur,ll l,ll r,ll delta)
{
    if (adl<=l&&r<=adr)
    {
        ans[cur]+=delta*(r-l+1)%mod;
        add[cur]+=delta%mod;
        return;
    }
    push_down;
    if (adl<=mid) addchange(adl,adr,leftson,l,mid,delta);
    if (adr>mid) addchange(adl,adr,rightson,mid+1,r,delta);
    push_up;
}
ll query(ll quel,ll quer,ll cur,ll l,ll r)
{
    if (quel<=l&&r<=quer)
    {
        return ans[cur]%mod;
    }
    push_down;
    ll answer=0;
    if (quel<=mid) answer+=query(quel,quer,leftson,l,mid)%mod;
    if (quer>mid) answer+=query(quel,quer,rightson,mid+1,r)%mod;
    return answer;
}
int main()
{
    scanf("%lld%lld",&n,&mod);
    build(1,1,n);
    ll cs;
    scanf("%lld",&m);
    for (ll i=1;i<=m;i++)
    {
        scanf("%lld",&cs);
        if (cs==1)
        {
            scanf("%lld%lld%lld",&a,&b,&c);
            mulchange(a,b,1,1,n,c);
            continue;           
        }
        if (cs==2)
        {
            scanf("%lld%lld%lld",&a,&b,&c);
            addchange(a,b,1,1,n,c);
            continue;
        }
        scanf("%lld%lld",&a,&b);
        printf("%lld\n",query(a,b,1,1,n)%mod);
    }
    return 0;
}

自我吐槽：写完整\(leftson\)和\(rightson\)（似乎别人一般写ls/rs/lson/rson）的线段树，以及大片宏定义，加上毒瘤递归\(inline\)，这\(segment-tree\)码风可能永远改不掉了（写的很舒服）

Luogu P2590 [ZJOI2008]树的统计

原文：https://www.cnblogs.com/Kan-kiz/p/10946305.html