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

题目描述

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

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：

输出样例#1：

说明

时空限制：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会变得非常美观（手动滑稽）

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define lglg long long int

 using namespace std;

 const lglg MAXN=;

 lglg n,m;

 lglg ans=;

 struct node

 {

     lglg l,r,w,f;

 }tree[MAXN*];

 inline void updata(lglg k)

 {

     tree[k].w=tree[k*].w+tree[k*+].w;

 }

 inline void build(lglg k,lglg ll,lglg rr)

 {

     tree[k].l=ll;tree[k].r=rr;

     if(tree[k].l==tree[k].r)

     {

         scanf("%lld",&tree[k].w);

         return ;

     }

     lglg m=(ll+rr)/;

     build(k*,ll,m);

     build(k*+,m+,rr);

     updata(k);

 }

 inline void down(lglg k)

 {

     tree[k*].f+=tree[k].f;

     tree[k*+].f+=tree[k].f;

     tree[k*].w+=(tree[k*].r-tree[k*].l+)*tree[k].f;

     tree[k*+].w+=(tree[k*+].r-tree[k*+].l+)*tree[k].f;

     tree[k].f=;

 }

 inline void interval_change(lglg k,lglg ll,lglg rr,lglg v)

 {

     if(tree[k].l>=ll&&tree[k].r<=rr)

     {

         tree[k].w+=(tree[k].r-tree[k].l+)*v;

         tree[k].f+=v;

         return ;

     }

     if(tree[k].f)   down(k);

     lglg m=(tree[k].l+tree[k].r)/;

     if(ll<=m)    interval_change(k*,ll,rr,v);

     if(rr>m)     interval_change(k*+,ll,rr,v);

     updata(k);

 }

 inline void interval_ask(lglg k,lglg ll,lglg rr)

 {

     if(tree[k].l>=ll&&tree[k].r<=rr)

     {

         ans+=tree[k].w;

         return ;

     }

     if(tree[k].f)    down(k);

     lglg m=(tree[k].l+tree[k].r)/;

     if(ll<=m)

         interval_ask(k*,ll,rr);

     if(rr>m)

         interval_ask(k*+,ll,rr);

 }

 int main()

 {

     scanf("%lld",&n);

     scanf("%lld",&m);

     build(,,n);

     while(m--)

     {

         lglg how;

         scanf("%lld",&how);

         if(how==)//区间增加

         {

             lglg x,y,v;

             scanf("%lld%lld%lld",&x,&y,&v);

             interval_change(,x,y,v);

         }

         else//区间求和

         {

             lglg x,y;

             ans=;

             scanf("%lld%lld",&x,&y);

             interval_ask(,x,y);

             printf("%lld\n",ans);

         }

     }

     return ;

 }

巴特西

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

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章