【学习笔记】带区间乘的线段树([AHOI2009]维护序列 题解)

作者: wjyyy 分类: 学习笔记,线段树,解题报告 发布时间: 2018-09-22 17:03

点击量:36

 

    这个题是好久的坑了,一直不知道怎么填,后来发现把层次搞清楚了就OK了。先贴题面

 

题目描述

老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。

 

有长为\(N\)的数列,不妨设为\(a_1,a_2,\dots ,a_N\)。有如下三种操作形式:

(1)把数列中的一段数全部乘一个值;

(2)把数列中的一段数全部加一个值;

(3)询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模\(P\)的值。

 

输入输出格式

输入格式:

第一行两个整数\(N\)和\(P(1≤P≤1000000000)\)。

第二行含有\(N\)个非负整数,从左到右依次为\(a_1,a_2,\dots,a_N,(0≤a_i≤1000000000,1≤i≤N)\)。

第三行有一个整数\(M\),表示操作总数。

 

从第四行开始每行描述一个操作,输入的操作有以下三种形式:

操作1:“1 t g c”(不含双引号)。表示把所有满足\(t≤i≤g\)的\(a_i\)改为\(a_i\times c (1≤t≤g≤N,0≤c≤1000000000)\)。

操作2:“2 t g c”(不含双引号)。表示把所有满足\(t≤i≤g\)的\(a_i\)改为\(a_i+c (1≤t≤g≤N,0≤c≤1000000000)\)。

操作3:“3 t g”(不含双引号)。询问所有满足\(t≤i≤g\)的\(a_i\)的和模\(P\)的值\((1≤t≤g≤N)\)。 同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。

 

输出格式:

对每个操作3,按照它在输入中出现的顺序,依次输出一行一个整数表示询问结果。

输入输出样例

输入样例#1:

7 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7
输出样例#1:

2
35
8

说明

【样例说明】

初始时数列为(1,2,3,4,5,6,7)。

经过第1次操作后,数列为(1,10,15,20,25,6,7)。

对第2次操作,和为10+15+20=45,模43的结果是2。

经过第3次操作后,数列为(1,10,24,29,34,15,16}

对第4次操作,和为1+10+24=35,模43的结果是35。

对第5次操作,和为29+34+15+16=94,模43的结果是8。

 

测试数据规模如下表所示

数据编号 1 2 3 4 5 6 7 8 9 10
N 10 1000 1000 10000 60000 70000 80000 90000 100000 100000
M 10 1000 1000 10000 60000 70000 80000 90000 100000 100000

 

题解/做法:

    这题和普通的线段树不一样的地方在于,它需要支持区间乘操作。因为加法和乘法存在先后顺序的差异,所以懒标记不能直接维护两个。

 

    但是在线段树中,如果要对区间做乘法,那么就要知道它的确切值是多少,可以在每次加法和乘法冲突时都先下传一次。但是这样多次下传懒标记对常数会有很大的影响,我们可以试图换一种方式思考:如何不下传懒标记就完成区间乘呢?

 

    假设我们线段树中一个节点的信息为\(t[k].v,t[k].lazy\),它的实际权值是\(t[k].v+t[k].lazy\times (r-l+1)\)。如果要修改的区间覆盖满了\(t[k]\)的\(l\sim r\),就可以认为新权值是\((t[k].v+t[k].lazy\times (r-l+1))\times x\)。看来我们只需要把\(v\times x\),和\(lazytag\times x\)即可。

 

    不过这时我们可以对乘法和加法维护两个懒标记,只要保证它们是先执行乘法再执行加法就可以了。每次下传也要注意这一点。

 

Code:

#include<cstdio>
#include<cstring>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].l+t[k].r>>1)
struct node
{
    int l,r;
    long long ad,mu,v;
    node(int l,int r)
    {
        this->l=l;
        this->r=r;
        ad=0,mu=1;
        v=0;
    }
    node()
    {
        ad=0,mu=1;
        v=0;
    }
}t[400000];
long long a[100100],p;
void build(int k,int l,int r)
{
    t[k]=node(l,r);
    if(l==r)
    {
        t[k].v=a[l];
        return;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    t[k].v=(t[ls].v+t[rs].v)%p;
    return;
}
void pushdown(int k)
{
    if(t[k].l==t[k].r||(t[k].ad==0&&t[k].mu==1))
        return;
    long long x=t[k].ad;
    long long y=t[k].mu;
    t[k].ad=0;
    t[k].mu=1;
    t[ls].v=t[ls].v*y%p;
    t[ls].mu=t[ls].mu*y%p;
    t[ls].ad=t[ls].ad*y%p;
    t[ls].v=(t[ls].v+(t[ls].r-t[ls].l+1)*x)%p;
    t[ls].ad=(t[ls].ad+x)%p;

    t[rs].v=t[rs].v*y%p;
    t[rs].mu=t[rs].mu*y%p;
    t[rs].ad=t[rs].ad*y%p;
    t[rs].v=(t[rs].v+(t[rs].r-t[rs].l+1)*x)%p;
    t[rs].ad=(t[rs].ad+x)%p;
    return;
}
void mul(int k,int l,int r,int x)
{
    if(t[k].l==l&&t[k].r==r)
    {
        t[k].v=t[k].v*x%p;
        t[k].ad=t[k].ad*x%p;
        t[k].mu=t[k].mu*x%p;
        return;
    }
    pushdown(k);
    if(r<=Mid)
        mul(ls,l,r,x);
    else if(l>Mid)
        mul(rs,l,r,x);
    else
    {
        mul(ls,l,Mid,x);
        mul(rs,Mid+1,r,x);
    }
    t[k].v=(t[ls].v+t[rs].v)%p;
}
void add(int k,int l,int r,long long x)
{
    t[k].v=(t[k].v+x*(r-l+1))%p;
    if(t[k].l==l&&t[k].r==r)
    {
        t[k].ad=(t[k].ad+x)%p;
        return;
    }
    pushdown(k);
    if(r<=Mid)
        return add(ls,l,r,x);
    else if(l>Mid)
        return add(rs,l,r,x);
    add(ls,l,Mid,x);
    return add(rs,Mid+1,r,x);
}
long long ask(int k,int l,int r)
{
    if(t[k].l==l&&t[k].r==r)
        return t[k].v;
    pushdown(k);
    if(r<=Mid)
        return ask(ls,l,r);
    if(l>Mid)
        return ask(rs,l,r);
    else
        return (ask(ls,l,Mid)+ask(rs,Mid+1,r))%p;
}
int main()
{
    int n,m,op,x,y;
    long long z;
    scanf("%d%lld",&n,&p);
    for(int i=1;i<=n;++i)
        scanf("%lld",&a[i]);
    build(1,1,n);
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d",&op);
        if(op==2)
        {
            scanf("%d%d%lld",&x,&y,&z);
            add(1,x,y,z);
        }
        else if(op==1)
        {
            scanf("%d%d%lld",&x,&y,&z);
            mul(1,x,y,z);
        }
        else
        {
            scanf("%d%d",&x,&y);
            printf("%lld\n",ask(1,x,y));
        }
    }
    return 0;
}

2
说点什么

avatar
2 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 【区间乘线段树学习笔记】 […]

trackback

[…] 由于这道题在splay上完成,同时splay还有翻转操作,这时就需要存3个lazytag。此时要注意pushdown的操作顺序:区间翻转可以放在任何一个位置,但是乘标记和加标记必须先乘再加,打标记的原理可以看另一篇区间乘线段树的题解,重点在于乘的时候也要对加标记做乘法。 […]

/* */