477
藍橋杯-算法訓練 操作格子
算法訓練 操作格子時間限製：1.0s 內存限製：256.0MB
問題描述
有n個格子，從左到右放成一排，編號為1-n。
共有m次操作，有3種操作類型：
1.修改一個格子的權值，
2.求連續一段格子權值和，
3.求連續一段格子的最大值。
對於每個2、3操作輸出你所求出的結果。
輸入格式
第一行2個整數n，m。
接下來一行n個整數表示n個格子的初始權值。
接下來m行，每行3個整數p,x,y，p表示操作類型，p=1時表示修改格子x的權值為y，p=2時表示求區間[x,y]內格子權值和，p=3時表示求區間[x,y]內格子最大的權值。
輸出格式
有若幹行，行數等於p=2或3的操作總數。
每行1個整數，對應了每個p=2或3操作的結果。
樣例輸入
4 3
1 2 3 4
2 1 3
1 4 3
3 1 4
樣例輸出
6
3
數據規模與約定
對於20%的數據n <= 100，m <= 200。
對於50%的數據n <= 5000，m <= 5000。
對於100%的數據1 <= n <= 100000，m <= 100000，0 <= 格子權值 <= 10000。
此題考察了線段樹的構造與使用，下圖就是線段樹的概念圖：
【1,10】
【1,5】 【6,10】
【1,3】 【4,5】 【6,8】 【9,10】
【1,2】 【3,3】 【4,4】 【5,5】 【6,7】 【8,8】 【9,9】 【10,10】
【1,1】【2,2】 【6,6】【7,7】
超時代碼：（用數組的一般方法一定會超時，計算100000個數組的和需要較多時間）
#include<stdio.h>
int a[100010];
void Fun1(int x,int y,int a[]){
a[x]=y;
}
int Fun2(int x,int y,int a[]){
int i,sum=0;
for(i=x;i<=y;i++)
sum+=a[i];
return sum;
}
int Fun3(int x,int y,int a[]){
int i,max=-999999;
for(i=x;i<=y;i++)
if(a[i]>max)
max=a[i];
return max;
}
int main()
{
int i,n,m,p,x,y;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
while(m--)
{
scanf("%d%d%d",&p,&x,&y);
if(p==1){
Fun1(x,y,a);
}else if(p==2){
printf("%d\n",Fun2(x,y,a));
}else{
printf("%d\n",Fun3(x,y,a));
}
}
return 0;
}
AC代碼：（采用線段樹）
#include<stdio.h>
int Testmax(int a,int b)//判斷大小的函數
{return a>b?a:b;}
typedef struct node//構造一個線段樹的結構體
{
int l,r;
int sum,max;
}node;
node a[400010];//申請線段樹節點空間
void Build(int n,int l,int r);//構建一棵範圍在l至r範圍的線段樹
void Insert(int n, int v, int num);//為線段樹插入一個值
void Change(int n, int v, int num);//為線段樹改變一個權值
int QSum(int n, int l, int r);//求一個範圍內的權值總和
int QMax(int n, int l, int r);//求一個範圍內的最大值
int main()
{
int i,j,n,m,value,que,b,c;
scanf("%d%d",&n,&m);
Build(1,1,n);//構建一個範圍為1至n的線段樹
for(i=1;i<=n;i++)
{
scanf("%d",&value);
Insert(1,i,value);//向已有線段樹中插入權值
}
while(m--)
{
scanf("%d%d%d",&que,&b,&c);
switch(que)
{
case 1:Change(1,b,c);break;//改變節點b的權值為c
case 2:printf("%d\n", QSum(1,b,c));break;//計算b至c範圍內的權值和
case 3:printf("%d\n", QMax(1,b,c));break;//計算b至c範圍內的最大權值
}
}
return 0;
}
void Build(int n,int l,int r)//構建一棵範圍在l至r範圍的線段樹
{
a[n].l=l;//左邊距
a[n].r=r;//右邊距
a[n].sum=0;//範圍在l至r之間權值和
a[n].max=0;//範圍在l至r之間權值最大值
if(l==r)//如果左右邊距相同不再構建孩子
return;
Build(n*2,l,(l+r)/2);//構建範圍為l至(l+r)/2的左孩子
Build(n*2+1,(l+r)/2+1,r);//構建範圍為l至(l+r)/2的右孩子
}
void Insert(int n, int v, int num)//為線段樹插入一個值
{
a[n].sum += num;//總和加入新數
if(a[n].max < num)
a[n].max = num;//更新最大值
if(a[n].l == a[n].r)//左右邊距相等不再插入更新
return;
if(v <= (a[n].l + a[n].r) / 2)
Insert(n*2, v, num);//更新左孩子
else
Insert(n*2+1, v, num);//更新右孩子
}
void Change(int n, int v, int num)//為線段樹改變一個權值
{
if(v == a[n].l && v == a[n].r)//下標與左右範圍相等 ，存本數
{
a[n].sum = num;
a[n].max = num;
return;
}
int middle = (a[n].l + a[n].r) / 2;
if(v <= middle)
Change(n*2, v, num);//更改左孩子
else
Change(n*2+1, v, num);//更改右孩子
a[n].sum = a[n*2].sum + a[n*2+1].sum;//更新總和
a[n].max = Testmax(a[n*2].max,a[n*2+1].max);//更新最大值
}
int QSum(int n, int l, int r)//求一個範圍內的權值總和
{
if(l == a[n].l && r == a[n].r)//所求範圍與左右範圍相等 ，直接輸出總和
return a[n].sum;
int middle = (a[n].l + a[n].r) / 2;
if(r <= middle)
return QSum(n*2, l, r);//若所求範圍在左孩子範圍內，從左孩子尋找
else if(l > middle)
return QSum(n*2+1, l, r);//若所求範圍在右孩子範圍內，從右孩子尋找
else return QSum(n*2,l,middle) + QSum(n*2+1,middle+1,r);//若範圍在左右孩子之間，分別求總和
}
int QMax(int n, int l, int r)//計算b至c範圍內的最大權值
{
if(l == a[n].l && r == a[n].r)//所求範圍與左右範圍相等 ，直接輸出最大值
return a[n].max;
int middle = (a[n].l + a[n].r) / 2;
if(r <= middle)
return QMax(n*2, l, r);//若所求範圍在左孩子範圍內，從左孩子尋找
else if(l > middle)
return QMax(n*2+1, l, r);//若所求範圍在右孩子範圍內，從右孩子尋找
else
return Testmax(QMax(n*2, l, middle), QMax(n*2+1, middle+1, r));//若範圍在左右孩子之間，分別求最大值，然後求最終最大值
}
最後更新：2017-04-03 12:54:44