アルゴリズム練習-1
2370 ワード
#include<iostream>
#include<stdio.h>
using namespace std;
int sum;
int ans;
struct Tree
{
int a,b;
int sum;
int ans;
Tree *lchile,*rchile;
};
int swap(int x,int y)
{
if(x>y)
return x;
else
return y;
}
Tree *build(int l,int r)
{
Tree *root=new Tree;
root->a=l;
root->b=r;
root->sum=0;
root->ans=-1;
root->lchile=NULL;
root->rchile=NULL;
if(l<r)
{
int mid=(l+r)>>1;
root->lchile=build(l,mid);
root->rchile=build(mid+1,r);
}
return root;
}
void insert(Tree *root,int l,int k)
{
if((root->a==l)&&(root->b==l))
{
root->ans=k;
root->sum=k;
return ;
}
int mid=(root->a+root->b)>>1;
if(mid>=l)
{
insert(root->lchile,l,k);
}
else
{
insert(root->rchile,l,k);
}
root->sum=root->lchile->sum+root->rchile->sum;
root->ans=swap(root->lchile->ans,root->rchile->ans);
}
void search(Tree *root,int l,int r)
{
if(root->a>=l&&root->b<=r)
{
if(root->ans>ans)
ans=root->ans;
sum+=root->sum;
return ;
}
int mid=(root->a+root->b)>>1;
if(mid>=r)
{
search(root->lchile,l,r);
}
else if(mid<l)
{
search(root->rchile,l,r);
}
else
{
search(root->lchile,l,mid);
search(root->rchile,mid+1,r);
}
}
int main()
{
Tree *root=new Tree;
int n,m,i,s,c,b,t;
cin>>n>>m;
root=build(1,n);
for(i=1;i<=n;i++)
{
cin>>t;
insert(root,i,t);
}
for(i=1;i<=m;i++)
{
int ch;
cin>>ch;
if(ch==1)
{
cin>>s>>b;
insert(root,s,b);
}
else
{
sum=0;
ans=-1;
cin>>s>>b;
search(root,s,b);
if(ch==2)
cout<<sum<<endl;
if(ch==3)
cout<<ans<<endl;
}
}
return 0;
}