Leyni
Time Limit: 3000 MS Memory Limit: 65536 K
Total Submit: 260(59 users) Total Accepted: 80(55 users) Rating: Special Judge: No
Description
Leyni被人掳走，身在水深火热之中...
小奈叶为了拯救Leyni，独自一人前往森林深处从静竹手中夺回昏迷中的Leyni。
历经千辛万苦，小奈叶救出了Leyni，但是静竹为此极为恼怒，决定对他们发起最强烈的进攻。
不过小奈叶有一个叫做能量保护圈的道具，可以保护他们。
这个保护圈由n个小的小护盾围成一圈，从1到n编号。当某一块小护盾受到攻击的时候，小护盾就会抵消掉这次攻击，也就是说对这一块小护盾的攻击是无效攻击，从而保护圈里的人，不过小护盾在遭到一次攻击后，需要t秒进行冷却，在冷却期间受到的攻击都是有效攻击,此时他们就会遭到攻击， 即假设1秒时受到攻击并成功防御，到1+t秒时冷却才结束并能进行防御，在2到t受到的都是有效攻击。
现在小奈叶专心战斗，Leyni昏迷，他们无法得知小护盾遭受的有效攻击次数，他们需要你的帮助。
只要能帮到他们，Leyni就会赠送出一份小奈叶写真集。
Input
第一行是一个整数T，表示有多少组测试数据。
第一行是三个整数，n,q,t，n表示保护圈的长度，q表示攻击的询问的总次数，t表示能量盾的冷却时间。
接下来的q行，每行表示受到的攻击或者她询问某范围内的能量盾被攻击的次数。
攻击：
Attack a
表示编号为a的小护盾受到一次攻击， 保证 1 <= a <= n
询问：
Query a b
表示询问编号从a到b的小护盾(包括a和b)总共受到了多少次有效攻击。保证 1<=a,b<=n
第k次攻击发生在第k秒，询问不花费时间。
1 <= n,q <=100000
1 <= t <= 50。
Output
每一组测试数据，先输出一行"Case i:",i表示第i组测试数据，从1开始计数。
之后对于每一个询问，输出该范围内的小护盾受到的有效攻击次数，一个询问一行。
Sample Input
1
4 7 3
Attack 1
Attack 1
Attack 1
Attack 2
Attack 2
Query 1 4
Query 1 1
Sample Output
Case 1:
3
2
Author
黄李龙
树状数组练习。
一开始想着用cd[]数组记录攻击数，每一次攻击都cd[a]-- 一次。后来发现这样每一次都要把整个数组循环一遍，会超时。就看了别人的代码，发现不用这么麻烦。不断计数攻击次数，如果防御时受到攻击(cd[a]+t<=cnt)，就把这块盾牌的cd时间=当前攻击次数(cd[a]=cnt)。
代码：
#include <stdio.h>
#include <iostream>
using namespace std;
int lowbit(int x)
{
return x & -x;
}
int sum(int a[],int x) //求出第x个元素之前的和
{
int ans = ;
while(x>){
ans+=a[x];
x -= lowbit(x); //向左上爬
}
return ans;
}
void add(int a[],int x,int d,int n) //将编号为x的数加d
{
while(x<=n){
a[x]+=d;
x+=lowbit(x);
}
}
int main()
{
int i,j,T,n,q,t,Case;
scanf("%d",&T);
for(Case=;Case<=T;Case++){
scanf("%d%d%d",&n,&q,&t);
printf("Case %d:\n",Case);
char str[];
int c[]={}; //有效攻击次数
int cd[]={}; //冷却时间
for(i=;i<=n;i++) //初始化cd[]数组
cd[i]=-t;
int cnt = ;
for(j=;j<=q;j++){
scanf("%s",str);
if(str[]=='A'){ //攻击
cnt++;
int a;
scanf("%d",&a);
if(cd[a]+t<=cnt){ //防御中
cd[a] = cnt;
}
else { //冷却中
add(c,a,,n);
}
}
else if(str[]=='Q'){ //询问
int a,b;
if(a>b){
int tt = a;
a=b;b=tt;
}
scanf("%d%d",&a,&b);
printf("%d\n",sum(c,b)-sum(c,a-));
}
}
}
return ;
}
Freecode : www.cnblogs.com/yym2013