#POJ3468#关于整数的简单题

题目描述

一个数列有N个整数A1, A2, ..., AN，每次操作可以是将某区间数字都加上一个相同的整数，也可以是询问一个区间中所有数字的和。（这里区间指的是数列中连续的若干个数）。

对每次询问给出结果。

输入

输出

每行回答一个Q操作的结果

注意：答案可能超过int范围

样例输入

10 51 2 3 4 5 6 7 8 9 10Q 4 4Q 1 10Q 2 4C 3 6 3Q 2 4
样例输出
455915
懒标记对数列的基本维护
sum维护当前区间的和
tg维护当前区间和其子区间之间的单位改变量
下传的时候记得改变子区间的sum值,tg值
注意查询的时候也需要下传
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;typedef long long LL;const int Max=100000;struct node{    int l,r;    LL tg,sum;//tg：该段更改的值；sum：更改后该段的和}Tr[4*Max+5];int N,Q;void build(int i,int l,int r){    Tr[i].l=l,Tr[i].r=r;    Tr[i].tg=0;    if(l==r)return ;    int mid=(l+r)>>1;    build(i*2,l,mid);    build(i*2+1,mid+1,r);}void pushdown(int i){//下传标记，不只要更改左右子区间的和的值，还要下传单位更改参数。    Tr[i*2].sum+=Tr[i].tg*(Tr[i*2].r-Tr[i*2].l+1);    Tr[i*2+1].sum+=Tr[i].tg*(Tr[i*2+1].r-Tr[i*2+1].l+1);    Tr[i*2].tg+=Tr[i].tg;    Tr[i*2+1].tg+=Tr[i].tg;    Tr[i].tg=0;}void add(int i,int l,int r,LL val){    if(r<Tr[i].l||l>Tr[i].r)return ;    if(l<=Tr[i].l&&r>=Tr[i].r){        Tr[i].sum+=val*(Tr[i].r-Tr[i].l+1);        Tr[i].tg+=val;//当前区间新增更改参数        return ;    }    if(Tr[i].tg)        pushdown(i);    add(i*2,l,r,val);    add(i*2+1,l,r,val);    Tr[i].sum=Tr[i*2].sum+Tr[i*2+1].sum;}LL cnt(int i,int l,int r){    if(l>Tr[i].r||r<Tr[i].l)  return 0;    if(l<=Tr[i].l&&r>=Tr[i].r)    return Tr[i].sum;    if(Tr[i].tg)pushdown(i);    LL lft=cnt(i*2,l,r);    LL rft=cnt(i*2+1,l,r);    Tr[i].sum=Tr[i*2].sum+Tr[i*2+1].sum;    return lft+rft;}int main(){    scanf("%d%d",&N,&Q);    build(1,1,N);    int x;    for(int i=1; i<=N; ++i){        scanf("%d",&x);        add(1,i,i,x);    }    char ord[3];    int a,b,c;    for(int i=1; i<=Q; ++i){        scanf("%s",ord);        if(ord[0]=='C'){            scanf("%d%d%d",&a,&b,&c);            add(1,a,b,c);        }        else{            scanf("%d%d",&a,&b);            PRintf("%lld/n",cnt(1,a,b));        }    }    return 0;}