首页 > ACM题库 > HDU-杭电 > HDU 4107-Gangster-线段树-[解题报告]HOJ
2015
04-16

HDU 4107-Gangster-线段树-[解题报告]HOJ

Gangster

问题描述 :

There are two groups of gangsters fighting with each other. The first group stands in a line, but the other group has a magic gun that can shoot a range [a, b], and everyone in that range will take a damage of c points. When a gangster is taking damage, if he has already taken at least P point of damage, then the damage will be doubled. You are required to calculate the damage that each gangster in the first group toke.
To simplify the problem, you are given an array A of length N and a magic number P. Initially, all the elements in this array are 0.
Now, you have to perform a sequence of operation. Each operation is represented as (a, b, c), which means: For each A[i] (a <= i <= b), if A[i] < P, then A[i] will be A[i] + c, else A[i] will be A[i] + c * 2.
Compute all the elements in this array when all the operations finish.

输入:

The input consists several testcases.
The first line contains three integers n, m, P (1 <= n, m, P <= 200000), denoting the size of the array, the number of operations and the magic number.
Next m lines represent the operations. Each operation consists of three integers a; b and c (1 <= a <= b <= n, 1 <= c <= 20).

输出:

The input consists several testcases.
The first line contains three integers n, m, P (1 <= n, m, P <= 200000), denoting the size of the array, the number of operations and the magic number.
Next m lines represent the operations. Each operation consists of three integers a; b and c (1 <= a <= b <= n, 1 <= c <= 20).

样例输入:

3 2 1
1 2 1
2 3 1

样例输出:

1 3 1

结点存当前区间伤害最小值,最大值,以及要加的伤害值。

更新到如果最小值大于等于P,或者最大值小于P为止。

时间卡很紧,一些不太注意的细节就会卡死 = =。。

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define FOR(i,s,t) for(int i=(s); i<(t); i++)
#define BUG puts("here!!!")
#define STOP system("pause")
#define file_r(x) freopen(x, "r", stdin)
#define file_w(x) freopen(x, "w", stdout)

using namespace std;

const int MAX = 200005;
struct Tnode{				// 一维线段树 
    int l, r, min, max, add;
    int len() { return r - l;}
    int mid() { return MID(l,r);}
    bool in(int ll,int rr) { return l >= ll && r <= rr; }
    void lr(int ll,int rr){ l = ll; r = rr;}
};
Tnode node[MAX<<2];
int P, n;
void Build(int t,int l,int r)
{
	node[t].lr(l,r);
	node[t].min = node[t].max = node[t].add = 0;
	if( node[t].len() == 1 )
		return ;
	int mid = MID(l,r);
	Build(L(t),l,mid);
	Build(R(t),mid,r);
}

void Updata_val(int t, int add)
{
	node[t].min += add;
	node[t].max += add;
}

void Updata_add(int t)
{
	if( node[t].add )
	{
		node[L(t)].add += node[t].add;
		Updata_val(L(t), node[t].add);
		node[R(t)].add += node[t].add;
		Updata_val(R(t), node[t].add);
		
		node[t].add = 0;
	}
}

void Updata(int t,int l,int r,int add)
{
	if( node[t].in(l,r) )
	{
		if( node[t].max < P )
		{
			node[t].add += add;
			Updata_val(t, add);
			return ;
		}
		else		
			if( node[t].min >= P )
			{
				node[t].add += add * 2;
				Updata_val(t, add * 2);
				return ;
			}
	}
	Updata_add(t);
	if( node[t].len() == 1 ) return ;
	int mid = node[t].mid();
	if( l < mid ) Updata(L(t),l,r,add);
	if( r > mid ) Updata(R(t),l,r,add);
	
	node[t].min = min(node[L(t)].min, node[R(t)].min);
	node[t].max = max(node[L(t)].max, node[R(t)].max);
}

void Query(int t)
{
	if( node[t].min == node[t].max )
	{
		FOR(i, node[t].l, node[t].r)
			printf(i == n-1 ? "%d\n" : "%d ", node[t].min);
		return ;
	}
	Updata_add(t);
	if( node[t].len() == 1 ) return ;
	int mid = node[t].mid();
	Query(L(t));
	Query(R(t));
}

int main()
{
	int m, x, y, val;
	
	while( ~scanf("%d%d%d", &n, &m, &P) )
	{
		Build(1, 0, n);
		while( m-- )
		{
			scanf("%d%d%d", &x, &y, &val);
			Updata(1, x-1, y, val);
		}
		Query(1);
	}

return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/zxy_snow/article/details/6919762


  1. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  2. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count