codevs 2216 线段树两种更新方式的冲突

题目描述 Description

“神州“载人飞船的发射成功让小可可非常激动，他立志长大后要成为一名宇航员假期一始，他就报名参加了“小小宇航员夏令营”，在这里小可可不仅学到了丰富的宇航知识，还参与解决了一些模拟飞行中发现的问题，今天指导老师交给他一个任务，在这次模拟飞行的路线上有N个行星，暂且称它们为一个行星序列，并将他们从1至n标号，在宇宙未知力量的作用下这N个行星的质量是不断变化的，所以他们对飞船产生的引力也会不断变化，小可可的任务就是在飞行途中计算这个行星序列中某段行星的质量和，以便能及时修正飞船的飞行线路，最终到达目的地，行星序列质量变化有两种形式：

1，行星序列中某一段行星的质量全部乘以一个值

2，行星序列中某一段行星的质量全部加上一个值

由于行星的质量和很大，所以求出某段行星的质量和后只要输出这个值模P的结果即可，小可可被这个任务难住了，聪明的你能够帮他完成这个任务吗？

输入描述 Input Description

第一行两个整数N和P（1<=p<=1000000000）；

第二行含有N个非负整数，从左到右依次为a1，a2，…………，an（0<=ai<=100000000，1<=i<=n），其中ai表示第i个行星的质量：

第三行有一个整数m，表示模拟行星质量变化以及求质量和等操作的总次数。从第四行开始每行描述一个操作，输入的操作有以下三种形式：

操作1：1 t g c 表示把所有满足t<=i<=g的行星质量ai改为ai*c

操作2：2 t g c 表示把所有满足t<=i<=g的行星质量ai改为ai+c

操作3：3 t g 表示输出所有满足t<=i<=g的ai的和模p的值

其中：1<=t<=g<=N，0<=c<=10000000

注：同一行相邻的两数之间用一个空格隔开,每行开头和末尾没有多余空格

输出描述 Output Description

对每个操作3,按照它在输入中出现的顺序，依次一行输出一个整数表示所求行星质量和

样例输入 Sample Input

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

样例输出 Sample Output

2
35
8

数据范围及提示 Data Size & Hint

100%的数据中，M，N<=100000

40%的数据中，M，N<=10000

题意：中文题面，对一段序列的三种操作,重点是更新操作有两种

某个区间的数都增加c或者都乘以c

题解：此题注意开long long

如果是单个更新操作的话，就是很容易的区间延迟标记，但是如果是两种不同的操作呢,这样是会有冲突的,

也就是对于一个下放区间的标记是先处理乘法呢?还是先处理加法呢?

参考了别人的代码之后,我是这样理解的，乘法的标记只对某个区间的sum值起作用,并且对于乘法标记的下放,

不仅要更新下放区间的plu,还要将plu转换为add

也可以这样考虑,就某一个数无非两种标记的执行顺序不同导致结果不同

先加后乘(add+sum)*plu=sum*plu+add*plu;

先乘后加sum*plu+add=sum*plu+add*1;

观察一下如何使得两种情况一起处理呢?就是把add*plu转化为新的add

具体看代码;

  1 /******************************
  2 code by drizzle
  3 blog: www.cnblogs.com/hsd-/
  4 ^ ^    ^ ^
  5  O      O
  6 ******************************/
  7 //#include<bits/stdc++.h>
  8 #include<iostream>
  9 #include<cstring>
 10 #include<cstdio>
 11 #include<map>
 12 #include<algorithm>
 13 #include<cmath>
 14 #define ll long long
 15 #define PI acos(-1.0)
 16 #define mod 1000000007
 17 using namespace std;
 18 struct node
 19 {
 20     int l,r;
 21     ll sum;
 22     ll add;
 23     ll plu;
 24 } tree[400005];
 25 int n;
 26 ll p;
 27 int q;
 28 int exm;
 29 int l1,r1;
 30 ll cc;
 31 void build(int root,int left,int right)
 32 {
 33     tree[root].l=left;
 34     tree[root].r=right;
 35     tree[root].add=0;
 36     tree[root].plu=1;
 37     if(left==right)
 38     {
 39         tree[root].sum=0;
 40         scanf("%lld",&tree[root].sum);
 41         tree[root].sum%=p;
 42         return ;
 43     }
 44     int mid=(left+right)>>1;
 45     build(root<<1,left,mid);
 46     build(root<<1|1,mid+1,right);
 47     tree[root].sum=(tree[root<<1].sum+tree[root<<1|1].sum)%p;
 48 }
 49 void pushdown(int root)
 50 {
 51     if(tree[root].l==tree[root].r) return ;
 52     ll pl=tree[root].plu;//针对区间sum起作用
 53     ll ad=tree[root].add;
 54     tree[root<<1].sum=(tree[root<<1].sum*pl%p+(tree[root<<1].r-tree[root<<1].l+1)*ad%p)%p;
 55     tree[root<<1|1].sum=(tree[root<<1|1].sum*pl%p+(tree[root<<1|1].r-tree[root<<1|1].l+1)*ad%p)%p;
 56     tree[root<<1].add=(tree[root<<1].add*pl+ad)%p;//对于这个区间的每个元素将plu转化为了add
 57     tree[root<<1|1].add=(tree[root<<1|1].add*pl+ad)%p;
 58     tree[root<<1].plu=(tree[root<<1].plu*pl)%p;
 59     tree[root<<1|1].plu=(tree[root<<1|1].plu*pl)%p;
 60     tree[root].add=0;
 61     tree[root].plu=1;
 62 }
 63 void updata(int root,int left,int right,ll c,int flag)
 64 {
 65     pushdown(root);
 66     if(tree[root].l==left&&tree[root].r==right)
 67     {
 68         if(flag==1)
 69         {
 70             tree[root].plu=(tree[root].plu*c)%p;
 71             tree[root].sum=tree[root].sum*c%p;
 72             return ;
 73         }
 74         if(flag==2)
 75         {
 76             tree[root].add=(tree[root].add+c)%p;
 77             tree[root].sum=(tree[root].sum+c*(right-left+1))%p;
 78             return ;
 79         }
 80     }
 81     int mid=(tree[root].l+tree[root].r)>>1;
 82     if(right<=mid)
 83         updata(root<<1,left,right,c,flag);
 84     else
 85     {
 86         if(left>mid)
 87             updata(root<<1|1,left,right,c,flag);
 88         else
 89         {
 90             updata(root<<1,left,mid,c,flag);
 91             updata(root<<1|1,mid+1,right,c,flag);
 92         }
 93     }
 94     tree[root].sum=(tree[root<<1].sum+tree[root<<1|1].sum)%p;
 95 }
 96 ll query(int root,int left,int right)
 97 {
 98     pushdown(root);
 99     if(tree[root].l==left&&tree[root].r==right)
100     {
101         return tree[root].sum;
102     }
103     int mid=(tree[root].l+tree[root].r)>>1;
104     if(right<=mid)
105         return query(root<<1,left,right);
106     else
107     {
108         if(left>mid)
109             return query(root<<1|1,left,right);
110         else
111             return query(root<<1,left,mid)+query(root<<1|1,mid+1,right);
112     }
113 }
114 int main()
115 {
116     while(~scanf("%d %lld",&n,&p))
117     {
118         build(1,1,n);
119         scanf("%d",&q);
120         for(int i=1; i<=q; i++)
121         {
122             scanf("%d",&exm);
123             if(exm==1)
124             {
125                 scanf("%d %d %lld",&l1,&r1,&cc);
126                 updata(1,l1,r1,cc,1);
127             }
128             if(exm==2)
129             {
130                 scanf("%d %d %lld",&l1,&r1,&cc);
131                 updata(1,l1,r1,cc,2);
132             }
133             if(exm==3)
134             {
135                 scanf("%d %d",&l1,&r1);
136                 printf("%lld
",query(1,l1,r1)%p);
137             }
138         }
139     }
140     return 0;
141 }

codevs 2216 线段树 两种更新方式的冲突

codevs 2216 线段树两种更新方式的冲突