Posted on 2011-11-14 16:11
C小加 閱讀(4011)
評論(-1) 編輯 收藏 引用 所屬分類:
解題報告
我的第一個線段樹題，用樹狀數組也可以過，我主要是想練習一下線段樹。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=50003;
int v[MAXN],sum;
typedef struct
{
int left,right,mid;
int count;
}line;
line l[4*MAXN];
void Creat(int a,int b,int r)
{
if(a==b)
{
l[r].left=l[r].right=a;
l[r].count=v[a];
return;
}
l[r].left=a;
l[r].right=b;
l[r].mid=(a+b)/2;
Creat(a,l[r].mid,2*r);
Creat(l[r].mid+1,b,2*r+1);
l[r].count=l[2*r].count+l[2*r+1].count;
}
void Add(int n,int m,int r)
{
if(l[r].left==n&&l[r].right==n)
{
l[r].count+=m;
return;
}
if(n>l[r].mid)
{
Add(n,m,2*r+1);
}
else
{
Add(n,m,2*r);
}
l[r].count=l[2*r].count+l[2*r+1].count;
}
void Query(int a,int b,int r)
{
if(l[r].left==a&&l[r].right==b)
{
sum+=l[r].count;
}
else if(a>l[r].mid)
{
Query(a,b,2*r+1);
}
else if(b<=l[r].mid)
{
Query(a,b,2*r);
}
else
{
Query(a,l[r].mid,2*r);
Query(l[r].mid+1,b,2*r+1);
}
}
int main()
{
int cnt=1;
int t;
scanf("%d",&t);
while(t--)
{
printf("Case %d:\n",cnt++);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
}
Creat(1,n,1);
char s[7];
while(scanf("%s",s),s[0]!='E')
{
int b,c;
scanf("%d %d",&b,&c);
if(s[0]=='Q')
{
sum=0;
Query(b,c,1);
printf("%d\n",sum);
}
else if(s[0]=='A')
{
Add(b,c,1);
}
else if(s[0]=='S')
{
Add(b,-1*c,1);
}
}
}
return 0;
}