POJ 3468

这是一道线段树的区间更新问题。。。。。

题意是给你一个N和Q。

然后给你一个N的数列。和Q个操作或者询问。

C a,b,c  就是在下标a-b之间的的数列的值+c

Q a,b  就是询问下标a-b之间的数列的值得和

我的思路：

先建立线段树。。。

每个区间存的值为改区间内所有值得和。

如果操作C a,b,c  刚好覆盖到某个区间时。 不需要在更新下去。而是把c的值保存在lazy中。

然后在需要用到该区间的子树时。。  再往下更新一步、、、、还原该区间的lazy值。把lazy值赋给子树的lazy值；

如果不这样做的话= =就会TLE= = 

注意数据类型= =  int 会爆掉= =  我在这里WA了好多次= =

贴上代码= =

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
long long m;
struct tree{
int left;
int right;
int lazy;
long long sum;
}tree[400000];
void inset(int inst,int le,int ri)
{
tree[inst].left=le;
tree[inst].right=ri;
tree[inst].sum=0;
tree[inst].lazy=0;
if(le==ri) return ;
int mid=(le+ri)>>1;
inset(2*inst,le,mid);
inset(2*inst+1,mid+1,ri);
}
void lazy(int inst,long long k)
{
int mid=(tree[inst].left+tree[inst].right)>>1;
tree[2*inst].sum+=(mid-tree[inst].left+1)*k;
tree[2*inst].lazy+=k;
tree[2*inst+1].sum+=(tree[inst].right-mid)*k;
tree[2*inst+1].lazy+=k;
tree[inst].lazy=0;
}
void Q(int inst,int le,int ri)
{
if(le==tree[inst].left&&ri==tree[inst].right)
{
m+=tree[inst].sum;
return ;
}
if(tree[inst].lazy!=0)
{
lazy(inst,tree[inst].lazy);
}
int mid=(tree[inst].left+tree[inst].right)>>1;
if(mid>=ri)
Q(2*inst,le,ri);
else if(mid<le)
Q(2*inst+1,le,ri);
else
{
Q(2*inst,le,mid);
Q(2*inst+1,mid+1,ri);
}
}
void C(int
inst,int le,int ri,long long k)
{
if(le>=tree[inst].left&&ri<=tree[inst].right)
{
tree[inst].sum+=(ri-le+1)*k;
//cout<<tree[inst].left<<" "<<tree[inst].right<<" "<<k<<endl;
}
if(tree[inst].left==tree[inst].right) return ;
if(le==tree[inst].left&&ri==tree[inst].right)
{ //if(le==ri) cout<<le<<endl;
tree[inst].lazy+=k;
return ;
}
int mid=(tree[inst].left+tree[inst].right)>>1;
if(ri<=mid)
C(2*inst,le,ri,k);
else if(le>mid)
C(2*inst+1,le,ri,k);
else
{
C(2*inst,le,mid,k);
C(2*inst+1,mid+1,ri,k);
}
}
int main()
{
int n,q;
while(scanf("%d%d",&n,&q)!=EOF)
{
int a;
inset(1,1,n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
C(1,i,i,a);
}
char h[10];
while(q--)
{
int k1,k2;
scanf("%s",h);
scanf("%d%d",&k1,&k2);
if(strcmp(h,"Q")==0)
{
m=0;
Q(1,k1,k2);
printf("%I64dn",m);
}
else
{
int k;
scanf("%d",&k);
C(1,k1,k2,k);
}
}
}
}

最后

以上就是知性爆米花最近收集整理的关于POJ 3468的全部内容，更多相关POJ内容请搜索靠谱客的其他文章。