HDU 4031 Attack(树状数组)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了HDU 4031 Attack(树状数组),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3617字,纯文字阅读大概需要6分钟。
内容图文
![HDU 4031 Attack(树状数组)](/upload/InfoBanner/zyjiaocheng/1050/1ae8e1d9fc8e4e9f8a3a23cfbf67a4ee.jpg)
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 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
美国建立了一套新的防御系统。每个点都可以进行自动防御,但是防御过后该点的防御
需要一段冷却时间,也就是说在此期间不能再进行防御。现在又两种操作:1.恐怖分子
每次会对一段范围进行攻击。2.指挥官询问某点被攻击的次数
BIT做法:我们知道由于询问不费时间,所以我们考虑设计一个数组tt[i]记录i点可以
进行防御的时间,当时间t>=tt[i]的时候表示攻击可以被防御。那么被攻击的次数=
总的攻击次数-防御次数。
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<string> #include<iostream> #include<queue> #include<cmath> #include<map> #include<stack> #include<bitset> using namespace std; #define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define REP( i , n ) for ( int i = 0 ; i < n ; ++ i ) #define CLEAR( a , x ) memset ( a , x , sizeof a ) typedef long long LL; const int maxn = 20005; int N,Q,T,t; int c[maxn],d[maxn],tt[maxn];//tt[i]记录某点可以进行防御的时间,大于这个时间都可以进行防御; struct node//d[i]记录某点成功防御次数 { int l,r; }e[maxn]; int lowbit(int x) { return x&(-x); } void update(int x,int w) { while(x<maxn) { c[x]+=w; x+=lowbit(x); } } int query(int x) { int s=0; while(x>0) { s+=c[x]; x-=lowbit(x); } return s; } int main() { int cas=1; int pos,l,r; char str[5]; scanf("%d",&t); while(t--) { int cnt=0; CLEAR(c,0); CLEAR(tt,0); CLEAR(d,0); scanf("%d%d%d",&N,&Q,&T); printf("Case %d:\n",cas++); while(Q--) { scanf("%s",str); if(str[0]=='A') { scanf("%d%d",&l,&r); e[cnt].l=l; e[cnt++].r=r; update(l,1); update(r+1,-1); } else { scanf("%d",&pos); for(int i=tt[pos];i<cnt;i++)//记录某点可以进行防御的时间,大于等于该时间的攻击都可以自动进行防御 { if(pos>=e[i].l&&pos<=e[i].r) { d[pos]++; tt[pos]=i+T; i+=T-1; } } printf("%d\n",query(pos)-d[pos]); } } } return 0; }
原文:http://blog.csdn.net/u013582254/article/details/42226905
内容总结
以上是互联网集市为您收集整理的HDU 4031 Attack(树状数组)全部内容,希望文章能够帮你解决HDU 4031 Attack(树状数组)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。