Loading...

线段树模板 洛谷P3373

check评论:0 条 remove_red_eye浏览量:430 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-05-06

O(log(n))

线段树的模板题 我就主要说一下懒标记的顺序吧

懒标记(Lazy Tag)主要的作用是保存一个点的所有更新信息,可以在 O(log(n))内实现区间修改

我们将懒标记分为 mul[i] 和 addv[i] ,其中 mul[i] 表示一个点修改得乘法标记, addv[i] 就是加法标记

通过模板1,大家应该知道修改的其中一个操作 pushdown ,用于下放当前点的标记至其子结点,而这道题面临一个新的问题, pushdown 是该先进行乘法标记的运算还是加法标记呐

如果先运算加法标记,例如

int pushdown(int o,int lf,int rg)
{
    if(addv[o])
    {
        int mid=(lf+rg)>>1;
        sum[o]=(sum[o]+(mid-lf+1)*addv[o])%p;
        //Do something else
    }
}

则当进行一次乘法标记,再次进行加法标记时,代码则变成了

int pushdown(int o,int lf,int rg)
{
    if(addv[o])
    {
        int mid=(lf+rg)>>1;
        sum[o]=(sum[o]+(mid-lf+1)*addv[o]+mul[o]/(rg-lf+1))%p;
        //Do something else
    }
}

由于不一定能整除,则精度出现了误差,所以正确的方法是先乘后加

#define ll long long
void pushdown(ll int o,ll int lf,ll int rg)
{
    if(mul[o]!=1)
    {
        mul[o<<1]=mul[o<<1]*mul[o]%p;
        mul[o<<1|1]=mul[o<<1|1]*mul[o]%p;
        sum[o<<1]=sum[o<<1]*mul[o]%p;
        sum[o<<1|1]=sum[o<<1|1]*mul[o]%p;
        addv[o<<1]=addv[o<<1]*mul[o]%p;
        addv[o<<1|1]=addv[o<<1|1]*mul[o]%p;
        mul[o]=1;
    }
    if(addv[o])
    {
        addv[o<<1]=(addv[o<<1]+addv[o])%p;
        addv[o<<1|1]=(addv[o<<1|1]+addv[o])%p;
        ll int mid=(lf+rg)>>1;
        sum[o<<1]=(sum[o<<1]+(mid-lf+1)*addv[o])%p;
        sum[o<<1|1]=(sum[o<<1|1]+(rg-mid)*addv[o])%p;
        addv[o]=0;
    }
}

这样子就不会出现误差了

最后贴上高清无码的代码

#include <iostream>
#include <stdio.h>
using namespace std;
#define pushup(o) sum[o]=sum[o<<1]+sum[o<<1|1]
#define ll long long 
ll int sum[400004],a[400004],addv[400004],mul[400004],n,m,p;
void build(ll int o,ll int lf,ll int rg)
{
    addv[o]=0;
    mul[o]=1;
    if(lf==rg)
    {
        sum[o]=a[lf];
        return ;
    }
    ll int mid=(lf+rg)>>1;
    build(o<<1,lf,mid);
    build(o<<1|1,mid+1,rg);
    pushup(o);
}
void pushdown(ll int o,ll int lf,ll int rg)
{
    if(mul[o]!=1)
    {
        mul[o<<1]=mul[o<<1]*mul[o]%p;
        mul[o<<1|1]=mul[o<<1|1]*mul[o]%p;
        sum[o<<1]=sum[o<<1]*mul[o]%p;
        sum[o<<1|1]=sum[o<<1|1]*mul[o]%p;
        addv[o<<1]=addv[o<<1]*mul[o]%p;
        addv[o<<1|1]=addv[o<<1|1]*mul[o]%p;
        mul[o]=1;
    }
    if(addv[o])
    {
        addv[o<<1]=(addv[o<<1]+addv[o])%p;
        addv[o<<1|1]=(addv[o<<1|1]+addv[o])%p;
        ll int mid=(lf+rg)>>1;
        sum[o<<1]=(sum[o<<1]+(mid-lf+1)*addv[o])%p;
        sum[o<<1|1]=(sum[o<<1|1]+(rg-mid)*addv[o])%p;
        addv[o]=0;
    }
}
void up_add(ll int o,ll int lf,ll int rg,ll int l,ll int r,ll int x)
{
    if(l<=lf&&rg<=r)
    {
        addv[o]=(addv[o]+x)%p;
        sum[o]=(sum[o]+x*(rg-lf+1))%p;
        return ;
    }
    ll int mid=(lf+rg)>>1;
    pushdown(o,lf,rg);
    if(l<=mid)
    {
        up_add(o<<1,lf,mid,l,r,x);
    }
    if(mid<r)
    {
        up_add(o<<1|1,mid+1,rg,l,r,x);
    }
    pushup(o);
}
void up_mul(ll int o,ll int lf,ll int rg,ll int l,ll int r,ll int x)
{
    if(l<=lf&&rg<=r)
    {
        mul[o]=mul[o]*x%p;
        addv[o]=addv[o]*x%p;
        sum[o]=sum[o]*x%p;
        return ;
    }
    ll int mid=(lf+rg)>>1;
    pushdown(o,lf,rg);
    if(l<=mid)
    {
        up_mul(o<<1,lf,mid,l,r,x);
    }
    if(mid<r)
    {
        up_mul(o<<1|1,mid+1,rg,l,r,x);
    }
    pushup(o);
}
ll int query(ll int o,ll int lf,ll int rg,ll int l,ll int r)
{
    if(l<=lf&&rg<=r)
    {
        return sum[o];
    }
    pushdown(o,lf,rg);
    ll int mid=(lf+rg)>>1;
    ll int ans=0;
    if(l<=mid)
    {
        ans=(ans+query(o<<1,lf,mid,l,r))%p;
    }
    if(mid<r)
    {
        ans=(ans+query(o<<1|1,mid+1,rg,l,r))%p;
    }
    return ans%p;
}
int main()
{
    cin>>n>>m>>p;
    for(ll int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    for(ll int i=1;i<=m;i++)
    {
        ll int t;
        scanf("%d",&t);
        ll int x,y,z;
        switch(t)
        {
            case 1:scanf("%lld%lld%lld",&x,&y,&z);up_mul(1,1,n,x,y,z);break;
            case 2:scanf("%lld%lld%lld",&x,&y,&z);up_add(1,1,n,x,y,z);break;
            case 3:scanf("%lld%lld",&x,&y);printf("%lld\n",query(1,1,n,x,y));break;
        }
    }
}

你好 世界 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名