HDU 4031 Attack（11年成都 线段树）

转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove

题目：每个位置有一个防御塔，每次敌人会对一个区间进行攻击。防御塔有一个冷却时间t。问某个时间时，某个位置被成功攻击的次数（没有被防御）

http://acm.hdu.edu.cn/showproblem.php?pid=4031

看上去有点复杂，需要维护某个位置上一次防御的时间。然后判断是否在冷却期

对于这种提问，可以从反面来考虑。

考虑某个位置被攻击的次数（包括防御的）-- 某个位置被防御的次数

第一部分可以用线段树，区间更新，点查询来实现。

对于第二部分，看上去有点暴力。从上一次统计的位置开始，枚举之后所有的区间，

#include<iostream>#include<cstdio>#include<map>#include<cstring>#include<cmath>#include<vector>#include<queue>#include<algorithm>#include<set>#define inf 110000#define M 10005#define N 200005#define Min(a,b) ((a)<(b)?(a):(b))#define Max(a,b) ((a)>(b)?(a):(b))#define pb(a) push_back(a)#define mem(a,b) memset(a,b,sizeof(a))#define eps 1e-9#define zero(a) fabs(a)<eps#define LL long long#define lson (step<<1)#define rson (step<<1|1)#define MOD 1000000007using namespace std;struct Node{int left,right,mid;int sum;}L[N*4];struct Attack{int left,right;Attack(){}Attack(int a,int b){left=a;right=b;}}att[N];int n,q,t,tot,cnt[N],pos[N];void Bulid(int step,int l,int r){L[step].left=l;L[step].right=r;L[step].mid=(l+r)/2;L[step].sum=0;if(l==r) return;Bulid(lson,l,L[step].mid);Bulid(rson,L[step].mid+1,r);}void Push_Down(int step){if(L[step].sum){L[lson].sum+=L[step].sum;L[rson].sum+=L[step].sum;L[step].sum=0;}}void Update(int step,int l,int r){if(L[step].left==l&&L[step].right==r){L[step].sum++;return;}Push_Down(step);if(r<=L[step].mid) Update(lson,l,r);else if(l>L[step].mid) Update(rson,l,r);else{Update(lson,l,L[step].mid);Update(rson,L[step].mid+1,r);}}int Query(int step,int pos){if(L[step].left==L[step].right)return L[step].sum;Push_Down(step);if(pos<=L[step].mid) return Query(lson,pos);else Query(rson,pos);}int main(){int T,cas=0;scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&q,&t);Bulid(1,1,n);tot=0;mem(cnt,0);mem(pos,0);printf("Case %d:\n",++cas);while(q--){char str[10];int l,r;scanf("%s",str);if(str[0]=='A'){scanf("%d%d",&l,&r);Update(1,l,r);att[tot++]=Attack(l,r);}else{scanf("%d",&l);if(t==1){puts("0");continue;}for(int i=pos[l];i<tot;i++){if(l>=att[i].left&&l<=att[i].right){cnt[l]++;pos[l]=i+t;i+=t-1;}}printf("%d\n",Query(1,l)-cnt[l]);}}}return 0;}