HDU 1698 Just a Hook線分樹
标题:1本の長い鎖の上にフックがたくさんあり、一次番号1-n、各フックには金銀銅の3種類の材質(3,2,1)があり、最初は銅質だったと仮定し、操作のたびにx-yの範囲内のフックをz材質に変えることができる.最後のチェーン全体の値を求めます.問題解:lazyタグ
#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;
}