HDU 1698 라인 트 리 세그먼트 업데이트
제목: T 조 의 데 이 터 를 드 리 겠 습 니 다. 각 조 의 N 개 수 는 처음에 1, M 개 작업 이 었 습 니 다. 각 작업 은 구간 a 에서 b 의 값 을 재 로 업데이트 하고 n 개 수의 합 을 물 었 습 니 다.
사고방식: 간단 한 라인 트 리 를 세그먼트 로 업데이트 하려 면 게 으 름 표 시 를 사용 해 야 한다. 게 으 름 표 시 는 사용 할 때 다시 업데이트 하 는 것 이다. 그렇지 않 으 면 거기에 두 어야 한다.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e5+10;
typedef long long ll;
#define mm(a) memset(a,0,sizeof(a))
int num[maxn<<2],num1[maxn<<2];
void pushup(int node){
num[node]=num[node<<1]+num[node<<1|1];
}
void pushdown(int node,int node1){
if(num1[node]){
int t=num1[node];
num1[node<<1]=t;
num1[node<<1|1]=t;
num[node<<1]=(node1-(node1>>1))*t;
num[node<<1|1]=(node1>>1)*t;
num1[node]=0;
}
}
void buildtree(int le,int ri,int node){
if(le==ri){
num[node]=1;
return ;
}
int t=(le+ri)>>1;
buildtree(le,t,node<<1);
buildtree(t+1,ri,node<<1|1);
pushup(node);
}
void update(int l,int r,int add,int le,int ri,int node){
if(l<=le&&ri<=r){
num1[node]=add;
num[node]=add*(ri-le+1);
return ;
}
pushdown(node,ri-le+1);
int t=(le+ri)>>1;
if(l<=t) update(l,r,add,le,t,node<<1);
if(r>t) update(l,r,add,t+1,ri,node<<1|1);
pushup(node);
}
int main(){
int T,t=1,n,m;
scanf("%d",&T);
while(T--){
mm(num1);
scanf("%d%d",&n,&m);
int a,b,c;
buildtree(1,n,1);
while(m--){
scanf("%d%d%d",&a,&b,&c);
update(a,b,c,1,n,1);
// for(int i=1;i<=4*n;i++)
// cout<<num[i]<<" ";
// cout<<endl;
}
printf("Case %d: The total value of the hook is %d.
",t++,num[1]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.