Description
【题目背景】
拿到了飞机的驾照(?)，这样补给就不愁了
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位置的燃料（如果有的话）依次向后排列。对于一个确定的燃料序列，其
能产生的最大总能量为：将序列依次分成"通常-后期-增强-通常"四段（每段可以为空），每一段在对应工作状态
下产生的能量之和的最大值。对于每次添加操作，你需要给出该次操作使得最大总能量增加了多少。如果对于这种
计算方式没有直观的感受，可以查看样例说明。
Input
第一行一个数n，表示操作个数。
接下来n行，每行5个数pi, ai, bi, ci, xi，空格分隔，表示向序列中的pi位置添加xi单位的同种燃料
这种燃料每单位在通常、后期、增强工作状态下产生的能量分别为ai, bi, ci。
对于100%的数据，1 ≤ n ≤ 10^5, 1 ≤ ai, bi, ci ≤ 10^4， 1 ≤ xi ≤ 10^9。
对于100%的数据，保证插入时序列中至少已有pi单位的燃料。
Output
n行，每行一个数，表示该次操作后能量序列所能产生的最大总能量增加了多少。
Sample Input
5 0 25 37 46 2 1 32 14 16 3 3 99 77 88 4 2 43 68 57 5 14 72 36 18 6
Sample Output
92 75 396 319 432 【样例解释】 第一次操作后，燃料序列为[1 1]，最大能量发生方式为[En1 En1]，共46+46=92。 第二次操作后，燃料序列为[1 2 2 2 1]，最大能量发生方式为[Or1 Or2 Or2 Or2 En1]，共25+32+32+32+46=167，增加了167-92=75。 第三次操作后，燃料序列为[1 2 2 3 3 3 2 1]，最大能量发生方式为[Or1 Or2 Or2 Or3 Or3 Or3 Or3 Or2 En1]，增加了99*4=396。 第四次操作后，燃料序列为[1 2 4 4 4 4 4 2 3 3 3 2 1] 最大能量发生方式为[Or1 Or2 Ex4 Ex4 Ex4 Ex4 Ex4 Or2 Or3 Or3 Or3 Or3 Or2 Or1]。 第五次操作后，燃料序列为[1 2 4 4 4 4 4 2 3 3 3 2 1 5 5 5 5 5 5] 最大能量发生方式为[Or1 Or2 Ex4 Ex4 Ex4 Ex4 Ex4 Or2 Or3 Or3 Or3 Or3 Or2 Or1 Or5 Or5 Or5 Or5 Or5 Or5]。
题解：
首先很明显能看出来，求最大能量需要用到dp。
显然，某一连续相同种类的燃料段，在满足最终为最大能量时，一定是内部所有燃料在同种工作状态下的
dp转移第一版：dp[i][j] (0<=j<3) 表示到第i个燃料段，第i个燃料段工作状态<=j可产生的最大能量。
伪方程：dp[i][j]=max(dp[i-1][j]+该工作状态j产生的单位能量*段长度,dp[i][j-1])
题目中有插入操作，需要用数据结构维护——平衡树。
我们把每一段加进来的燃料作为一个节点拆入平衡树中。
根据插入位置，这个节点可能插在某个原来的“燃料段”中间，那我们就需要把那个燃料段拆成两半，把这个节点插到中间
所以选择，到底用哪个平衡树？
这个平衡树需要知道“排名”，需要支持不断删点、加点的操作——
SPLAY！
这时我们发现，如果按之前的dp方式，每新加一个点便要O(n)求一遍，总复杂度O(n²)
这可不太妙。。。
于是我们需要探索一种新的dp方式
我们可以考虑将dp于splay结合在一起，或是说在splay的时候顺便dp
那么dp转移第二版就出来了：对于splay中每一个节点，dp[i][j] (0<=i,j<4) 表示该节点及子树这一大段中的工作状态在i~j之间（或者可以这样理解：这段中最左边的燃料段的工作状态>=i，最右边的燃料段工作状态<=j，整个大段满足题目要求）
在每次update时维护即可。
这样感觉很巧妙有木有！
注意：我曾被卡常了好几次。。。就是dp[i][j]的含义问题：如果如上面叙述那样表示，每次转移复杂度大约4³；可如果表示这段中最左边燃料段工作状态就是i，最右边的就是j，那每次转移的复杂度就是44了…所以有句话说得好：dp状态想对了就是成功了一半
代码：
1 #include<cstdio>
2 #include<iostream>
3 #include<algorithm>
4 using namespace std;
5
6 typedef
long long ll;
7 const int N =
100005;
8 struct node{
9 int v,a,b,c;
10 ll s[
4][
4],dp[
4][
4],len;
11 node *pa,*ch[
2];
12 }pool[
2*N],*root,*
rf;
13 int cnt;
14
15 inline ll len(node *p) {
return p?p->len:
0; }
16 ll c[
4][
4];
17 void merge(ll a[
4][
4],ll b[
4][
4],node *
p){
18 for(
int i=
0;i<
4;i++
)
19 for(
int j=i;j<
4;j++
){
20 c[i][j]=
0;
21 for(
int k=i;k<=j;k++
)
22 c[i][j]=max(c[i][j],a[i][k]+
b[k][j]);
23 }
24 for(
int i=
0;i<
4;i++
)
25 for(
int j=
0;j<
4;j++) p->dp[i][j]=
c[i][j];
26 }
27 void update(node *
p){
28 p->len=(ll)(len(p->ch[
0])+len(p->ch[
1])+p->
v);
29 for(
int i=
0;i<
4;i++
)
30 for(
int j=
0;j<
4;j++) p->dp[i][j]=p->
s[i][j];
31 if(p->ch[
0]) merge(p->ch[
0]->dp,p->
dp,p);
32 if(p->ch[
1]) merge(p->dp,p->ch[
1]->
dp,p);
33 }
34 void ups(node *
p){
35 p->dp[
0][
0]=p->dp[
3][
3]=p->s[
0][
0]=p->s[
3][
3]=(ll)p->v*p->
a;
36 p->dp[
1][
1]=p->s[
1][
1]=(ll)p->v*p->
b;
37 p->dp[
2][
2]=p->s[
2][
2]=(ll)p->v*p->
c;
38 for(
int i=
0;i<
4;i++
)
39 for(
int j=i+
1;j<
4;j++
)
40 p->dp[i][j]=p->s[i][j]=max(p->s[i][j-
1],p->
s[j][j]);
41 }
42
43 void rotate(node *p,
int t){
44 node *pa=p->pa,*gp=pa->pa,*son=p->ch[t^
1];
45 pa->ch[t]=son;
if(son) son->pa=
pa;
46 p->ch[t^
1]=pa; pa->pa=
p;
47 p->pa=gp; gp->ch[pa==gp->ch[
1]]=
p;
48 if(root==pa) root=
p;
49 update(pa);update(p);
50 }
51 void splay(node *p,node *
t){
52 while(p->pa!=
t){
53 if(p->pa->pa==
t)
54 rotate(p,p==p->pa->ch[
1]);
55 else{
56 node *pa=p->pa,*gp=pa->
pa;
57 int f=pa==gp->ch[
0];
58 if(p==pa->ch[f]) rotate(p,f),rotate(p,!
f);
59 else rotate(pa,!f),rotate(p,!
f);
60 }
61 }
62 }
63
64 node *find(node *
p,ll k){
65 if(len(p->ch[
0])>=k)
return find(p->ch[
0],k);
66 if(len(p->ch[
0])+p->v>=k)
return p;
67 return find(p->ch[
1],k-p->v-len(p->ch[
0]));
68 }
69 void addnew(node *p,
int a,
int b,
int c,
int v){
70 p->a=a;p->b=b;p->c=c;p->v=v;p->len=
(ll)v;
71 ups(p);
72 }
73 void insert(ll k,node *
nd){
74 node *p=find(root,k),*
q;
75 splay(p,rf);
76 if(root->len==
k) {
77 p->ch[
1]=nd; nd->pa=
p;
78 update(p);
79 return;
80 }
81 q=find(root,k+
1);
82 if(p!=
q){
83 splay(q,root);
84 q->ch[
0]=nd; nd->pa=
q;
85 update(q); update(p);
86 return;
87 }
88 q=p->ch[
1];
89 if(!
q){
90 p->ch[
1]=nd; nd->pa=
p;
91 q=&pool[++cnt]; addnew(q,p->a,p->b,p->c,(
int)(len(p->ch[
0])+p->v-
k));
92 nd->ch[
1]=q; q->pa=
nd;
93 p->v=p->v-q->
v; ups(p);
94 update(nd);update(p);
95 }
96 else{
97 while(q->ch[
0]) q=q->ch[
0];
98 splay(q,root);
99 node *tmp=&pool[++cnt]; addnew(tmp,p->a,p->b,p->c,(
int)(len(p->ch[
0])+p->v-
k));
100 q->ch[
0]=nd; nd->pa=
q;
101 nd->ch[
1]=tmp; tmp->pa=
nd;
102 p->v=p->v-tmp->
v; ups(p);
103 update(tmp);update(nd);update(q);update(p);
104 }
105 }
106
107 int n;
108
109 int main()
110 {
111 int a,b,c,x,i,j;
112 ll pos,last=
0,now;
113 scanf(
"%d",&
n);
114
115 rf=&pool[++
cnt];
116 while(n--
){
117 scanf(
"%lld%d%d%d%d",&pos,&a,&b,&c,&
x);
118 node *nd=&pool[++
cnt]; addnew(nd,a,b,c,x);
119 if(!
root) {
120 root=
nd;
121 root->pa=rf;rf->ch[
1]=
root;
122 }
123 else insert(pos,nd);
124
125 now=root->dp[
0][
3];
126 printf(
"%lld\n",now-
last);
127 last=
now;
128 }
129
130 return 0;
131 }
View Code
转载于:https://www.cnblogs.com/lindalee/p/7989878.html
