4927 线段树练习5

时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 黄金 Gold

题解

 查看运行结果

题目描述 Description

有n个数和5种操作

add a b c:把区间[a,b]内的所有数都增加c

set a b c:把区间[a,b]内的所有数都设为c

sum a b:查询区间[a,b]的区间和

max a b:查询区间[a,b]的最大值

min a b:查询区间[a,b]的最小值

输入描述 Input Description

第一行两个整数n,m,第二行n个整数表示这n个数的初始值

接下来m行操作,同题目描述

输出描述 Output Description

对于所有的sum、max、min询问,一行输出一个答案

样例输入 Sample Input

10 6

3 9 2 8 1 7 5 0 4 6

add 4 9 4

set 2 6 2

add 3 8 2

sum 2 10

max 1 7

min 3 6

样例输出 Sample Output

49

11

4

数据范围及提示 Data Size & Hint

10%:1<n,m<=10

30%:1<n,m<=10000

100%:1<n,m<=100000

保证中间结果在long long(C/C++)、int64(pascal)范围内

PS:由于数据6出错导致某些人只有90分,已于2016.5.13修正。

出题人在此对两位90分的用户表示诚挚的歉意

好恶心的一道题

这道题特殊在set操作

对于这个操作,我们需要增加两个变量来维护,一个维护这个区间是否被修改,一个维护被修改成了多少

特别注意不能只维护被修改成了多少(会有0的情况)

在下传标记的时候,需要先下传set标记,再下传add标记

因为我们在设置set标记的时候已经把add标记置为0

如果此时add标记不为0,就说明这个标记一定是在set标记设置之后设置的

再注意一下细节就可以了

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #define LL long long 
  6 #define ls k<<1
  7 #define rs k<<1|1
  8 using namespace std;
  9 const LL MAXN=400400;
 10 const LL INF =0x7fffff;
 11 inline void read(LL &n)
 12 {
 13     char c=getchar();n=0;bool flag=0;
 14     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
 15     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
 16 }
 17 struct node
 18 {
 19     LL l,r,w,Max,Min,Set,Add;
 20     bool V;
 21 }tree[MAXN];
 22 LL n,m;
 23 LL ans=0;
 24 inline void update(LL k)
 25 {
 26     tree[k].w=tree[ls].w+tree[rs].w;
 27     tree[k].Max=max(tree[ls].Max,tree[rs].Max);
 28     tree[k].Min=min(tree[ls].Min,tree[rs].Min);
 29 }
 30 void Build_Tree(LL ll,LL rr,LL k)
 31 {
 32     tree[k].l=ll;tree[k].r=rr;
 33     if(tree[k].l==tree[k].r)
 34     {
 35         read(tree[k].w);
 36         tree[k].Max=tree[k].w;
 37         tree[k].Min=tree[k].w;
 38         return ;
 39     }
 40     LL mid=tree[k].l+tree[k].r>>1;
 41     Build_Tree(ll,mid,ls);
 42     Build_Tree(mid+1,rr,rs);
 43     update(k);
 44 }
 45 void down(LL k)
 46 {
 47     if(tree[k].V)
 48     {
 49         tree[ls].Add=0;
 50         tree[ls].V=1;
 51         tree[ls].w=(tree[ls].r-tree[ls].l+1)*tree[k].Set;
 52         tree[ls].Max=tree[ls].Min=tree[ls].Set=tree[k].Set;
 53         
 54         tree[rs].Add=0;
 55         tree[rs].V=1;
 56         tree[rs].w=(tree[rs].r-tree[rs].l+1)*tree[k].Set;
 57         tree[rs].Max=tree[rs].Min=tree[rs].Set=tree[k].Set;
 58         
 59         tree[k].Set=tree[k].V=0;
 60     }
 61     if(tree[k].Add)
 62     {
 63         tree[ls].w+=(tree[ls].r-tree[ls].l+1)*tree[k].Add;
 64         tree[ls].Add+=tree[k].Add;
 65         tree[ls].Max+=tree[k].Add;
 66         tree[ls].Min+=tree[k].Add;
 67         
 68         tree[rs].w+=(tree[rs].r-tree[rs].l+1)*tree[k].Add;
 69         tree[rs].Add+=tree[k].Add;
 70         tree[rs].Max+=tree[k].Add;
 71         tree[rs].Min+=tree[k].Add;
 72         tree[k].Add=0;    
 73     }
 74     
 75 }
 76 void Interval_Add(LL k,LL ll,LL rr,LL val)
 77 {
 78     if(ll<=tree[k].l&&tree[k].r<=rr)
 79     {
 80         tree[k].w+=(tree[k].r-tree[k].l+1)*val;
 81         tree[k].Add+=val;
 82         tree[k].Max+=val;
 83         tree[k].Min+=val;
 84         return ;
 85     }
 86     if(tree[k].Add||tree[k].V)    down(k);
 87     LL mid=tree[k].r+tree[k].l>>1;
 88     if(ll<=mid)    Interval_Add(ls,ll,rr,val);
 89     if(rr>mid)    Interval_Add(rs,ll,rr,val);
 90     update(k);
 91 }
 92 void Interval_Change(LL k,LL ll,LL rr,LL val)
 93 {
 94     if(ll<=tree[k].l&&tree[k].r<=rr)
 95     {
 96         tree[k].Max=tree[k].Min=val;
 97         tree[k].Set=val;tree[k].V=1;
 98         tree[k].w=(tree[k].r-tree[k].l+1)*val;
 99         tree[k].Add=0;
100         return ;
101     }
102     if(tree[k].Add||tree[k].V)    down(k);
103     LL mid=tree[k].r+tree[k].l>>1;
104     if(ll<=mid)    Interval_Change(ls,ll,rr,val);
105     if(rr>mid)    Interval_Change(rs,ll,rr,val);
106     update(k);
107 }
108 void Interval_Sum(LL k,LL ll,LL rr)
109 {
110     if(ll<=tree[k].l&&tree[k].r<=rr)
111     {
112         ans+=tree[k].w;
113         return ;
114     }
115     if(tree[k].Add||tree[k].V)    down(k);
116     LL mid=tree[k].r+tree[k].l>>1;
117     if(ll<=mid)    Interval_Sum(ls,ll,rr);
118     if(rr>mid)    Interval_Sum(rs,ll,rr);
119 }
120 void Interval_Max(LL k,LL ll,LL rr)
121 {
122     if(ll<=tree[k].l&&tree[k].r<=rr)
123     {
124         ans=max(ans,tree[k].Max);
125         return ;
126     }
127     if(tree[k].Add||tree[k].V)    down(k);
128     LL mid=tree[k].r+tree[k].l>>1;
129     if(ll<=mid)    Interval_Max(ls,ll,rr);
130     if(rr>mid)    Interval_Max(rs,ll,rr);
131 }
132 void Interval_Min(LL k,LL ll,LL rr)
133 {
134     if(ll<=tree[k].l&&tree[k].r<=rr)
135     {
136         ans=min(ans,tree[k].Min);
137         return ;
138     }
139     if(tree[k].Add||tree[k].V)    down(k);
140     LL mid=tree[k].r+tree[k].l>>1;
141     if(ll<=mid)    Interval_Min(ls,ll,rr);
142     if(rr>mid)    Interval_Min(rs,ll,rr);
143 }
144 int main()
145 {
146     read(n);read(m);
147     Build_Tree(1,n,1);
148     for(LL i=1;i<=m;i++)
149     {
150         char how[5];
151         scanf("%s",how);
152         if(how[0]=='a')//区间加 
153         {
154             LL x,y,val;read(x);read(y);read(val);
155             Interval_Add(1,x,y,val);
156         }
157         else if(how[0]=='s'&&how[1]=='e')//区间赋值 
158         {
159             LL x,y,val;read(x);read(y);read(val);
160             Interval_Change(1,x,y,val);
161         }
162         else if(how[0]=='s'&&how[1]=='u')//区间求和 
163         {
164             LL x,y;read(x);read(y);ans=0;
165             Interval_Sum(1,x,y);
166             printf("%lld\n",ans);
167         }
168         else if(how[0]=='m'&&how[1]=='a')//区间最大值 
169         {
170             LL x,y;read(x);read(y);ans=0;
171             Interval_Max(1,x,y);
172             printf("%lld\n",ans);
173         }
174         else if(how[0]=='m'&&how[1]=='i')// 区间最小值 
175         {
176             LL x,y;read(x);read(y);ans=INF;
177             Interval_Min(1,x,y);
178             printf("%lld\n",ans);
179         } 
180     }
181     return 0;
182 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏赵俊的Java专栏

合并区间

21330
来自专栏函数式编程语言及工具

Scalaz(3)- 基础篇:函数概括化-Generalizing Functions

  Scalaz是个通用的函数式编程组件库。它提供的类型、函数组件都必须具有高度的概括性才能同时支持不同数据类型的操作。可以说,scalaz提供了一整套所有编程...

19190
来自专栏闻道于事

Java基础类库

47560
来自专栏iOS技术杂谈

iOS block探究(一): 基础详解你要知道的block都在这里

你要知道的block都在这里 转载请注明出处 https://cloud.tencent.com/developer/user/1605429 本文大纲 blo...

33880
来自专栏Java 源码分析

HashSet 源码分析

HashSet 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 IDE 方便,所以在...

32640
来自专栏IT可乐

Java数据结构和算法(十四)——堆

  在Java数据结构和算法(五)——队列中我们介绍了优先级队列,优先级队列是一种抽象数据类型(ADT),它提供了删除最大(或最小)关键字值的数据项的方法,插入...

407110
来自专栏小二的折腾日记

LeetCode-49-Group-Anagrams

输入一个字符串数组,输出的是:将相同字符的字符串放在一个数组的二维数组。相同字符的处理,基本就是要对字符串排序的。然后需要考虑的就是排序好的那一个字符串怎么存的...

8010
来自专栏互联网杂技

今天由我亲自给大家总结

javascript内置对象有哪些? reg正则,booer,math,string,arr,obj,number,date,function,window全...

34180
来自专栏wOw的Android小站

[Objective-C] id类型和instancetype类型

id数据类型可以存储任何类型的对象。可以说,它是一般对象类型。 例如可以声明一个为id类型的变量:

11110
来自专栏郭耀华‘s Blog

Java集合框架(五)—— Map、HashMap、Hashtable、Properties、SortedMap、TreeMap、WeakHashMap、IdentityHashMap、EnumMap

Map Map用于保存具有映射关系的数据,因此Map集合里保存着两组值,一组值用于保存Map里的key,另一组值用于保存Map里的value,key和v...

30780

扫码关注云+社区

领取腾讯云代金券