首页 > 代码库 > poj3468 A Simple Problem with Integers

poj3468 A Simple Problem with Integers

2024-07-12 17:57:53   227人阅读

Description

You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 51 2 3 4 5 6 7 8 9 10Q 4 4Q 1 10Q 2 4C 3 6 3Q 2 4

Sample Output

455915

Hint

The sums may exceed the range of 32-bit integers.
题目大意：给出一些数和一些操作，q表示询问，c表示修改。
思路：纯线段树
 1 /* 2  * Author:  Joshua 3  * Created Time:  2014年07月16日 星期三 15时19分46秒 4  * File Name: poj3468.cpp 5  */ 6 #include<cstdio> 7 #include<algorithm> 8 #define maxn 100005 9 #define L(x) (x<<1)10 #define R(x) (x<<1 |1)11 typedef long long LL;12 using namespace std;13 struct node14 {15     int l,r;16     LL sum,mark;17 } e[maxn <<2];18 int n,m;19 int a[maxn];20 LL ans;21 void built(int t,int l,int r)22 {23     e[t].l=l;24     e[t].r=r;25     e[t].mark=0;26     if (l==r)27     {28         e[t].sum=a[e[t].l];29         return;30     }31     int mid=l+r >>1;32     built(L(t),l,mid);33     built(R(t),mid+1,r);34     e[t].sum=e[L(t)].sum+e[R(t)].sum;35 }36 37 void add(int t,int l,int r,int v)38 {39     if (l==e[t].l && r==e[t].r)40     {41         e[t].mark+=v;42         return;43     }44     e[t].sum+=(r-l+1)*v;45     int mid=e[t].l+e[t].r >>1;46     if (r>mid) add(R(t),max(mid+1,l),r,v);47     if (l<=mid) add(L(t),l,min(mid,r),v);48 }49 50 void getSum(int t,int l,int r)51 {52     ans+=e[t].mark*(r-l+1);53     if (e[t].l==l && e[t].r==r)54     {55         ans+=e[t].sum;56         return;57     }58     int mid=e[t].l+e[t].r >>1;59     if (r>mid) getSum(R(t),max(mid+1,l),r);60     if (l<=mid) getSum(L(t),l,min(mid,r));61 }62 void solve()            63 {64     for (int i=1;i<=n;++i)65        scanf("%d",&a[i]);66     built(1,1,n);67     char c;68     int x,y,v;69     for (int i=1;i<=m;++i)70     {71         scanf("%c",&c);72         scanf("%c%d%d",&c,&x,&y);73         if (c==‘Q‘) 74         {75             ans=0;76             getSum(1,x,y);77             printf("%lld\n",ans);78         }79         else80         {81             scanf("%d",&v);82             add(1,x,y,v);83         }84     }    85 }86 int main()87 {88     while (scanf("%d%d",&n,&m)==2)89         solve();90 91     return 0;92 }

 


联系
我们