文档章节

P3373 【模板】线段树 2

o
 osc_4nmshwhm
发布于 2018/08/07 13:41
字数 1997
阅读 7
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题目描述

如题,已知一个数列,你需要进行下面三种操作:

1.将某区间每一个数乘上x

2.将某区间每一个数加上x

3.求出某区间每一个数的和

输入输出格式

输入格式:

 

第一行包含三个整数N、M、P,分别表示该数列数字的个数、操作的总个数和模数。

第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数,表示一个操作,具体如下:

操作1: 格式:1 x y k 含义:将区间[x,y]内每个数乘上k

操作2: 格式:2 x y k 含义:将区间[x,y]内每个数加上k

操作3: 格式:3 x y 含义:输出区间[x,y]内每个数的和对P取模所得的结果

 

输出格式:

 

输出包含若干行整数,即为所有操作3的结果。

 

输入输出样例

输入样例#1:  复制
5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4
输出样例#1:  复制
17
2

说明

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=8,M<=10

对于70%的数据:N<=1000,M<=10000

对于100%的数据:N<=100000,M<=100000

(数据已经过加强^_^)

样例说明:

故输出应为17、2(40 mod 38=2)

题解:

这个题真是毒瘤,疯狂卡你的时间,int,取余运算不可太多,否者时间回很多,甚至会超时,如果一开始你有30分,请看是否使用 long long,还有就是取模运算是否足够,还有就是乘法的lazyc标记在不等于-1是进行运算可能有负数。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL MAXN=1e6+10;
LL a[MAXN],mod;
struct node{
    LL l,r;
    long long sum;
    long long lazy;
    long long lazyc;
}Tree[MAXN<<2];
inline LL ls(LL p){ return p<<1;}//左儿子
inline LL rs(LL p){ return p<<1|1;}
void PushUP(LL p)//向上更新
{
    Tree[p].sum=(Tree[ls(p)].sum+Tree[rs(p)].sum)%mod;
    Tree[p].sum%=mod;
}
void build(LL p,LL l,LL r)
{
    Tree[p].lazy=0;
    Tree[p].lazyc=1;
    Tree[p].l=l;Tree[p].r=r;
    if(l==r) {Tree[p].sum=a[l];return;}
    LL mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    PushUP(p);
}
void PushDown(LL p,LL l,LL r)//lazy节点下移
{
    if(Tree[p].lazy)
    {
        LL len=(r-l+1);
        Tree[ls(p)].lazy=(Tree[ls(p)].lazy%mod+Tree[p].lazy%mod)%mod;
        Tree[rs(p)].lazy=(Tree[rs(p)].lazy%mod+Tree[p].lazy%mod)%mod;

        Tree[ls(p)].sum=(Tree[ls(p)].sum%mod+Tree[p].lazy%mod*(len-(len>>1)))%mod;

        Tree[rs(p)].sum=(Tree[rs(p)].sum%mod+Tree[p].lazy%mod*(len>>1))%mod;

        Tree[p].lazy=0;//下移后,原节点取消标记
    }
}
void PushDownc(LL p,LL l,LL r)
{
    if(Tree[p].lazyc!=1)//数据中有可能有负数,
    {
        Tree[ls(p)].lazyc=(Tree[ls(p)].lazyc%mod*Tree[p].lazyc%mod)%mod;
        Tree[rs(p)].lazyc=(Tree[rs(p)].lazyc%mod*Tree[p].lazyc%mod)%mod;
        Tree[ls(p)].lazy=(Tree[ls(p)].lazy%mod*Tree[p].lazyc%mod)%mod;
        Tree[rs(p)].lazy=(Tree[rs(p)].lazy%mod*Tree[p].lazyc%mod)%mod;
        Tree[ls(p)].sum=(Tree[ls(p)].sum%mod*Tree[p].lazyc%mod)%mod;
        Tree[rs(p)].sum=(Tree[rs(p)].sum%mod*Tree[p].lazyc%mod)%mod;
        Tree[p].lazyc=1;
    }
    PushDown(p,l,r);
}
void UpDate(LL L,LL R,LL c,LL l,LL r,LL p)//更新操作
{
    if(l>=L&&r<=R)//这个区间完全在更新区间的内部
    {
        Tree[p].lazy=(Tree[p].lazy%mod+c)%mod;
        Tree[p].sum=(Tree[p].sum%mod+c*(r-l+1))%mod;
        return;
    }
    PushDownc(p,l,r);//加法的更新操作也应当使得乘法的lazyc标记向下移动
    LL mid=(l+r)>>1;
    if(mid>=L) UpDate(L,R,c,l,mid,ls(p));
    if(mid<R) UpDate(L,R,c,mid+1,r,rs(p));
    PushUP(p);
}
void Updatec(LL L,LL R,LL c,LL l,LL r,LL p)
{
    if(l>=L&&r<=R)//这个区间完全在更新区间的内部
    {
        Tree[p].lazyc=(Tree[p].lazyc%mod*c)%mod;
        Tree[p].lazy=(Tree[p].lazy%mod*c)%mod;
        Tree[p].sum=(Tree[p].sum%mod*c)%mod;

        return;
    }
    PushDownc(p,l,r);
    LL mid=(l+r)>>1;
    if(mid>=L) Updatec(L,R,c,l,mid,ls(p));
    if(mid<R) Updatec(L,R,c,mid+1,r,rs(p));
    PushUP(p);
}
LL query(LL L,LL R,LL l,LL r,LL p)
{
    LL res=0;
    if(l>=L&&r<=R) return Tree[p].sum%mod;
    LL mid=(l+r)>>1;

    PushDownc(p,l,r);

    if(mid>=L) res+=(query(L,R,l,mid,ls(p))%mod);
    if(mid<R) res+=(query(L,R,mid+1,r,rs(p))%mod);
    return res%mod;
}
int main()
{
    LL n,m;
    scanf("%lld%lld%lld",&n,&m,&mod);
    for (LL i = 1; i <=n ; ++i) {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    while (m--)
    {
        LL flag;
        scanf("%lld",&flag);
        if(flag==1)
        {
            LL x,y,z;
            scanf("%lld%lld%lld",&x,&y,&z);
            Updatec(x,y,z%mod,1,n,1);
        }
        else if(flag==2)
        {
            LL x,y,z;
            scanf("%lld%lld%lld",&x,&y,&z);
            UpDate(x,y,z,1,n,1);
        }
        else if(flag==3)
        {
            LL x,y;
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",query(x,y,1,n,1)%mod);
        }
    }
    return 0;
}

  

P2023 [AHOI2009]维护序列

题解:

其实是一样的题,但是直接上面那个代码有两个点过不去,因此加了一个输入挂,然后就没什么问题了。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL MAXN=1e6+10;
LL a[MAXN],mod;
struct node{
    LL l,r;
    long long sum;
    long long lazy;
    long long lazyc;
}Tree[MAXN<<2];
inline LL ls(LL p){ return p<<1;}//左儿子
inline LL rs(LL p){ return p<<1|1;}
void PushUP(LL p)//向上更新
{
    Tree[p].sum=(Tree[ls(p)].sum+Tree[rs(p)].sum)%mod;
    Tree[p].sum%=mod;
}
void build(LL p,LL l,LL r)
{
    Tree[p].lazy=0;
    Tree[p].lazyc=1;
    Tree[p].l=l;Tree[p].r=r;
    if(l==r) {Tree[p].sum=a[l];return;}
    LL mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    PushUP(p);
}
void PushDown(LL p,LL l,LL r)//lazy节点下移
{
    if(Tree[p].lazy)
    {
        LL len=(r-l+1);
        Tree[ls(p)].lazy=(Tree[ls(p)].lazy%mod+Tree[p].lazy%mod)%mod;
        Tree[rs(p)].lazy=(Tree[rs(p)].lazy%mod+Tree[p].lazy%mod)%mod;

        Tree[ls(p)].sum=(Tree[ls(p)].sum%mod+Tree[p].lazy%mod*(len-(len>>1)))%mod;

        Tree[rs(p)].sum=(Tree[rs(p)].sum%mod+Tree[p].lazy%mod*(len>>1))%mod;

        Tree[p].lazy=0;//下移后,原节点取消标记
    }
}
void PushDownc(LL p,LL l,LL r)
{
    if(Tree[p].lazyc!=1)//数据中有可能有负数,
    {
        Tree[ls(p)].lazyc=(Tree[ls(p)].lazyc%mod*Tree[p].lazyc%mod)%mod;
        Tree[rs(p)].lazyc=(Tree[rs(p)].lazyc%mod*Tree[p].lazyc%mod)%mod;
        Tree[ls(p)].lazy=(Tree[ls(p)].lazy%mod*Tree[p].lazyc%mod)%mod;
        Tree[rs(p)].lazy=(Tree[rs(p)].lazy%mod*Tree[p].lazyc%mod)%mod;
        Tree[ls(p)].sum=(Tree[ls(p)].sum%mod*Tree[p].lazyc%mod)%mod;
        Tree[rs(p)].sum=(Tree[rs(p)].sum%mod*Tree[p].lazyc%mod)%mod;
        Tree[p].lazyc=1;
    }
    PushDown(p,l,r);
}
void UpDate(LL L,LL R,LL c,LL l,LL r,LL p)//更新操作
{
    if(l>=L&&r<=R)//这个区间完全在更新区间的内部
    {
        Tree[p].lazy=(Tree[p].lazy%mod+c)%mod;
        Tree[p].sum=(Tree[p].sum%mod+c*(r-l+1))%mod;
        return;
    }
    PushDownc(p,l,r);//加法的更新操作也应当使得乘法的lazyc标记向下移动
    LL mid=(l+r)>>1;
    if(mid>=L) UpDate(L,R,c,l,mid,ls(p));
    if(mid<R) UpDate(L,R,c,mid+1,r,rs(p));
    PushUP(p);
}
void Updatec(LL L,LL R,LL c,LL l,LL r,LL p)
{
    if(l>=L&&r<=R)//这个区间完全在更新区间的内部
    {
        Tree[p].lazyc=(Tree[p].lazyc%mod*c)%mod;
        Tree[p].lazy=(Tree[p].lazy%mod*c)%mod;
        Tree[p].sum=(Tree[p].sum%mod*c)%mod;

        return;
    }
    PushDownc(p,l,r);
    LL mid=(l+r)>>1;
    if(mid>=L) Updatec(L,R,c,l,mid,ls(p));
    if(mid<R) Updatec(L,R,c,mid+1,r,rs(p));
    PushUP(p);
}
LL query(LL L,LL R,LL l,LL r,LL p)
{
    LL res=0;
    if(l>=L&&r<=R) return Tree[p].sum%mod;
    LL mid=(l+r)>>1;

    PushDownc(p,l,r);

    if(mid>=L) res+=(query(L,R,l,mid,ls(p))%mod);
    if(mid<R) res+=(query(L,R,mid+1,r,rs(p))%mod);
    return res%mod;
}
long long read()
{
    char ch=' ';
    LL ans=0;
    while(ch<'0' || ch>'9')
        ch=getchar();
    while(ch<='9' && ch>='0')
    {
        ans=ans*10+ch-'0';
        ch=getchar();
    }
    return ans;
}
int main()
{
    LL n,m;
    scanf("%lld%lld",&n,&mod);
    for (LL i = 1; i <=n ; ++i) {
//        scanf("%lld",&a[i]);
        a[i]=read();
    }
    build(1,1,n);
    scanf("%lld",&m);
    while (m--)
    {
        LL flag;
        scanf("%lld",&flag);
        if(flag==1)
        {
            LL x,y,z;
            //scanf("%lld%lld%lld",&x,&y,&z);
            x=read();y=read();z=read();
            Updatec(x,y,z%mod,1,n,1);
        }
        else if(flag==2)
        {
            LL x,y,z;
            //scanf("%lld%lld%lld",&x,&y,&z);
            x=read();y=read();z=read();
            UpDate(x,y,z,1,n,1);
        }
        else if(flag==3)
        {
            LL x,y;
            //scanf("%lld%lld",&x,&y);
            x=read();y=read();
            printf("%lld\n",query(x,y,1,n,1)%mod);
        }
    }
    return 0;
}

  

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

自从尝了 Rust,Java 突然不香了

Rust 是软件行业中相对而言比较新的一门编程语言,如果从语法上来比较,该语言与 C++ 其实非常类似,但从另一方面而言,Rust 能更高效地提供许多功能来保证性能和安全。而且,Rust 还能在无需...

osc_k3vwonkw
30分钟前
10
0
Java 高级 面试题 及 参考答案

一、面试题基础总结 1、 JVM结构原理、GC工作机制详解 答:具体参照:JVM结构、GC工作机制详解 ,说到GC,记住两点:1、GC是负责回收所有无任何引用对象的内存空间。 注意:垃圾回收回收的是无...

FH-Admin
31分钟前
26
0
机器学习中的AUC-ROC曲线

作者|ANIRUDDHA BHANDARI 编译|VK 来源|Analytics Vidhya AUC-ROC曲线 你已经建立了你的机器学习模型-那么接下来呢?你需要对它进行评估,并验证它有多好(或有多坏),这样你就可以决定是否...

osc_bg8v9gvf
32分钟前
8
0
音视频(消息)应用场景 :连麦交友例子

实现一个小例子: 效果类似唱吧APP里的 连麦交友功能,音视频,IM 及音视频 SDK参考融云服务商。 没有印象的可以搜索 ’连麦’ 关键字在 应用商店下载一款 连麦的软件 体验下 业务方面的需求...

T型人才追梦者
33分钟前
11
0
逛淘宝天猫想到SSO单点登录

我的原文地址:https://mp.weixin.qq.com/s/77xukPDlgkKnYpwu4LrqaA

osc_yy65eb2q
33分钟前
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部