HDU ACM 4031 Attack (树状数组--单点查询+区间更新)

 

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

 用了树状数组的区间更新 单点查找（一般为单点更新 区间查找）

例如 区间（2,4）加1

则Updata(2,1)   Updata(4+1,-1)

实现了更新（2,4）的值而不改变其他值

求Sum时即可得到某一点的值

 

 

 

 

View Code #include <iostream> using namespace std; const int MAX = 20000 + 100; int C[MAX]; int N; struct Node {int l;int r; }; int LowBit(int x) {return x & (-x); } void Update(int num,int key) {while(num <= N){C[num] += key;num += LowBit(num);} }int CalSum(int num) {int sum = 0;while(num > 0){sum += C[num];num -= LowBit(num);}return sum; } int main() {int T;cin>>T;int Case = 0;while(T--){int Q;//操作数量int CD;//护盾冷却时间int time = 0;//当前经过时间int used_time[MAX] = {0};//记录护盾什么时候进入冷却int porected[MAX] = {0};//记录保护次数Node attack[MAX] = {0};//定义结构体,记录攻击的位置memset(C,0,sizeof(C));Case++;cout<<"Case "<<Case<<":"<<endl;scanf("%d%d%d",&N,&Q,&CD);int i;for(i=0;i<Q;i++){char str[20];scanf("%s",str);if(str[0] == 'A'){scanf("%d%d",&attack[time].l,&attack[time].r);Update(attack[time].l,1);Update(attack[time].r+1,-1);time++;}else{int num;scanf("%d",&num);int i;for(i = used_time[num] ; i< time ;i++)//每一次询问计算被保护的次数 {if(attack[i].l <=num && num <= attack[i].r ){porected[num]++;used_time[num] = i + CD;i = i + CD - 1;}}printf("%d\n",CalSum(num)-porected[num]);//成功攻击次数= 总攻击数 - 被保护次数 }}}return 0; }

 

 

转载于:https://www.cnblogs.com/zxotl/archive/2012/11/10/2764340.html

总结

以上是生活随笔为你收集整理的HDU ACM 4031 Attack (树状数组--单点查询+区间更新)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。