首页 > 代码库 > [bzoj4906][BeiJing2017]喷式水战改
[bzoj4906][BeiJing2017]喷式水战改
来自FallDream的博客，未经允许，请勿转载，谢谢。
【题目背景】
拿到了飞机的驾照(?)，这样补给就不愁了
XXXX年XX月XX日
拿到了喷气机(??)的驾照，这样就飞得更快了
XXXX年XX月XX日
拿到了攻击机(???)的驾照（不存在的）
XXXX年XX月XX日
用铅版做夹层的话，机身可是会变重的呢
XXXX年XX月XX日
幸酱的特制快递，精确投递到了目标地点
-------------------------------------
又是核平的一天。
天音正在给喷气机做保养，并充填燃料。
这种喷气机是某姬(?????)特别制作的，发动机拥有三种工作状态
1、通常型（Original）：在高空平飞或隐蔽飞行时进行的低功耗高效率工作状态
2、后期型（Extended）：为在俯冲时最大化能量利用率而特别改造过的工作状态
3、增强型（Enhanced）：在俯冲攻击结束后为产生极限扭力抬高高度的工作状态
在一次攻击中，喷气机将会经历"通常-后期-增强-通常"的工作流程
不同工作状态中，燃料的利用效率是不同的
现在天音正在调整喷气机燃料装填序列
你需要做的就是求出燃料能产生的最大总能量
为什么是你？
和平还是核平，选一个吧
【题目描述】
初始燃料序列为空。每次操作会向序列中的pi位置添加xi单位的同种燃料，该燃料每一单位在三种工作状态下能产生的能量分别为ai, bi, ci。添加的位置pi是指，在添加后，加入的第一个单位燃料前面有pi个单位的原燃料。全部的xi单位燃料依次放置，然后原来在pi位置的燃料（如果有的话）依次向后排列。对于一个确定的燃料序列，其能产生的最大总能量为：将序列依次分成"通常-后期-增强-通常"四段（每段可以为空），每一段在对应工作状态下产生的能量之和的最大值。对于每次添加操作，你需要给出该次操作使得最大总能量增加了多少。如果对于这种计算方式没有直观的感受，可以查看样例说明。
1 ≤ n ≤ 10^5, 1 ≤ ai, bi, ci ≤ 10^4， 1 ≤ xi ≤ 10^9
显然存在最优解，满足每一段都取相同的状态。
然后考虑平衡树维护，合并可以类似区间dp。
复杂度4^3*nlogn
#include<iostream>#include<cstdio>#include<cstring>#define ll long long#define MN 500005#define getchar() (*S++)char BB[1<<26],*S=BB;using namespace std;inline int read(){ int x = 0; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘) ch = getchar(); while(ch >= ‘0‘ && ch <= ‘9‘){x = x * 10 + ch - ‘0‘;ch = getchar();} return x;}inline ll llread(){ ll x = 0; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘)ch = getchar(); while(ch >= ‘0‘ && ch <= ‘9‘){x = x * 10 + ch - ‘0‘;ch = getchar();} return x;}struct data{ ll x[4][4]; data(){} data(ll a,ll b,ll c) { memset(x,0,sizeof(x)); x[0][0]=x[3][3]=a;x[1][1]=b; x[2][2]=c;x[0][1]=max(a,b); x[1][2]=max(b,c);x[2][3]=max(a,c); x[0][2]=x[1][3]=x[0][3]=max(a,max(b,c)); } friend data operator + (data a,data b) { data c;memset(c.x,0,sizeof(c.x)); for(int l=1;l<=4;++l) for(int i=0;i+l-1<4;++i) { int j=i+l-1;c.x[i][j]=0; for(int k=i;k<=j;++k) c.x[i][j]=max(c.x[i][j],a.x[i][k]+b.x[k][j]); } return c; }}s[MN+5];int fa[MN+5],sz[MN+5],c[MN+5][2],rt=0,mark,A[MN+5],L[MN+5],B[MN+5],C[MN+5],n,cnt=0,q[MN+5],top=0;ll size[MN+5],tot;int tms=0;inline void update(int x){ s[x]=(data){1LL*A[x]*L[x],1LL*B[x]*L[x],1LL*C[x]*L[x]}; if(c[x][0]) s[x]=s[c[x][0]]+s[x]; if(c[x][1]) s[x]=s[x]+s[c[x][1]]; size[x]=size[c[x][0]]+size[c[x][1]]+L[x]; sz[x]=sz[c[x][0]]+sz[c[x][1]]+1;}int Find(int x,ll pos){ ll Sz1=size[c[x][0]],Sz2=Sz1+L[x]; if((Sz1<pos||(!c[x][0]&&!pos))&&Sz2>=pos) return x; if(Sz1>=pos) return Find(c[x][0],pos); return tot+=Sz2,Find(c[x][1],pos-Sz2);}void ins(int&x,int ai,int bi,int ci,ll pos,int len,int last=0){ if(!x) { x=++cnt;s[x]=data(1LL*ai*len,1LL*bi*len,1LL*ci*len); L[x]=size[x]=len;A[x]=ai;B[x]=bi;C[x]=ci;sz[x]=1;fa[x]=last; return; } ll Sz=size[c[x][0]]+L[x]; if(Sz<=pos) ins(c[x][1],ai,bi,ci,pos-Sz,len,x); else ins(c[x][0],ai,bi,ci,pos,len,x); update(x); if(max(sz[c[x][0]],sz[c[x][1]])>0.7*sz[x]) mark=x;}void Modify(int x,int k,ll pos,int Len){ if(x==k) { L[x]=Len;update(x); return; } if(size[c[x][0]]>=pos) Modify(c[x][0],k,pos,Len); else Modify(c[x][1],k,pos-L[x]-size[c[x][0]],Len); update(x);}void Dfs(int x){ if(c[x][0]) Dfs(c[x][0]); q[++top]=x; if(c[x][1]) Dfs(c[x][1]); }void Build(int&x,int l,int r,int last){ if(l>r) {x=0;return;} int mid=l+r>>1;x=q[mid];fa[x]=last; Build(c[x][0],l,mid-1,x); Build(c[x][1],mid+1,r,x); update(x);}void rebuild(int x){ mark=top=0;Dfs(x);int y=fa[x]; if(!y) Build(rt,1,top,0); else Build(c[y][c[y][1]==x],1,top,y);}int main(){ fread(BB,1,1<<26,stdin); n=read();ins(rt,0,0,0,0,0);ll pre=0; for(int i=1;i<=n;++i) { ll p=llread(); int ai=read(),bi=read(),ci=read(),x=read(); tot=tms=0;int k=Find(rt,p); if(tot+size[c[k][0]]+L[k]!=p) { ll Left=tot+size[c[k][0]]+L[k]-p; tms=0;Modify(rt,k,p,L[k]-Left); ins(rt,ai,bi,ci,p,x);if(mark) rebuild(mark); ins(rt,A[k],B[k],C[k],p+x,Left); } else ins(rt,ai,bi,ci,p,x); printf("%lld\n",s[rt].x[0][3]-pre); pre=s[rt].x[0][3];if(mark) rebuild(mark); } return 0;}
[bzoj4906][BeiJing2017]喷式水战改
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。