如题,已知一个数列,你需要进行下面两种操作:
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 }