codevs1081 线段树练习 2<区间修改>

1081 线段树练习 2

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 大师 Master

题目描述 Description

给你N个数，有两种操作

1：给区间[a,b]的所有数都增加X

2：询问第i个数是什么？

输入描述
Input Description

第一行一个正整数n，接下来n行n个整数，再接下来一个正整数Q，表示操作的个数. 接下来Q行每行若干个整数。如果第一个数是1，后接3个正整数a,b,X，表示在区间[a,b]内每个数增加X,如果是2，后面跟1个整数i, 表示询问第i个位置的数是多少。

输出描述
Output Description

对于每个询问输出一行一个答案

样例输入
Sample Input

1 2 3 2

2 3

样例输出
Sample Output

数据范围及提示
Data Size & Hint

数据范围

1<=n<=100000

1<=q<=100000

NotOnlySuccess

有兴趣的可以去这个博客看一下线段树，讲的真是很好。

先看一个暴力吧并没有什么用，我只是比较惊讶于暴力的神奇；正解在下边。.

 #include<iostream>

 using namespace std;

 #include<cstdio>

 int n,m,a[],l,r,f;

 int main() {

     cin>>n;

     for(int i=; i<=n; i++)

         cin>>a[i];

     cin>>m;

     for(int i=; i<=m; i++) {

         int x;

         cin>>x;

         if(x==) {

             cin>>l>>r>>f;

             for(int i=l; i<=r; i++)

                 a[i]+=f;

         }

         if(x==) {

             cin>>f;

             cout<<a[f]<<endl;

         }

     }

     return ;

 }

这里才是正解：

 //s d s

 #include<cstdio>

 #include<iostream>

 #include<cstdlib>

 using namespace std;

 const int N=;

 int a[N],sum[N];int miku[N];

 int b,c,d,e;

 void update(int rt)

 {

     sum[rt]=sum[rt*]+sum[rt*+];

 }

 void build(int l,int r,int rt)

 {

     if(l==r)

     {

         sum[rt]=a[l];

         return ;

     }

     int m=(l+r)/;

     build(l,m,rt*);

     build(m+,r,rt*+);

     update(rt);

 }

 void midify_interval(int l,int r,int rt,int nowl,int nowr,int neww)

 {

     if(nowl==l&&nowr==r)

     {

         miku[rt]+=neww;

         sum[rt]+=neww*(r-l+);

         return ;

     }

     int m=(l+r)>>;

     if(nowr<=m) midify_interval(l,m,rt*,nowl,nowr,neww);

     else if(nowl>m) midify_interval(m+,r,rt*+,nowl,nowr,neww);

     else

     {

         midify_interval(l,m,rt*,nowl,m,neww);

         midify_interval(m+,r,rt*+,m+,nowr,neww);

     }

     update(rt);

 }

 int query(int l,int r,int rt,int nowrt)

 {

     if(l==r)

     {

         return sum[rt];

     }

     int m=(r+l)/;

     sum[rt+rt]+=miku[rt]*(m-l+);

     sum[rt+rt+]+=miku[rt]*(r-m);

     miku[rt+rt]+=miku[rt];

     miku[rt+rt+]+=miku[rt];

     miku[rt]=;

     int ans=;

     if(nowrt<=m) ans=query(l,m,rt<<,nowrt);

     else if(nowrt>m)  ans=query(m+,r,rt*+,nowrt);

     return ans;

 }

 int main()

 {

     int n;

     scanf("%d",&n);

     for(int i=;i<=n;i++)scanf("%d",a+i);

     build(,n,);

     int m;

     scanf("%d",&m);

     for(int i=;i<=m;i++)

     {

         scanf("%d",&b);

         if(b==)

         {

             scanf("%d%d%d",&c,&d,&e);

             midify_interval(,n,,c,d,e);

         }

         if(b==)

         {

             scanf("%d",&c);

             printf("%d\n",query(,n,,c));

         }

     }

     return ;

 }

巴特西

codevs1081 线段树练习 2<区间修改>

1081 线段树练习 2

最新文章

热门文章