[セグメントツリー]スコアの変更
3021 ワード
タイトルの説明
複数のテストのセットが含まれています.ファイルが終了するまで処理してください.各試験の第1行目には、2つの正の整数N(0
入力
タイトルの説明を参照
しゅつりょく
該当する質問を出力します.
サンプル入力
5 61 2 3 4 5Q 1 5U 3 6Q 3 4Q 4 5U 2 9Q 1 5
サンプル出力
5659
ACM週間訓練中の線分木の問題は、このような問題の明らかな特徴の一つはデータが非常に大きいことであり、大きなデータを考慮しなければ、簡単な循環と配列を使うだけで解決できるが、データの膨大さのため、線分木の優位性が明らかになる.
#include <cstdio>
#include <cmath>
#include <iostream>
const int MAXNODE=1000000;
const int MAX=1000000;
using namespace std;
struct NODE
{
int value;
int left,right;
}node[MAXNODE];
int father[MAX]={0};
void Buildtree(int i,int left,int right)
{
node[i].left=left;
node[i].right=right;
node[i].value=0;
if(left==right){
father[left]=i;
return;
}
Buildtree(i<<1,left,(left+right)/2);
Buildtree((i<<1)+1,(left+right)/2+1,right);
}
void Updatatree(int ri)
{
if(ri<=1) return;
int fi=ri/2;
int x1=fi*2,x2=fi*2+1;
int a=node[x1].value;
int b=node[x2].value;
node[fi].value=(a>b?a:b);
Updatatree(ri/2);
}
int Max=-(1<<20);
void Query(int i,int l,int r)
{
if(node[i].left==l&&node[i].right==r){
Max=(Max<node[i].value?node[i].value:Max);
return;
}
i=i<<1;
if(l<=node[i].right){
if(r<=node[i].right)
Query(i,l,r);
else Query(i,l,node[i].right);
}
i+=1;
if(r>=node[i].left){
if(l>=node[i].left)
Query(i,l,r);
else Query(i,node[i].left,r);
}
}
int main()
{
int m,n;
int x;
while(scanf("%d%d",&n,&m)!=EOF){
Buildtree(1,1,n);
for(int i=1;i<=n;++i)
{
scanf("%d",&x);
node[father[i]].value=x;
Updatatree(father[i]);
}
char o;
int A,B;
while(m--)
{
cin>>o>>A>>B;
if(A==0) A=1;
if(o=='Q')
{
Max=-(1<<20);
Query(1,A,B);
printf("%d
",Max);
}
else if(o=='U')
{
node[father[A]].value=B;
Updatatree(father[A]);
}
}
}
return 0;
}