如题:
问题描述
有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。
我用的java,用线段树写的,结果还是时间超限,高手求解
代码如下:
/**
- 线段树,操作格子
- @author Administrator * */ class Node { int max,sum; int left,right; Node lNode,rNode; //构造方法 Node() { max = 0; sum = 0; lNode = null; rNode = null; }
}
public class Tree {
//创建树
public static Node createTree(int left,int right)
{
Node xNode = new Node();
xNode.left = left;
xNode.right = right;
if(left != right)
{
int mid = (left + right) / 2;
xNode.lNode = createTree(left,mid); //创建左子树
xNode.rNode = createTree(mid+1,right); //创建右子树
}
return xNode;
}
//为线段树赋权值
public static void insert(Node xNode,int point, int value)
{
xNode.sum += value;
xNode.max = value > xNode.max ? value:xNode.max;//修改经过的节点的值
if(xNode.left == xNode.right) //找到最终节点结束
return;
else
{
int mid = (xNode.left + xNode.right) / 2;
if(point <= mid)
insert(xNode.lNode,point,value); //向左修改
else
insert(xNode.rNode,point,value); //向右修改
}
return;
}
//操作1:修改格子权值
public static void revise(Node xNode,int point,int value)
{
if(xNode.left == point && xNode.right == point)
{
xNode.max = value;
xNode.sum = value;
return;
}
else
{
int mid = (xNode.left + xNode.right) / 2;
if(point <= mid)
revise(xNode.lNode,point,value); //递归入,寻找节点
else
revise(xNode.rNode,point,value);
xNode.sum = xNode.lNode.sum + xNode.rNode.sum; //递归出,从下往上修改和
xNode.max = xNode.lNode.max > xNode.rNode.max ?
xNode.lNode.max : xNode.rNode.max;
}
}
//操作2:求连续一段格子的权值和
public static int getSum(Node xNode,int left,int right)
{
if(xNode.left == left && xNode.right == right) //找到节点
return xNode.sum;
else
{
int mid = (xNode.left + xNode.right) / 2;
if(right <= mid) //向左子树搜索
return getSum(xNode.lNode,left,right);
else
if(left > mid) //向右子树搜索
return getSum(xNode.rNode,left,right);
else //左右子树分叉搜索,求和
return getSum(xNode.lNode,left,mid) + getSum(xNode.rNode,mid+1,right);
}
}
//操作3:求连续一段格子的最大值
public static int getMax(Node xNode,int left,int right)
{
if(xNode.left == left && xNode.right == right) //找到当前节点
return xNode.max;
else
{
int mid = (xNode.left + xNode.right) / 2;
if(right <= mid) //搜索左子树
return getMax(xNode.lNode,left,right);
else
if(left > mid) //搜索右子树
return getMax(xNode.rNode,left,right);
else //左右子树分叉搜索,取最大值
return getMax(xNode.lNode,left,mid) > getMax(xNode.rNode,mid + 1,right) ?
getMax(xNode.lNode,left,mid) : getMax(xNode.rNode,mid + 1,right);
}
}
public static void main(String[] args)
{
int m = 0,n = 0;
Node xNode = null;
java.util.Scanner cin = new java.util.Scanner(System.in);
n = cin.nextInt();
m = cin.nextInt();
xNode = createTree(1,n);
for(int i = 1;i<=n;i++)
{
int value = cin.nextInt();
insert(xNode,i,value);
}
while(m>0)
{
m--;
int p,x,y;
p = cin.nextInt();
x = cin.nextInt();
y = cin.nextInt();
switch(p)
{
case 1 : revise(xNode,x,y); break;
case 2 : System.out.println(getSum(xNode,x,y)); break;
case 3 : System.out.println(getMax(xNode,x,y)); break;
default: break;
}
}
cin.close();
return;
}
}