A Simple Problem with Integers

Time Limit: 1 Sec Memory Limit: 256 MB

题目连接

http://poj.org/problem?id=3468

Description

You have

N integers,

₁,

₂, ... ,

A_N. 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 ≤

Q ≤ 100000.

The second line contains

N numbers, the initial values of

₁,

₂, ... ,

A_N. -1000000000 ≤

A_i ≤ 1000000000.

Each of the next

Q lines represents an operation.

c" means adding

c to each of

A_a,

A_a

₊₁, ... ,

A_b. -10000 ≤

c ≤ 10000.

b" means querying the sum of

A_a,

A_a

₊₁, ... ,

A_b.

Output

You need to answer all

Q commands in order. One answer in a line.

Sample Input

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

Sample Output

HINT

题意

区间加，区间查询和

题解：

线段树，记住懒操作~

代码：

//qscqesze#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 200001#define mod 10007#define eps 1e-9int Num;char CH[20];//const int inf=0x7fffffff; //нчоч╢Сconst int inf=0x3f3f3f3f;/*inline void P(int x){ Num=0;if(!x){putchar('0');puts("");return;} while(x>0)CH[++Num]=x%10,x/=10; while(Num)putchar(CH[Num--]+48); puts("");}*///**************************************************************************************inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}inline void P(int x){ Num=0;if(!x){putchar('0');puts("");return;} while(x>0)CH[++Num]=x%10,x/=10; while(Num)putchar(CH[Num--]+48); puts("");}struct node{ int l,r; ll sum,add; void fun(ll tmp) { add+=tmp; sum+=(r-l+1)*tmp; }}a[maxn*4];ll d[maxn];void relax(int x){ if(a[x].add) { a[x<<1].fun(a[x].add); a[x<<1|1].fun(a[x].add); a[x].add=0; }}void build(int x,int l,int r){ a[x].l=l,a[x].r=r; if(l==r) { a[x].sum=d[l]; } else { int mid=(l+r)>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r); a[x].sum=a[x<<1].sum+a[x<<1|1].sum; }}void update(int x,int st,int ed,ll c){ int l=a[x].l,r=a[x].r; if(st<=l&&r<=ed) a[x].fun(c); else { relax(x); int mid=(l+r)>>1; if(st<=mid)update(x<<1,st,ed,c); if(ed>mid) update(x<<1|1,st,ed,c); a[x].sum=a[x<<1].sum+a[x<<1|1].sum; }}ll query(int x,int st,int ed){ int l=a[x].l,r=a[x].r; if(st<=l&&r<=ed) return a[x].sum; else { relax(x); int mid=(l+r)>>1; ll sum1=0,sum2=0; if(st<=mid) sum1=query(x<<1,st,ed); if(ed>mid) sum2=query(x<<1|1,st,ed); return sum1+sum2; }}int main(){ int n=read(),m=read(); for(int i=1;i<=n;i++) d[i]=read(); build(1,1,n); char s[3]; int bb,cc,dd; for(int i=0;i