데이터 구조 & 알고리즘 학습 노트: 선분 트 리
29116 단어 선분 수알고리즘 학습 노트
#define lson rt<<1, left, m
#define rson rt<<1|1, m + 1, right
const int maxn = 1e5+5;
using namespace std;
struct Node
{
int value;
int left,right;
int mid()
{
return (left + right) >> 1;
}
}node[maxn<<2];
int lindex[maxn];//
void PushUp(int rt)
{
node[rt].value = node[rt<<1].value + node[rt<<1|1].value;
//node[rt].value = max(node[rt<<1].value, node[rt<<1|1].value);
}
void BuildTree(int rt, int left, int right)
{
node[rt].left = left;
node[rt].right = right;
node[rt].value = 0;
if(left == right)
{
scanf("%d",&node[rt].value);
lindex[left] = rt;
return ;
}
int m = node[rt].mid();
BuildTree(lson);
BuildTree(rson);
PushUp(rt);
}
void Update(int rt)
{
if(rt == 1)return ;
int f = rt >> 1;
int a = node[f<<1].value;
int b = node[f<<1|1].value;
node[f].value = a + b;//
//node[f].value = max(a,b);//
Update(f);
}
int ans;
void Query(int rt, int left, int right)
{
if(node[rt].left == left && node[rt].right == right)
{
ans += node[rt].value;//
//ans = max(ans, node[rt].value);//
return ;
}
int m = node[rt].mid();
if(right <= m) Query(rt<<1, left, right);
else if(left > m) Query(rt<<1|1, left, right);
else{
Query(lson);
Query(rson);
}
}연습 문제 연습 HDU 1754 (전송 문) I Hate It Time Limit: 9000 / 3000 MS (Java / Others) Memory Limit: 32768 / 32768 K (Java / Others) Problem 많은 학교 에서 비교 하 는 습관 이 유행 하고 있다.선생님 들 은 모모 에서 모모 까지 점수 가 가장 높 은 것 이 얼마 인지 묻 는 것 을 좋아한다.이것 은 많은 학생 들 로 하여 금 매우 반감 을 가지 게 한다.네가 좋아 하 든 안 좋아 하 든 지금 네가 해 야 할 일 은 바로 선생님 의 요구 에 따라 프로그램 을 써 서 선생님 의 질문 을 모 의 하 는 것 이다.물론 선생님 은 어떤 학우 의 성적 을 갱신 해 야 할 때 가 있다.Input 이 문 제 는 여러 그룹 테스트 를 포함 하고 있 습 니 다. 파일 이 끝 날 때 까지 처리 하 십시오.각 테스트 의 첫 줄 에는 두 개의 정수 N 과 M (0 < N < = 20000, 0 < M < 5000) 이 있 는데 각각 학생 의 수량 과 조작 수량 을 대표 한다.학생 ID 번 호 는 각각 1 번 에서 N 번 으로 매 겨 진다.두 번 째 줄 은 N 개의 정 수 를 포함 하고 이 N 명의 학생 들 의 초기 성적 을 대표 하 며 그 중에서 i 의 수 는 ID 가 i 인 학생 들 의 성적 을 대표 한다.다음은 M 줄.줄 마다 하나의 문자 C ('Q' 또는 'U' 만 가 져 오기) 와 두 개의 정수 A, B 가 있 습 니 다.C 가 'Q' 일 때 이것 은 질문 조작 이 라 고 표시 했다. ID 가 A 에서 B (A, B 포함) 까지 의 학생 중에서 성적 이 가장 높 은 것 은 얼마 인지 물 었 다.C 가 'U' 일 때 이것 은 업데이트 작업 이 라 고 표시 하고 ID 가 A 인 학생 의 성적 을 B 로 변경 하 라 고 요구 했다.Output 은 매번 문의 작업 에 대해 한 줄 에서 최고 성적 을 출력 합 니 다.Sample Input 5 6 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 2 9 Q 1 5 Sample Output 5 6 5 9
Hint Huge input,the C function scanf() will work better than cin
#includeelse
{
if(s[0] == 'U')
{
node[lindex[a]].value = b;
Update(lindex[a]);
}
}
}
}
return 0;
}
NYOJ 116 (전송 문) 병사 의 적 을 죽 이 는 시간 제한: 1000 ms | 메모리 제한: 65535 KB 난이도: 5 남장 군 수하 에 N 명의 병사 가 있 는데 각각 1 번 에서 N 번 으로 번 호 를 매 겼 다. 이 병사 들 의 적 을 죽 이 는 수 는 모두 알려 져 있다.
막노동 자 는 남 장군 수하 의 군사 입 니 다. 남 장군 은 항상 m 번 부터 n 번 까지 병사 의 총 살 적 수 를 알 고 싶 어 합 니 다. 막노동 자 를 도와 남 장군 에 게 대답 해 주세요.
남 장군 의 한 질문 이후 병사 i 는 또 적 q 명 을 죽 일 수 있 습 니 다. 이후 남 장군 이 다시 물 었 을 때 추가 적 인 적 수 를 고려 해 야 합 니 다.
입력 한 테스트 데이터 의 첫 줄 은 두 개의 정수 N, M 입 니 다. 그 중에서 N 은 병사 의 개 수 를 표시 합 니 다 (1 < N < 1000000). M 은 명령 의 개 수 를 표시 합 니 다.(1 < M < 100000) 다음 줄 은 N 개의 정수 이 고 ai 는 제 i 호 병사 의 적 을 죽 이 는 수 를 나타 낸다.(0 < = ai < = 100) 다음 M 줄 은 각각 하나의 명령 입 니 다. 이 명령 은 하나의 문자열 과 두 개의 정 수 를 포함 하고 있 습 니 다. 먼저 하나의 문자열 입 니 다. 문자열 QUERY 라면 남 장군 이 조회 작업 을 했 고 뒤의 두 개의 정수 m, n 은 조회 의 시작 과 끝 병사 번 호 를 표시 합 니 다.문자열 ADD 라면 뒤 를 따 르 는 두 정수 I, A (1 < = I < = N, 1 < = A < = 100) 는 제 I 병사 의 신규 살 적 수 를 A 로 표시 합 니 다.각 그룹의 출력 이 한 줄 을 차지 하 는 샘플 입력 5 6 1 2 3 4 5 QUERY 1 3 ADD 1 2 QUERY 1 3 ADD 2 3 QUERY 1 2 QUERY 1 5 샘플 출력 6 8 20
#includeelse{
if(s[0] == 'A')
{
node[lindex[a]].value += b;
Update(lindex[a]);
}
}
}
}
return 0;
}
HDU 1166 (전송 문) 은 상기 제목 과 유사 하 다.
// 【a,b】 c
#define lson rt<<1, left, m
#define rson rt<<1|1, m + 1, right
#define maxn 100004
using namespace std;
struct Node{
int left, right;
int value;
int add;//lazy
int mid()
{
return (left + right) >> 1;
}
}node[maxn<<2];
void PushUp(int rt)
{
node[rt].value = node[rt<<1].value + node[rt<<1|1].value;
}
void BuildTree(int rt, int left, int right)
{
node[rt].left = left;
node[rt].right = right;
node[rt].add = 0;
if(left == right)
{
scanf("%d",&node[rt].value);
return ;
}
int m = node[rt].mid();
BuildTree(lson);
BuildTree(rson);
PushUp(rt);
}
void PushDown(int rt, int len)// lazy
{//len
if(node[rt].add)
{
node[rt<<1].add += node[rt].add;
node[rt<<1|1].add += node[rt].add;
node[rt<<1].value += node[rt].add * (len - (len >> 1));//len - (len >> 1)
node[rt<<1|1].value += node[rt].add * (len >> 1);//len>>1
node[rt].add = 0;
}
}
void Update(int rt, int left, int right, int c)
{
if(node[rt].left == left && node[rt].right == right)
{
node[rt].value += (right - left + 1) * c;
node[rt].add += c;
return ;
}
PushDown(rt, node[rt].right - node[rt].left + 1);
int m = node[rt].mid();
if(right <= m)Update(rt<<1,left,right, c);
else if(left > m)Update(rt<<1|1,left,right, c);
else {
Update(lson, c);
Update(rson, c);
}
PushUp(rt);
}
void Query(int rt, int left, int right)
{
if(node[rt].left == left && node[rt].right == right)
{
ans += node[rt].value;
return ;
}
PushDown(rt, node[rt].right - node[rt].left + 1);
int m = node[rt].mid();
if(right <= m) Query(rt<<1,left,right);
else if(left > m) Query(rt<<1|1,left,right);
else{
Query(lson);
Query(rson);
}
}연습 문제 Poj 3468 (전송 문) Integers 와 간단 한 문제 시간 제한: 5000 MS 메모리 제한: 131072 K 케이스 시간 제한: 2000 MS 설명
You have N integers, A1, A2, … , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000. The second line contains N numbers, the initial values of A1, A2, … , AN. -1000000000 ≤ Ai ≤ 1000000000. Each of the next Q lines represents an operation. “C a b c” means adding c to each of Aa, Aa+1, … , Ab. -10000 ≤ c ≤ 10000. “Q a b” means querying the sum of Aa, Aa+1, … , Ab.
Output
You need to answer all Q commands in order. One answer in a line.
Sample Input
10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4 Sample Output
4 55 9 15 Hint
The sums may exceed the range of 32-bit integers.
#include
",ans);
}
else
{
scanf("%d%d%I64d",&a,&b,&c);
Update(1,a,b,c);
}
}
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU - 1166 - 적병 포진 (나무형 수조 또는 선분 수)C 국 의 앙 숙 A 국 은 그동안 군사훈련 을 하고 있 었 기 때문에 C 국 간첩 두목 인 데 릭 과 그의 수하 인 티 디 는 또 바 빠 지기 시작 했다.A 국 가 는 해안선 을 따라 직선 으로 N 개 공병 캠프 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
