Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:给一个线段树容易出错的测试用例

Posted by 18357 at 2014-05-22 18:21:18 on Problem 3468
In Reply To:给一个线段树容易出错的测试用例 Posted by:fanlonglong8500 at 2008-08-25 10:54:41
```#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define N 100005

typedef struct KSD
{
int l,r;
long long w,f;
}ksd;ksd s[N<<2];
int n,m;
void reset()
{
memset(s,0,sizeof(s));
}
void swap(int &a,int &b){int c=a;a=b;b=c;}

void build(int note,int l,int r)
{
int mid=(l+r)>>1;
s[note].l=l;
s[note].r=r;
if(l==r)
{
scanf("%lld",&s[note].w);
return ;
}
build(note<<1,l,mid);
build((note<<1)+1,mid+1,r);
s[note].w=s[note<<1].w+s[(note<<1)+1].w;
}

void et(int note)
{
s[note].w+=(s[note].f*(s[note].r-s[note].l+1));
if(s[note].l!=s[note].r)
{
s[note<<1].f+=s[note].f;
s[(note<<1)+1].f+=s[note].f;
}
s[note].f=0;
}

long long noc(int note,int l,int r,int x)
{
long long a,b;
b=0;
int mid=(s[note].l+s[note].r)>>1;
et(note);
if(l==s[note].l&&r==s[note].r)
{
s[note].f=x;
return s[note].w;
}
//s[note].w+=(x*(r-l+1));就是它就是它，忘了这个东西的话样例能过，楼主测点过不了。
if(r<=mid)
{
a=noc(note<<1,l,r,x);
return a;
}
else if(l>mid)
{
a=noc((note<<1)+1,l,r,x);
return a;
}
else
{
a=noc(note<<1,l,mid,x);
b=noc((note<<1)+1,mid+1,r,x);
return a+b;
}
}

char a;
int b,c,d;

void lesgo()
{
int i,j,k;
for(i=1;i<=m;i++)
{
scanf("\n%c%d%d",&a,&b,&c);
if(b>c)swap(b,c);
if(a=='Q')
{
printf("%lld\n",noc(1,b,c,0));
}
else
{
scanf("%d",&d);
noc(1,b,c,d);
}
}
return ;
}

int main()
{
//freopen("test.in","r",stdin);
while(scanf("%d%d",&n,&m)!=EOF)
{
reset();
build(1,1,n);
lesgo();
}
return 0;
}
/*
noc函数集修改与查找于一身。

4
85
-16
-147
-122
-6
115
27
-73
7
14
21
25
57

*/```

Followed by: