首页 > 代码库 > POJ 3468 A Simple Problem with Integers

POJ 3468 A Simple Problem with Integers

2024-08-14 10:31:38   218人阅读

题目大意：给一组数据，Q 为查询求a,b区间和，C为为区间a,b间的各个元素都加上c。

题目思路：线段树模板

技术分享
#include<iostream>#include<algorithm>#include<cstring>#include<vector>#include<stdio.h>#include<queue>#include<math.h>#define INF 0x3f3f3f3f#define MAX 1000005#define Temp 1000000000using namespace std;long long a[MAX];struct node{    int l,r,root;    long long s,e;}tree[MAX];void MakeTree(int L,int R,int root){    tree[root].l=L;    tree[root].r=R;    tree[root].e=0;    int Mid=(L+R)/2;    if(L==R)    {        tree[root].s=a[L];        return;    }    MakeTree(L,Mid,root*2);    MakeTree(Mid+1,R,root*2+1);    tree[root].s=tree[root*2].s+tree[root*2+1].s;}void Down(int root){    tree[root*2].s+=(tree[root*2].r - tree[root*2].l + 1)*tree[root].e;    tree[root*2+1].s+=(tree[root*2+1].r - tree[root*2+1].l + 1)*tree[root].e;    tree[root*2].e+=tree[root].e;    tree[root*2+1].e+=tree[root].e;    tree[root].e=0;}void UpDate(int L,int R,int date,int root){    tree[root].s+=(R-L+1)*date;    int Mid=(tree[root].l + tree[root].r)/2;    if(tree[root].l==L && tree[root].r==R)    {          return;    }    Down(root);    if(R <= Mid)        UpDate(L,R,date,root*2);    else if(L > Mid)        UpDate(L,R,date,root*2+1);    else    {        UpDate(Mid+1,R,date,root*2+1);        UpDate(L,Mid,date,root*2);    }}long long Query(int L,int R,int root){    if(tree[root].l==L && tree[root].r==R)    {        return tree[root].s;    }    Down(root);    int Mid=(tree[root].l + tree[root].r)/2;    if(R <= Mid)        return Query(L,R,root*2);    else if(L > Mid)        return Query(L,R,root*2+1);    else    {        long long lsum=Query(L,Mid,root*2);        long long rsum=Query(Mid+1,R,root*2+1);        return lsum+rsum;    }}int main(){    int n,m,l,r,date;    char op[2];    while(scanf("%d%d",&n,&m)!=EOF)    {        for(int i=1;i<=n;i++)        {            scanf("%lld",&a[i]);        }        MakeTree(1,n,1);        while(m--)        {            scanf("%s",op);            if(op[0]==‘Q‘)            {                scanf("%d%d",&l,&r);                long long ans = Query(l,r,1);                printf("%lld\n",ans);            }            else            {                scanf("%d%d%d",&l,&r,&date);                UpDate(l,r,date,1);            }        }    }    return 0;}
View Code

 

POJ 3468 A Simple Problem with Integers


联系
我们