题目大意
题解
一开始看漏条件了
题目保证当占领城池可以使攻击力乘上\(v_i\)时,一定有\(v_i>0\) 上面这句话很重要(或者说去掉这句话就可以出成一道新题) 我们考虑在每个节点上都维护一个最小堆 每次移动时我们让在堆中的所有骑士一起移动 这样我们知道:如果堆顶的骑士可以占领成功 那么这个堆里剩下的所有骑士都一定能够占领成功 如果堆顶元素无法占领我们就删去这个堆顶的元素,这样我们最多删除n次 最坏情况是\(O(nlogn)\)的,可以承受 所以我们还需要这个堆支持快速合并,任意一个可并堆即可于是我敲了一棵左偏树上去...打标记打到手软...第一次在堆上打标记
这个标记的正确性就由上面加粗的话保证了 这句话保证了:打标记后树的结构不会改变调了1h才发现是merge没有return...
神奇的windows系统还让我过了样例和对拍,linux虚拟机下直接爆炸Code
#include#include #include using namespace std;typedef long long ll;template 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 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;}