hdoj 1166
4657 단어 OJ
제목: 약.
사고방식: 기본 적 인 라인 트 리, 정적 트 리, 결점 업데이트, 정보 조회.코드 는 다음 과 같 습 니 다:
#include<iostream>
using namespace std;
const int Max = 50005;
struct data
{
int l, r, num;
}node[3*Max]; // 。
int num[Max];
void BuildTree(int left, int right, int u)
{ // 。
node[u].l = left;
node[u].r = right;
if(left == right)
node[u].num = num[left];
else
{
BuildTree(left, (left+right)/2, 2*u);
BuildTree((left+right)/2+1, right, 2*u+1);
node[u].num = node[2*u].num + node[2*u+1].num;
}
}
int updata(int camp, int w, int u)
{ // 。
node[u].num += w;
if(node[u].l == node[u].r)
return 0;
else
if(camp <= node[2*u].r)
updata(camp, w, 2*u);
else
updata(camp, w, 2*u+1);
return 0;
}
int query(int left, int right, int u)
{ // 。
if(node[u].l == left && node[u].r == right)
return node[u].num;
if(right <= node[2*u].r)
return query(left, right, 2*u);
if(left >= node[2*u+1].l)
return query(left, right, 2*u+1);
int a = query(left, (node[u].l+node[u].r)/2, 2*u);
int b = query((node[u].l+node[u].r)/2+1, right, 2*u+1);
return a + b;
}
int main()
{
int t, k, n;
scanf("%d", &t);
for(k = 1; k <= t; k ++)
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
scanf("%d", &num[i]);
BuildTree(1, n, 1);
printf("Case %d:
", k);
char str[10];
while(cin >> str && str[0] != 'E')
{
int a, b;
scanf("%d%d", &a, &b);
if(str[0] == 'A')
updata(a, b, 1);
else if(str[0] == 'S')
updata(a, -b, 1);
else
printf("%d
", query(a, b, 1));
}
}
return 0;
}
hdoj 1754 는 이 문제 와 유사 하고 정적 으로 나 무 를 만 들 며 노드 휴식 을 수정 하고 마지막 으로 조회 합 니 다.
코드 는 다음 과 같 습 니 다:
#include<iostream>
using namespace std;
const int Max = 200050;
struct data
{
int l, r, max;
}node[3*Max];
int score[Max];
int max(int a, int b)
{
return a > b ? a : b;
}
void BuildTree(int left, int right, int u)
{ // 。
node[u].l = left;
node[u].r = right;
if(left == right)
node[u].max = score[left];
else
{
BuildTree(left, (left+right)/2, 2*u);
BuildTree((left+right)/2+1, right, 2*u+1);
node[u].max = max(node[2*u].max, node[2*u+1].max);
}
}
void updata(int stu, int val, int u)
{ // 。
if(node[u].l == node[u].r)
{
node[u].max = val;
return;
}
if(stu <= node[2*u].r)
updata(stu, val, 2*u);
else
updata(stu, val, 2*u+1);
node[u].max = max(val, node[u].max);
}
int query(int left, int right, int u)
{ // 。
if(node[u].l == left && node[u].r == right)
return node[u].max;
if(right <= node[2*u].r)
return query(left, right, 2*u);
if(left >= node[2*u+1].l)
return query(left, right, 2*u+1);
int mid = (node[u].l + node[u].r) / 2;
return max(query(left, mid, 2*u), query(mid+1, right, 2*u+1));
}
int main()
{
int n, m;
while(scanf("%d%d", &n, &m) != EOF)
{
for(int i = 1; i <= n; i ++)
scanf("%d", &score[i]);
getchar(); // 。
BuildTree(1, n, 1);
while(m--)
{
int a, b;
char order;
scanf("%c%d%d", &order, &a, &b);
if(order == 'U')
updata(a, b, 1);
if(order == 'Q')
cout << query(a, b, 1) << endl;
getchar();
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
9도 OJ 1116: 가감승제(기초문제)시간 제한: 1초 메모리 제한: 32메가바이트 특수 판제: 아니요 제출: 1466 해결 방법: 902 제목 설명: 입력한 연산자에 따라 입력한 정수에 대해 간단한 정수 연산을 진행한다.연산자는 더하기 +, 빼기 -,...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.