Attack
Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 1890 Accepted Submission(s): 554
Problem Description
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.
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.
Input
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 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
Output
For the ith case, output one line “Case i: ” at first. Then for each query, output one line containing one integer, the number of time the pth unit was successfully attacked when asked.
Sample Input
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
Sample Output
Case 1: 0 1 0 1 Case 2: 3 2
Source
Recommend
题意：
一个长度为n(最大20000)的墙。每单位长度有一个保护罩。每个保护罩可以抵挡一次攻击。但是要t的冷却时间才能抵挡下一次攻击。想在q组询问。攻击[L,R]。或询问某单位墙被成功攻击的次数。
一个长度为n(最大20000)的墙。每单位长度有一个保护罩。每个保护罩可以抵挡一次攻击。但是要t的冷却时间才能抵挡下一次攻击。想在q组询问。攻击[L,R]。或询问某单位墙被成功攻击的次数。
思路：
用树状数组维护墙被攻击的总次数。只涉及到区间加减一个值。和查询一个点值。这个有两种写法。然后一个墙被成功攻击的次数就等于总攻击次数-被抵挡的攻击次数。关于被抵挡的攻击次数的算法就近乎暴力了。。反正分析时间复杂度怎么都会超的。但是没出那样的数据而已。
详细见代码：
版本一
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
int C[maxn],n,attack[maxn][2],head[maxn],num[maxn];
int lowbit(int x)
{
return x&-x;
}
void update(int x,int d)
{
for(int i=x;i>0;i-=lowbit(i))
C[i]+=d;
}
int getsum(int x)
{
int i,sum=0;
for(i=x;i<=n;i+=lowbit(i))
sum+=C[i];
return sum;
}
int main()
{
int t,q,tm,i,j,ct,cas=1,a,b;
char cmd[20];
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&q,&tm);
for(i=1;i<=n;i++)
C[i]=num[i]=0,head[i]=0;
ct=0;
printf("Case %d:\n",cas++);
while(q--)
{
scanf("%s%d",cmd,&a);
if(cmd[0]=='A')
{
scanf("%d",&b);
attack[ct][0]=a;
attack[ct][1]=b;
ct++;
update(b,1);
update(a-1,-1);//和线段树类似.加个lazy。等要算的时候在顺着父亲累加上去。
}
else
{
for(j=head[a];j<ct;j++)
if(attack[j][0]<=a&&attack[j][1]>=a)
num[a]++,head[a]=j+tm,j+=tm-1;
printf("%d\n",getsum(a)-num[a]);
}
}
}
return 0;
}
版本二：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
int C[maxn],n,attack[maxn][2],head[maxn],num[maxn];
int lowbit(int x)
{
return x&-x;
}
void update(int x,int d)
{
for(int i=x;i<=n;i+=lowbit(i))
C[i]+=d;
}
int getsum(int x)
{
int i,sum=0;
for(i=x;i>0;i-=lowbit(i))
sum+=C[i];
return sum;
}
int main()
{
int t,q,tm,i,j,ct,cas=1,a,b;
char cmd[20];
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&q,&tm);
for(i=1;i<=n;i++)
C[i]=num[i]=head[i]=0;
ct=0;
printf("Case %d:\n",cas++);
while(q--)
{
scanf("%s%d",cmd,&a);
if(cmd[0]=='A')
{
scanf("%d",&b);
attack[ct][0]=a;
attack[ct][1]=b;
ct++;
update(a,1);//用打标记的方法。前缀和就是当前点的值。
update(b+1,-1);
}
else
{
for(j=head[a];j<ct;j++)
if(attack[j][0]<=a&&attack[j][1]>=a)
num[a]++,head[a]=j+tm,j+=tm-1;//因为j在for循环还要加1所以只能加tm-1
printf("%d\n",getsum(a)-num[a]);
}
}
}
return 0;
}