首页 > ACM题库 > HDU-杭电 > HDU 4031-Attack-线段树-[解题报告]HOJ
2015
04-15

HDU 4031-Attack-线段树-[解题报告]HOJ

Attack

问题描述 :

Today is the 10th Annual of “September 11 attacks”, the Al Qaeda is about to attack American again. However, American is protected by a high wall this time, which can be treating as a segment with length N. Al Qaeda has a super weapon, every second it can attack a continuous range of the wall. American deployed N energy shield. Each one defends one unit length of the wall. However, after the shield defends one attack, it needs t seconds to cool down. If the shield defends an attack at kth second, it can’t defend any attack between (k+1)th second and (k+t-1)th second, inclusive. The shield will defend automatically when it is under attack if it is ready.

During the war, it is very important to understand the situation of both self and the enemy. So the commanders of American want to know how much time some part of the wall is successfully attacked. Successfully attacked means that the attack is not defended by the shield.

输入:

The beginning of the data is an integer T (T ≤ 20), the number of test case.
The first line of each test case is three integers, N, Q, t, the length of the wall, the number of attacks and queries, and the time each shield needs to cool down.
The next Q lines each describe one attack or one query. It may be one of the following formats
1. Attack si ti
  Al Qaeda attack the wall from si to ti, inclusive. 1 ≤ si ≤ ti ≤ N
2. Query p
  How many times the pth unit have been successfully attacked. 1 ≤ p ≤ N
The kth attack happened at the kth second. Queries don’t take time.
1 ≤ N, Q ≤ 20000
1 ≤ t ≤ 50

输出:

The beginning of the data is an integer T (T ≤ 20), the number of test case.
The first line of each test case is three integers, N, Q, t, the length of the wall, the number of attacks and queries, and the time each shield needs to cool down.
The next Q lines each describe one attack or one query. It may be one of the following formats
1. Attack si ti
  Al Qaeda attack the wall from si to ti, inclusive. 1 ≤ si ≤ ti ≤ N
2. Query p
  How many times the pth unit have been successfully attacked. 1 ≤ p ≤ N
The kth attack happened at the kth second. Queries don’t take time.
1 ≤ N, Q ≤ 20000
1 ≤ t ≤ 50

样例输入:

2
3 7 2
Attack 1 2
Query 2
Attack 2 3
Query 2
Attack 1 3
Query 1
Query 3
9 7 3
Attack 5 5
Attack 4 6
Attack 3 7
Attack 2 8
Attack 1 9
Query 5
Query 3

样例输出:

Case 1:
0
1
0
1
Case 2:
3
2

/*
分析:
    线段树。
    在复习树状数组找到了这题,不过我怎么看都是用
线段树更好呀-、-I。
    一开始想要在线段树里加信息,然后直接读出所求
的时间,不过怎么加都挺别扭的。于是就参考下别人怎
么弄的,原来都用的暴力呀-、-I。
    ans[i]=i被攻击的次数-i被保护的次数。用线段树
记录并查找i被攻击的次数,同时用另一数组attack记录
下每次的攻击,在询问i的时候,暴力遍历attack来确定
i被保护的次数,从而得到ans[i]。(当然,遍历也不是
完全暴力,记录元素这次遍历结束的位置从而方便此元
素下次的遍历)。

                                        2012-10-18
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
int n,q,t;
struct SegTree
{
	int l,r,mid;
	int ts;
}T[80011];
int attack_l[20011],attack_r[20011],tot;
int next[20011],pro[20011];
void build(int l,int r,int k)
{
	T[k].l=l;
	T[k].r=r;
	T[k].mid=(l+r)>>1;
	T[k].ts=0;
	if(l==r)	return ;
	build(l,T[k].mid,2*k);
	build(T[k].mid+1,r,2*k+1);
}
void update(int l,int r,int k)
{
	if(T[k].l==l && T[k].r==r)	{T[k].ts++;return ;}
	if(r<=T[k].mid)		update(l,r,2*k);
	else if(l>T[k].mid)	update(l,r,2*k+1);
	else
	{
		update(l,T[k].mid,2*k);
		update(T[k].mid+1,r,2*k+1);
	}
}
int find(int d,int k)
{
	int sum=0;
	if(T[k].l==T[k].r && T[k].l==d)	return T[k].ts;
	if(T[k].l<=d && d<=T[k].r)
	{
		sum+=T[k].ts;
		if(d<=T[k].mid)	sum+=find(d,2*k);
		else			sum+=find(d,2*k+1);
		return sum;
	}
	else return 0;
}
int main()
{
	int T,Case;
	int j;
	char str[11];
	int a,b;
	int temp;
	scanf("%d",&T);
	for(Case=1;Case<=T;Case++)
	{
		scanf("%d%d%d",&n,&q,&t);
		build(1,n,1);
		printf("Case %d:\n",Case);
		memset(pro,0,sizeof(pro));
		memset(next,0,sizeof(next));
		tot=0;
		while(q--)
		{
			scanf("%s",str);
			if(str[0]=='A')
			{
				scanf("%d%d",&a,&b);
				update(a,b,1);
				attack_l[tot]=a;
				attack_r[tot++]=b;
			}
			else
			{
				scanf("%d",&a);
				j=next[a];
				while(j<tot)
				{
					if(attack_l[j]<=a && a<=attack_r[j])
					{
						pro[a]++;
						j+=t;
					}
					else j++;
				}
				next[a]=j;
				temp=find(a,1);
				printf("%d\n",temp-pro[a]);
			}
		}
	}
	return 0;
}

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

参考:http://blog.csdn.net/ice_crazy/article/details/8087234


  1. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  3. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n