poj3468区间延迟更新模板题

#include<stdio.h>

#include<string.h>

#define N 100000

struct st{

int x,y;

__int64 yanchi,sum;

}a[N*4];

__int64 b[N];

void build(int t,int x,int y) {

a[t].x=x;

a[t].y=y;

a[t].yanchi=0;

if(x==y) {

  a[t].sum=b[x];

  return ;

}

int temp=t*2;

int mid=(a[t].x+a[t].y)/2;

build(temp,x,mid);

build(temp+1,mid+1,y);

a[t].sum=a[temp].sum+a[temp+1].sum;

return ;

}

void change(int t,int x,int y,int z) {

if(a[t].x==x&&a[t].y==y) {

  a[t].yanchi+=z;

  return ;

}

a[t].sum+=(y-x+1)*z;

int temp=t*2;

int mid=(a[t].x+a[t].y)/2;

if(y<=mid)

  change(temp,x,y,z);

else

  if(x>mid)

   change(temp+1,x,y,z);

  else {

   change(temp,x,mid,z);

   change(temp+1,mid+1,y,z);

  }

  return ;

}

__int64 qury(int t,int x,int y) {

if(a[t].x==x&&a[t].y==y)

  return a[t].sum+(y-x+1)*a[t].yanchi;

   int temp=t<<1;

   int mid=(a[t].y+a[t].x)/2;

   a[temp+1].yanchi+=a[t].yanchi;

   a[temp].yanchi+=a[t].yanchi;

   a[t].sum+=a[t].yanchi*(a[t].y-a[t].x+1);

   a[t].yanchi=0;

   if(y<=mid)

    return qury(temp,x,y);

   else

    if(x>mid)

     return qury(temp+1,x,y);

    else

     return qury(temp,x,mid)+qury(temp+1,mid+1,y);

}

int main() {

int i,j,k,n,m;

char s[100];

while(scanf("%d%d",&n,&m)!=EOF) {

  for(i=1;i<=n;i++)

   scanf("%I64d",&b[i]);

  build(1,1,n);

  while(m--) {

   scanf("%s",s);

   if(s[0]=='Q') {

    scanf("%d%d",&i,&j);

    printf("%I64d\n",qury(1,i,j));

   }

   else {

    scanf("%d%d%d",&i,&j,&k);

    change(1,i,j,k);

   }

}

}

return 0;

}

巴特西

poj3468区间延迟更新模板题

最新文章

热门文章