题目大意
http://www.lydsy.com/JudgeOnline/problem.php?id=4003
题解
一开始看漏条件了
题目保证当占领城池可以使攻击力乘上\(v_i\)时,一定有\(v_i>0\)
上面这句话很重要(或者说去掉这句话就可以出成一道新题)
我们考虑在每个节点上都维护一个最小堆
每次移动时我们让在堆中的所有骑士一起移动
这样我们知道:如果堆顶的骑士可以占领成功
那么这个堆里剩下的所有骑士都一定能够占领成功
如果堆顶元素无法占领我们就删去这个堆顶的元素,这样我们最多删除n次
最坏情况是\(O(nlogn)\)的,可以承受
所以我们还需要这个堆支持快速合并,任意一个可并堆即可
于是我敲了一棵左偏树上去...打标记打到手软...第一次在堆上打标记
这个标记的正确性就由上面加粗的话保证了
这句话保证了:打标记后树的结构不会改变
调了1h才发现是merge没有return...
神奇的windows系统还让我过了样例和对拍,linux虚拟机下直接爆炸
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &x){x=0;char ch;bool flag = false;while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 300010;
struct Node{Node *ch[2];ll val,add,mul;int cnt,tag,deg,id;
}*null;
Node mem[maxn<<1],*li;
Node *root[maxn];
inline void init(){li = mem;null = li++;null->ch[0] = null->ch[1] = null;null->val = null->add = null->cnt = null->tag = null->mul = 0;
}
inline Node* newNode(int id,ll val){Node *p = li++;p->val = val;p->ch[0] = p->ch[1] = null;p->cnt = p->tag = p->deg = p->add = 0;p->mul = 1;p->id = id;return p;
}
inline void pushdown(Node *p){if(p == null) return;if(p->ch[0] != null){Node *x = p->ch[0];if(p->mul != 1){x->mul *= p->mul;x->add *= p->mul;x->val *= p->mul;}if(p->add != 0){x->add += p->add;x->val += p->add;}if(p->tag != 0){x->tag += p->tag;x->cnt += p->tag;}}if(p->ch[1] != null){Node *x = p->ch[1];if(p->mul != 1){x->mul *= p->mul;x->add *= p->mul;x->val *= p->mul;}if(p->add != 0){x->add += p->add;x->val += p->add;}if(p->tag != 0){x->tag += p->tag;x->cnt += p->tag;}}p->mul = 1;p->tag = p->add = 0;
}
Node *merge(Node *x,Node *y){//printf("%d %d\n",x,y);if(x == null) return y;if(y == null) return x;if(x->val > y->val) swap(x,y);pushdown(x);x->ch[1] = merge(x->ch[1],y);if(x->ch[0]->deg < x->ch[1]->deg)swap(x->ch[0],x->ch[1]);x->deg = x->ch[1]->deg + 1;return x;
}
int ans1[maxn],ans2[maxn];
inline void pop_less(int i,ll k,int p){while(1){if(root[i] == null) break;if(root[i]->val >= k) break;pushdown(root[i]);ans2[root[i]->id] = root[i]->cnt;//printf("%d died on %d with killed %d\n",root[i]->id,p,root[i]->cnt);//printf("%lld <-> %lld\n",root[i]->val,k);root[i] = merge(root[i]->ch[0],root[i]->ch[1]);ans1[p]++;}
}
ll h[maxn],v[maxn],s[maxn];
int c[maxn],fa[maxn],a[maxn];
inline void update(Node *p,int i){//printf("update");p->tag++;p->cnt++;if(a[i] == 0){p->add += v[i];p->val += v[i];}else{p->mul *= v[i];p->add *= v[i];p->val *= v[i];}
}
int main(){init();int n,m;read(n);read(m);for(int i=1;i<=n;++i) read(h[i]),root[i] = null;//printf("%d\n",root[2]);for(int i=2;i<=n;++i){read(fa[i]);read(a[i]);read(v[i]);}for(int i=1;i<=m;++i){read(s[i]);read(c[i]);if(s[i] < h[c[i]]){ans1[c[i]]++;ans2[i] = 0;}else{Node *p = newNode(i,s[i]);update(p,c[i]);root[c[i]] = merge(root[c[i]],p);}}for(int i=n;i>=2;--i){pop_less(i,h[fa[i]],fa[i]);update(root[i],fa[i]);root[fa[i]] = merge(root[i],root[fa[i]]);}while(root[1] != null){pushdown(root[1]);ans2[root[1]->id] = root[1]->cnt;//printf("%d win with killed %d\n",root[1]->id,root[1]->cnt);root[1] = merge(root[1]->ch[0],root[1]->ch[1]);}for(int i=1;i<=n;++i) printf("%d\n",ans1[i]);for(int i=1;i<=m;++i) printf("%d\n",ans2[i]);getchar();getchar();return 0;
}