| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
我要吐槽,线段树一直WA,原来是lazy数组没开long long如果一直WA,但测试数据都对,可以看看tree[N],a[N],lazy[N],ret,x有没有long long
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
#define N 1010000
long long tree[N],a[N];
long long lazy[N];//k++的容器,所以要long long
void sbuild(int l,int r,int p){
if(l==r) {
tree[p]=a[l];
return ;
}
int mid=(l+r)>>1;
sbuild(l,mid,p<<1);
sbuild(mid+1,r,p<<1|1);
tree[p]=tree[p<<1]+tree[p<<1|1];//设置父结点为左右子树的最大值
}
void supdate(int L,int R,int p,int l,int r,int k){
if(L<=l&&R>=r) {
tree[p]+=k*(r-l+1);
lazy[p]+=k;
return ;
}
int mid=(l+r)>>1;
if(lazy[p]!=0){
tree[p<<1]+=(mid-l+1)*lazy[p];//为什么不*k?
tree[p<<1|1]+=(r-mid)*lazy[p];
lazy[p<<1]+=lazy[p];
lazy[p<<1|1]+=lazy[p];//标记p的下一层也已修改
lazy[p]=0;//当前标记取消
}
if(mid>=L) supdate(L,R,p<<1,l,mid,k);
if(mid+1<=R) supdate(L,R,p<<1|1,mid+1,r,k);//为什么不是<=
tree[p]=tree[p<<1]+tree[p<<1|1];
}
//查询[L,R]的信息
long long ssearch2 (int l,int r,int p,int L,int R){
if(l>=L&&r<=R) return tree[p];
int mid=(l+r)>>1;
long long ret=0;
if(lazy[p]!=0){
tree[p<<1]+=(mid-l+1)*lazy[p];//这个是干啥的?
tree[p<<1|1]+=(r-mid)*lazy[p];
lazy[p<<1]+=lazy[p];//也许是防止标记了lazy的还没运行
lazy[p<<1|1]+=lazy[p];//反正都修改完了这个就不会运行
lazy[p]=0;
}
if(mid>=L) ret+=ssearch2(l,mid,p<<1,L,R);
if(mid+1<=R) ret+=ssearch2(mid+1,r,p<<1|1,L,R);
return ret;
}
int main(){
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
getchar();
sbuild(1,n,1);
while(q--){
char c;
scanf(" %c",&c);
getchar();
int b,d;
int e;
if(c=='C'){
scanf("%d%d%d",&b,&d,&e);
supdate(b,d,1,1,n,e);
}
else{
scanf("%d %d",&b,&d);
long long x=ssearch2(1,n,1,b,d);
printf("%lld\n",x);
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator