P3372 【模板】线段树 1 区间查询与区间修改

2018-06-17 22:39:32来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

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

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

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

输入输出格式

输入格式:

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

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

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

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

操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和

输出格式:

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

输入输出样例

输入样例#1:
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
输出样例#1:
11
8
20

说明

时空限制:1000ms,128M

数据规模:

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

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

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

(数据已经过加强^_^,保证在int64/long long数据范围内)

样例说明:

 

在这里提醒大家一点

如果你用的是Dev-c++的5.92版本的话,用%lld输入可能会发生运行时错误

这时候如果你确保你的程序百分百对的话,可以直接提交

如果你不放心自己的程序,可以把%lld改成%I64d(I是大写i)进行调试,这样就不会出错了

但是切记

提交到洛谷上的时候一定要写%lld!!!!!!

否则全部WA而不是RE

切记切记

(ps:cena评测系统也是%lld)

我的代码基本是由函数构成的

写法比较通俗易懂

大家可以参考一下

再教大家一个小技巧:

如果你想要大批量的吧int改为long long int 的话

可以使#define 语句

然后用查找替换功能

注意查找的时候 查找的是 int+空格

否则你的printf会变得非常美观(手动滑稽)

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define lglg long long int
 5 using namespace std;
 6 const lglg MAXN=200001;
 7 lglg n,m;
 8 lglg ans=0;
 9 struct node
10 {
11     lglg l,r,w,f;
12 }tree[MAXN*4];
13 inline void updata(lglg k)
14 {
15     tree[k].w=tree[k*2].w+tree[k*2+1].w;
16 }
17 inline void build(lglg k,lglg ll,lglg rr)
18 {
19     tree[k].l=ll;tree[k].r=rr;
20     if(tree[k].l==tree[k].r)
21     {
22         scanf("%lld",&tree[k].w);
23         return ;
24     }
25     lglg m=(ll+rr)/2;
26     build(k*2,ll,m);
27     build(k*2+1,m+1,rr);
28     updata(k);
29 }
30 inline void down(lglg k)
31 {
32     tree[k*2].f+=tree[k].f;
33     tree[k*2+1].f+=tree[k].f;
34     tree[k*2].w+=(tree[k*2].r-tree[k*2].l+1)*tree[k].f;
35     tree[k*2+1].w+=(tree[k*2+1].r-tree[k*2+1].l+1)*tree[k].f;
36     tree[k].f=0;
37 }
38 inline void interval_change(lglg k,lglg ll,lglg rr,lglg v)
39 {
40     if(tree[k].l>=ll&&tree[k].r<=rr)
41     {
42         tree[k].w+=(tree[k].r-tree[k].l+1)*v;
43         tree[k].f+=v;
44         return ;
45     }
46     if(tree[k].f)   down(k);
47     lglg m=(tree[k].l+tree[k].r)/2;
48     if(ll<=m)    interval_change(k*2,ll,rr,v);
49     if(rr>m)     interval_change(k*2+1,ll,rr,v);
50     updata(k);
51 }
52 inline void interval_ask(lglg k,lglg ll,lglg rr)
53 {
54     if(tree[k].l>=ll&&tree[k].r<=rr)
55     {
56         ans+=tree[k].w;
57         return ;
58     }
59     if(tree[k].f)    down(k);
60     lglg m=(tree[k].l+tree[k].r)/2;
61     if(ll<=m)
62         interval_ask(k*2,ll,rr);
63     if(rr>m)
64         interval_ask(k*2+1,ll,rr);
65 }
66 int main()
67 {
68     scanf("%lld",&n);
69     scanf("%lld",&m);
70     build(1,1,n);
71     while(m--)
72     {
73         lglg how;
74         scanf("%lld",&how);
75         if(how==1)//区间增加 
76         {
77             lglg x,y,v;
78             scanf("%lld%lld%lld",&x,&y,&v);
79             interval_change(1,x,y,v);
80         }
81         else//区间求和 
82         {
83             lglg x,y;
84             ans=0;
85             scanf("%lld%lld",&x,&y);
86             interval_ask(1,x,y);
87             printf("%lld\n",ans);
88         }
89     }
90     return 0;
91 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Leetcode: 23. Merge k Sorted Lists

下一篇:[原创]ObjectARX开发环境搭建之VS2010+ObjectARX2012Wizard+Addi