HDU 1698 Just a Hook 세그먼트 트리
#include <cstring>
#include <iostream>
using namespace std;
#define L(u) ( u << 1 )
#define R(u) ( u << 1 | 1 )
#define N 100005
struct item { int l, r, v, kind; } node[N*3];
void build ( int u, int l, int r )
{
node[u].l = l;
node[u].r = r;
node[u].v = r - l + 1;
node[u].kind = 1;
if ( l == r ) return;
int mid = ( l + r ) >> 1;
build ( L(u), l, mid );
build ( R(u), mid + 1, r );
}
void update ( int u, int l, int r, int val )
{
if ( node[u].kind == val ) return; //
if ( l <= node[u].l && node[u].r <= r )
{
node[u].v = ( node[u].r - node[u].l + 1 ) * val;
node[u].kind = val;
return;
}
if ( node[u].kind != 0 )
{
node[L(u)].kind = node[u].kind;
node[L(u)].v = ( node[L(u)].r - node[L(u)].l + 1 ) * node[L(u)].kind;
node[R(u)].kind = node[u].kind;
node[R(u)].v = ( node[R(u)].r - node[R(u)].l + 1 ) * node[R(u)].kind;
node[u].kind = 0;
}
int mid = ( node[u].l + node[u].r ) >> 1;
if ( r <= mid )
update ( L(u), l, r, val );
else if ( l > mid )
update ( R(u), l, r, val );
else
{
update ( L(u), l, mid, val );
update ( R(u), mid+1, r, val );
}
node[u].v = node[L(u)].v + node[R(u)].v;
}
int main()
{
int t, n, q, l, r, kind;
scanf("%d",&t);
for ( int i = 1; i <= t; i++ )
{
scanf("%d",&n);
build ( 1, 1, n );
scanf("%d",&q);
while ( q-- )
{
scanf("%d%d%d",&l,&r,&kind);
update ( 1, l, r, kind );
}
printf("Case %d: The total value of the hook is %d.
", i, node[1].v );
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Ruby의 구조체 클래스은 접근자 메서드가 있는 속성 모음입니다. 클래스를 명시적으로 작성할 필요 없이. Struct 클래스는 구성원 및 해당 값 집합을 포함하는 새 하위 클래스를 생성합니다. 각 멤버에 대해 #attr_accessor 와...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.