[bzoj4003]城市攻占
2024-09-06 15:49:07
倍增,对于每一个点计算他走到$2^i$次祖先所需要的攻击力以及最终会变成什么(一个一次函数),简单处理即可
(然而这样是错的,因为他只保证了骑士的攻击力可以存,并没有保证这个一次函数的系数可以存)
(其实还可以用科学记数法即pair<long double,int>来存即可,只要注意精度&常数)
正解是模拟,维护当前子树中骑士血量的左偏树(支持合并),然后考虑不断删除堆顶,修改可以用打标记来实现(因为乘的是正的,所以不改变顺序)
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 300005
4 #define ll long long
5 struct ji{
6 int nex,to,len;
7 }edge[N<<1];
8 pair<ll,int>val[N];
9 int E,n,m,x,r[N],dis[N],ls[N],rs[N],head[N],d[N],p[N],ans1[N],ans2[N];
10 ll y,tc[N],tj[N],h[N],v[N];
11 void upd(int k,ll x,ll y){
12 tc[k]=tc[k]*x;
13 tj[k]=tj[k]*x+y;
14 val[k].first=val[k].first*x+y;
15 }
16 void down(int k){
17 upd(ls[k],tc[k],tj[k]);
18 upd(rs[k],tc[k],tj[k]);
19 tc[k]=1;
20 tj[k]=0;
21 }
22 int merge(int x,int y){
23 if ((!x)||(!y))return x+y;
24 down(x);
25 down(y);
26 if (val[x]>val[y])swap(x,y);
27 rs[x]=merge(rs[x],y);
28 if (dis[ls[x]]<dis[rs[x]])swap(ls[x],rs[x]);
29 dis[x]=dis[rs[x]]+1;
30 return x;
31 }
32 void add(int x,int y){
33 edge[E].nex=head[x];
34 edge[E].to=y;
35 head[x]=E++;
36 }
37 void dfs(int k,int sh){
38 d[k]=sh;
39 for(int i=head[k];i!=-1;i=edge[i].nex){
40 dfs(edge[i].to,sh+1);
41 r[k]=merge(r[k],r[edge[i].to]);
42 }
43 while ((r[k])&&(val[r[k]].first<h[k])){
44 down(r[k]);
45 ans1[k]++;
46 ans2[r[k]]=d[val[r[k]].second]-d[k];
47 r[k]=merge(ls[r[k]],rs[r[k]]);
48 }
49 if (!p[k])upd(r[k],1,v[k]);
50 else upd(r[k],v[k],0);
51 }
52 int main(){
53 scanf("%d%d",&n,&m);
54 memset(head,-1,sizeof(head));
55 for(int i=1;i<=n;i++)scanf("%lld",&h[i]);
56 for(int i=2;i<=n;i++){
57 scanf("%d%d%lld",&x,&p[i],&v[i]);
58 add(x,i);
59 }
60 for(int i=1;i<=m;i++){
61 scanf("%lld%d",&y,&x);
62 val[i]=make_pair(y,x);
63 tc[i]=1;
64 r[x]=merge(r[x],i);
65 }
66 dfs(1,0);
67 while (r[1]){
68 ans2[r[1]]=d[val[r[1]].second]+1;
69 r[1]=merge(ls[r[1]],rs[r[1]]);
70 }
71 for(int i=1;i<=n;i++)printf("%d\n",ans1[i]);
72 for(int i=1;i<=m;i++)printf("%d\n",ans2[i]);
73 }
最新文章
- 用Crontab打造简易工作流引擎
- win7下exe提示无法正常启动(0xc0000906)
- HDU 3555 Bomb
- android studio1.0 for Mac环境搭建与demo运行(手动下载gradle,科学上google) 转载
- jquery.ajaxfileupload.js
- border-radius 样式表CSS3圆角属性
- C# 发送邮件方法
- log4net使用简明教程
- ArcSDE for Microsoft SQL Server Post Installation图解(转)
- python的min()函数也可用于比较tuple
- UIBezierPath详解
- IP相关常识
- Wireshark网络抓包(四)——工具
- [知了堂学习笔记]_牵线Eclipse和Tomcat第一篇 —— 配置Java环境变量&;&;安装eclipse
- TCP的定时器系列 — SYNACK定时器
- SUSE12SP3-Mycat(4)rule.xml配置详解
- Admin Console 反应慢的相关bug
- Abp vNext 切换MySql数据库
- hugepage优势
- jQuery.TreeView插件实现树状导航(十三)
热门文章
- Linux基础安全配置(centos7)
- Azure Devops实践(5)- 构建springboot项目打包docker镜像及容器化部署
- Flink Sql 之 Calcite Volcano优化器(源码解析)
- Java 是编译型语言还是解释型语言?
- Sequence Model-week1编程题2-Character level language model【RNN生成恐龙名 LSTM生成莎士比亚风格文字】
- JAVA的array中indexOf
- 『学了就忘』Linux基础 — 3、CentOS镜像下载
- 高并发场景下JVM调优实践之路
- longest-consecutive-sequence leetcode C++
- 如何反编译微信小程序&#128123;