hdu 1698 WA 求助哇！！

答案:1 悬赏:20

解决时间 2021-01-20 09:53

提问者网友：沉默菋噵
2021-01-19 11:41

hdu 1698 WA 求助哇！！

最佳答案

二级知识专家网友：猎心人
2021-01-19 13:13

已ac，线段树去看胡浩的博客。。
#include
#include

struct Num
{
int flag;
int l, r, m, sum;
}num[400005];

void build( int l, int r, int rt )
{
num[rt].flag = 0;
num[rt].l = l, num[rt].r = r;
num[rt].m = ( l + r ) >> 1;
num[rt].sum = r - l + 1;
if( l == r )
{
return ;
}
build( l, num[rt].m, rt << 1 );
build( num[rt].m + 1, r, rt << 1|1 );
}

void updata( int x, int y, int value, int rt )
{
if( x <= num[rt].l && num[rt].r <= y )
{
num[rt].sum = value * ( num[rt].r - num[rt].l + 1 );
num[rt].flag = value;
return ;
}
if( num[rt].flag )
{
int rt2 = rt<<1;
num[rt2].flag = num[rt].flag;
num[rt2].sum = ( num[rt2].r - num[rt2].l + 1 ) * num[rt].flag;
num[rt2|1].flag = num[rt].flag;
num[rt2|1].sum = ( num[rt2|1].r - num[rt2|1].l + 1 ) * num[rt].flag;//！！！！！！！！！
num[rt].flag = 0;
}
if( x <= num[rt].m )
updata( x, y, value, rt << 1 );
if( y > num[rt].m )
updata( x, y, value, rt << 1|1 );
num[rt].sum = num[rt<<1].sum + num[rt<<1|1].sum;
}

void solve( int n, int m )
{
int i, x, y, value;
build( 1, n, 1 );
for( i = 0; i < m; i ++ )
{
scanf( "%d%d%d", &x, &y, &value );
updata( x, y, value, 1 );
}
return ;
}

int main( )
{
int n, m, t, nth = 1;
scanf( "%d", &t );
while( t -- )
{
scanf( "%d%d", &n, &m );
solve( n, m );
printf( "Case %d: The total value of the hook is %d.\n", nth++, num[1].sum );
}
return 0;
}

我要举报

如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！