POJ 3468 A Simple Problem with Integers（线段树基础） - c++编程基础

需要注意的是记录sum和lazy延时标识变量也要是64位整数，因为有乘法。




#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include //形如INT_MAX一类的   
#define MAX 100050   
#define INF 0x7FFFFFFF   
#define REP(i,s,t) for(int i=(s);i<=(t);++i)   
#define ll long long   
#define mem(a,b) memset(a,b,sizeof(a))   
#define mp(a,b) make_pair(a,b)   
#define L(x) x<<1   
#define R(x) x<<1|1   
# define eps 1e-5   
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂   
using namespace std;  
  
struct node {  
    int r,l,mid;  
    __int64 lazy,sum;  
}edge[4*MAX];  
  
int a[MAX];  
void up(int num) {  
    edge[num].sum = edge[L(num)].sum + edge[R(num)].sum;  
}  
  
void build(int l,int r,int num) {  
    edge[num].l = l;  
    edge[num].r = r;  
    edge[num].mid = (l+r) >> 1;  
    edge[num].lazy = 0;  
    if(l == r) {  
        edge[num].sum = a[l];  
        return ;  
    }  
    build(l,edge[num].mid,L(num));  
    build(edge[num].mid+1,r,R(num));  
    //   
    up(num);  
}  
  
void down(int num) {  
    if(edge[num].lazy) {  
        edge[L(num)].lazy += edge[num].lazy;  
        edge[R(num)].lazy += edge[num].lazy;  
        edge[L(num)].sum += (edge[L(num)].r - edge[L(num)].l + 1) * edge[num].lazy;  
        edge[R(num)].sum += (edge[R(num)].r - edge[R(num)].l + 1) * edge[num].lazy;  
        edge[num].lazy = 0;  
    }  
}  
  
void update(int l,int r,int num,__int64 k) {  
    if(l <= edge[num].l && r >= edge[num].r) {  
        edge[num].lazy += k;  
        edge[num].sum += (edge[num].r - edge[num].l + 1) * k;  
        return ;  
    }  
    down(num);  
    if(r <= edge[num].mid) {  
        update(l,r,L(num),k);  
    }  
    else if(l > edge[num].mid) {  
        update(l,r,R(num),k);  
    }  
    else {  
        update(l,edge[num].mid,L(num),k);  
        update(edge[num].mid + 1,r,R(num),k);  
    }  
    up(num);  
}  
  
__int64 query(int l,int r,int num) {  
    if(l <= edge[num].l && r >= edge[num].r) {  
        return edge[num].sum;  
    }  
    down(num);  
    if(r <= edge[num].mid) {  
        return query(l,r,L(num));  
    }  
    else if(l > edge[num].mid) {  
        return query(l,r,R(num));  
    }  
    else {  
        return query(l,edge[num].mid,L(num)) + query(edge[num].mid + 1,r,R(num));  
    }  
}  
int main() {  
  
    int n,m,b,c;  
    __int64 d;  
    char str[3];  
    scanf("%d%d",&n,&m);  
    for(int i=1; i<=n; i++) {  
        scanf("%d",&a[i]);  
    }  
    build(1,n,1);  
    for(int i=0; i





#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include //形如INT_MAX一类的
#define MAX 100050
#define INF 0x7FFFFFFF
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define L(x) x<<1
#define R(x) x<<1|1
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂
using namespace std;

struct node {
    int r,l,mid;
    __int64 lazy,sum;
}edge[4*MAX];

int a[MAX];
void up(int num) {
    edge[num].sum = edge[L(num)].sum + edge[R(num)].sum;
}

void build(int l,int r,int num) {
    edge[num].l = l;
    edge[num].r = r;
    edge[num].mid = (l+r) >> 1;
    edge[num].lazy = 0;
    if(l == r) {
        edge[num].sum = a[l];
        return ;
    }
    build(l,edge[num].mid,L(num));
    build(edge[num].mid+1,r,R(num));
    //
    up(num);
}

void down(int num) {
    if(edge[num].lazy) {
        edge[L(num)].lazy += edge[num].lazy;
        edge[R(num)].lazy += edge[num].lazy;
        edge[L(num)].sum += (edge[L(num)].r - edge[L(num)].l + 1) * edge[num].lazy;
        edge[R(num)].sum += (edge[R(num)].r - edge[R(num)].l + 1) * edge[num].lazy;
        edge[num].lazy = 0;
    }
}

void update(int l,int r,int num,__int64 k) {
    if(l <= edge[num].l && r >= edge[num].r) {
        edge[num].lazy += k;
        edge[num].sum += (edge[num].r - edge[num].l + 1) * k;
        return ;
    }
    down(num);
    if(r <= edge[num].mid) {
        update(l,r,L(num),k);
    }
    else if(l > edge[num].mid) {
        update(l,r,R(num),k);
    }
    else {
        update(l,edge[num].mid,L(num),k);
        update(edge[num].mid + 1,r,R(num),k);
    }
    up(num);
}

__int64 query(int l,int r,int num) {
    if(l <= edge[num].l && r >= edge[num].r) {
        return edge[num].sum;
    }
    down(num);
    if(r <= edge[num].mid) {
        return query(l,r,L(num));
    }
    else if(l > edge[num].mid) {
        return query(l,r,R(num));
    }
    else {
        return query(l,edge[num].mid,L(num)) + query(edge[num].mid + 1,r,R(num));
    }
}
int main() {

    int n,m,b,c;
    __int64 d;
    char str[3];
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
    }
    build(1,n,1);
    for(int i=0; i