ZQ的杀龙之旅（2）【线段树+树状数组】

ZQ的杀龙之旅（2）【线段树+树状数组】

  能讲懂这道题才算是会解了这道题——题记。

题面：题目链接

Description 

    ZQ在你的帮助下集齐了宝剑，经历重重的困难，终于到达了黑龙的洞穴，ZQ突然发现，宝剑发出耀眼的光芒，ZQ震惊了，他回忆起他们家族所传承下的一个责任，每隔一千年，他们家族就要对黑龙进行封印。每当天命者手持宝剑抵达命运之地，天赐者便会降临世间，封印黑龙。

    ZQ想到这里，他的身旁突然出现了，一排身穿黑色盔甲的骑士手持长枪，向黑龙的封印之地前进。黑龙的双眼逐渐睁开，那双金黄的双眼发出诡异的光芒，它发出吼~~的叫声，这时洞穴涌现出一大波强大的怪物向这骑士的位置冲去。

    nn个骑士从左到右依次位于 1−n1−n 号位置, 每个骑士有一个HPHP值和KK值，HPHP代表血量（每个骑士的HPHP和KK不一定相同），KK值代表伤害值。第ii分钟会有一个怪物从第11个骑士走到第nn个骑士，他会对路径上的骑士造成aiai的伤害，第jj个骑士也会对怪物造成KjKj的伤害（血量小于等于00即为死亡，死亡的怪物不会对骑士造成伤害，死亡的骑士也不会对怪物造成伤害），由于骑士的长枪受到上帝的加持，所以骑士会先对怪物造成伤害，其次怪物对骑士造成伤害。ZQ现在想知道，qq分钟后，每个骑士的血量。怪物（骑士）只能对在与其同一位置的骑士（怪物）造成伤害。

Input 

第一行有一个数TT（T≤105T≤105），表示测试组数。 对于每一组测试，包含以下内容： 第一行两个数nn，qq(0<n,q≤2×1050<n,q≤2×105) 分别表示骑士的数量，ZQ想要询问的时间。 第二行有nn个整数HPiHPi (0<HPi≤1090<HPi≤109) 表示第i个骑士的血量。 第三行有nn个整数KiKi (0<Ki≤1090<Ki≤109) 表示第i个骑士的伤害值。 接下来 qq行，每行有两个整数 HPjHPj，ajaj ( 0<HPj,aj≤1090<HPj,aj≤109) 表示第j分钟的怪物的血量及伤害值。 数据保证∑n≤2×105∑n≤2×105 ，∑q≤2×105∑q≤2×105。

Output 

对于每一组测试，输出一行nn个整数表示qq分钟后骑士的血量。

• Sample Input
• Raw

1 4 2 5 2 6 10 1 2 2 1 4 3 4 3

• Sample Output
• Raw

0 0 3 10

Hint 

不要用memset。不然你会黄的。。。。。

思路：

  这道题有几个需要处理的东西，首先是骑士的血量与伤害，另外就是怪的血量与伤害，我想法就是：我们用树状数组记录前缀和的方式存下骑士的伤害，就能知道怪能走到哪个骑士的面前（并且还能知道他对该骑士之前的所有骑士造成伤害）<-这里二分优化；然后，线段树记录骑士的血量下限，我们对线段树的更新是更新它的值，且要有lazy标记，一旦有节点出现“<=0”情况，就要往下推，找到那个（些）被杀死的骑士，此时，将他们的存在树状数组中的伤害清零，并且将他们节点的值改为INF（无限大）。 

细节：

  二分操作的时候，我们用一个ans来逼近答案，最初的l=1, r=N, ans=N+1。然后就是普通的二分，记得最后返回时-1。

  pushdown的时候，本题最难也就在于pushdown，我们往下判断，遇到INF无限大的时候不用给予它赋值了，因为已经死了，不用考虑它。还有向下走的时候，判断lazy标记的同时，不要忘记加上一句"l!=r"，毕竟那是叶子节点。

  最后啊，就是剧终大礼包，我献上自己写的两份代码，一份备注满满的，还有一份给读者找BUG时用。

详细备注的代码一：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
typedef long long ll;
const int maxN=2e5+7;
const ll INF=(ll)1<<58;
int N,M;
ll bit[maxN<<2];       //骑士伤害的前缀和，后面用二分来查找是否符合条件这样的mid，一一寻找会找到第几个
ll q_k[maxN<<2];       //每个骑士的血量和伤害
ll trie[maxN<<2],lazy[maxN<<2];       //用线段树存储每个骑士的血量（区间非0最小值），活着的骑士才有伤害
void update(int i, ll x)        //更新树状数组，记录骑士伤害值前缀
{while(i<=N){bit[i]+=x;i+=lowbit(i);}
}
ll sum(int i)       //前缀和的（<=i）的值，意味着此前（包括该点）的骑士能造成的伤害总值
{ll res=0;while(i){res+=bit[i];i-=lowbit(i);}return res;
}
int erfen_shanghai(ll question)        //这个怪的血量能走到哪一个骑士的面前？——最后答案-1，骑士先动手
{int l=1,r=N,ans=N+1;while(l<=r){int mid=(l+r)>>1;if(sum(mid)<question) l=mid+1;else{ans=mid;r=mid-1;}}return ans-1;       //前面一位骑士就能击杀这个怪，——此时已经找到前几位需要扣血了
}
void buildTree(int rt, int l, int r)
{if(l==r){scanf("%lld",&trie[rt]);return;}int mid=(l+r)>>1;buildTree(rt<<1, l, mid);buildTree(rt<<1|1, mid+1, r);trie[rt]=min(trie[rt<<1], trie[rt<<1|1]);
}
void pushdown(int rt, int l, int r, bool flag)
{if(lazy[rt] && l!=r)        //这里需要考虑l==r也就是叶子节点{if(trie[rt<<1]!=INF)                //如果这个节点所有的骑士都已经阵亡，那么就不用去考虑这个节点了（==INF情况）{trie[rt<<1]+=lazy[rt];lazy[rt<<1]+=lazy[rt];}if(trie[rt<<1|1]!=INF){trie[rt<<1|1]+=lazy[rt];lazy[rt<<1|1]+=lazy[rt];}lazy[rt]=0;}if(trie[rt]>0) return;      //既然父节点的值>0则子节点的值一定>0，则不必往下递推（是flag==true时专门判断该节点是否需要下一步判断使用）if(l==r)            //叶子节点{if(flag)      //此时有{根节点的值<=0；上面已经判断出需要向下更新},flag代表此时的父节点<=0，需要更新（至少一个）子节点{update(l, -q_k[l]);q_k[l]=0;trie[rt]=INF;}return;}if(flag)        //访问到根节点出现"<=0"即区间内有骑士死亡，则向下找到那个骑士{int mid=(l+r)>>1;pushdown(rt<<1, l, mid, true);pushdown(rt<<1|1, mid+1, r, true);trie[rt]=min(trie[rt<<1], trie[rt<<1|1]);}
}
void updateTree(int rt, int l, int r, int ql, int qr, ll val)  //val表示将要扣的血量（为负数）
{if(trie[rt]==INF) return;           //全都阵亡，无需考虑if(ql<=l && qr>=r){trie[rt]+=val;lazy[rt]+=val;if(trie[rt]<=0) pushdown(rt, l, r, true);       //有死亡骑士，向下更新，去除其在树状数组中的值return;}pushdown(rt, l, r, false);int mid=(l+r)>>1;if(ql<=mid) updateTree(rt<<1, l, mid, ql, qr, val);if(qr>mid) updateTree(rt<<1|1, mid+1, r, ql, qr, val);trie[rt]=min(trie[rt<<1], trie[rt<<1|1]);
}
void push_final(int rt, int l, int r)
{if(l==r){printf("%lld",(trie[rt]==INF || trie[rt]<0)?0:trie[rt]);printf(l==N?"n":" ");return;}pushdown(rt, l, r, false);int mid=(l+r)>>1;push_final(rt<<1, l, mid);push_final(rt<<1|1, mid+1, r);
}
int main()
{int T;scanf("%d",&T);while(T--)      //T<=1e5，直接上复杂度为O(n)的memset()会T{scanf("%d%d",&N,&M);        //骑士的数量，想要询问的时间for(int i=0; i<=(N<<2); i++) {bit[i]=0; trie[i]=0; lazy[i]=0; q_k[i]=0;}buildTree(1, 1, N);         //骑士血量->建立线段树for(int i=1; i<=N; i++){scanf("%lld",&q_k[i]);       //骑士伤害->建立树状数组update(i, q_k[i]);}while(M--){ll hp,k;       //怪物的血量与伤害scanf("%lld%lld",&hp,&k);int pos=erfen_shanghai(hp);     //二分找到杀到第几个骑士那里怪才会死if(!pos) continue;        //可能怪遇到第一个骑士就死了updateTree(1, 1, N, 1, pos, -k);}push_final(1, 1, N);}return 0;
}

代码二：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
typedef long long ll;
const ll INF=(ll)1<<58;
const int maxN=2e5+7;
int N,Q;
ll tree[maxN<<2],lazy[maxN<<2],bit[maxN<<2],Kill[maxN<<2];
void updatebit(int i, ll x)
{while(i<=N){bit[i]+=x;i+=lowbit(i);}
}
ll Sum(int i)
{ll res=0;while(i){res+=bit[i];i-=lowbit(i);}return res;
}
int erfen_match(ll ques)
{int l=1,r=N,ans=N+1;while(l<=r){int mid=(l+r)>>1;if(Sum(mid)<ques) l=mid+1;else{ans=mid;r=mid-1;}}return ans-1;
}
void buildTree(int rt, int l, int r)
{if(l==r){scanf("%lld",&tree[rt]);return;}int mid=(l+r)>>1;buildTree(rt<<1, l, mid);buildTree(rt<<1|1, mid+1, r);tree[rt]=min(tree[rt<<1], tree[rt<<1|1]);
}
void pushdown(int rt, int l, int r, bool flag)
{if(lazy[rt] && l!=r){if(tree[rt<<1]!=INF){tree[rt<<1]+=lazy[rt];lazy[rt<<1]+=lazy[rt];}if(tree[rt<<1|1]!=INF){tree[rt<<1|1]+=lazy[rt];lazy[rt<<1|1]+=lazy[rt];}lazy[rt]=0;}if(tree[rt]>0) return;if(l==r){if(flag){updatebit(l, -Kill[l]);Kill[l]=0;tree[rt]=INF;}return;}if(flag){int mid=(l+r)>>1;pushdown(rt<<1, l, mid, true);pushdown(rt<<1|1, mid+1, r, true);tree[rt]=min(tree[rt<<1], tree[rt<<1|1]);}
}
void updateTree(int rt, int l, int r, int ql, int qr, ll val)
{if(tree[rt]==INF) return;if(ql<=l && qr>=r){tree[rt]+=val;lazy[rt]+=val;if(tree[rt]<=0) pushdown(rt, l, r, true);return;}pushdown(rt, l, r, false);int mid=(l+r)>>1;if(ql<=mid) updateTree(rt<<1, l, mid, ql, qr, val);if(qr>mid) updateTree(rt<<1|1, mid+1, r, ql, qr, val);tree[rt]=min(tree[rt<<1], tree[rt<<1|1]);
}
void push_final(int rt, int l, int r)
{if(l==r){printf("%lld",(tree[rt]<=0 || tree[rt]==INF)?0:tree[rt]);printf(l==N?"n":" ");return;}pushdown(rt, l, r, false);int mid=(l+r)>>1;push_final(rt<<1, l, mid);push_final(rt<<1|1, mid+1, r);
}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&N,&Q);for(int i=0; i<=(N<<2); i++) {tree[i]=0; lazy[i]=0; bit[i]=0; Kill[i]=0;}buildTree(1, 1, N);for(int i=1; i<=N; i++){scanf("%lld",&Kill[i]);updatebit(i, Kill[i]);}while(Q--){ll hp,k;scanf("%lld%lld",&hp,&k);int pos=erfen_match(hp);if(!pos) continue;updateTree(1, 1, N, 1, pos, -k);}push_final(1, 1, N);}return 0;
}

  我的第100份原创博客，还不错，一道有思维的题，很好的巩固了我关于线段树和树状数组的知识。