# P3103 [USACO14FEB]Airplane Boarding G 题解(P3103 [usaco14feb] aircraft boarding g problem solution)-ai

## P3103 [USACO14FEB]Airplane Boarding G 题解(P3103 [usaco14feb] aircraft boarding g problem solution)

Luogu传送门

### $$Solution$$

$$d – c < b – a$$ 使得 $$(c, d)$$ 对于当前的奶牛没有贡献，再加上 $$a < c$$ 使得 $$(c, d)$$ 这个条件对于后面所有的奶牛都没有了贡献。

• 查询：把 $$pos \leq S_i$$ 的数切下来查询。
• 修改：当前插入的二元组是 $$(a, b)$$，然后把树中 $$d – c > b – a$$ 的点全都删掉。

### $$Code$$

#include <bits/stdc++.h>

using namespace std;

namespace IO{
int x = 0;
char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x;
}

template <typename T> inline void write(T x){
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;

const int N = 2e5 + 10;
int n;
int S[N], T[N];

namespace FHQ_treap{
#define ls(x) t[x].l
#define rs(x) t[x].r

struct tree{
int sum, wei, l, r, x, y, val, tag;
}t[N];
int root, tot;

inline void pushup(int x){
if(!x) return;
t[x].val = t[x].y;
if(ls(x)) t[x].val = max(t[x].val, t[ls(x)].val);
if(rs(x)) t[x].val = max(t[x].val, t[rs(x)].val);
}

inline void pushdown(int x){
if(!x || !t[x].tag) return;
int tag = t[x].tag;
if(ls(x)){
t[ls(x)].x -= tag, t[ls(x)].y += tag;
t[ls(x)].tag += tag, t[ls(x)].val += tag;
}
if(rs(x)){
t[rs(x)].x -= tag, t[rs(x)].y += tag;
t[rs(x)].tag += tag, t[rs(x)].val += tag;
}
t[x].tag = 0;
}

inline void split_pos(int x, int k, int &a, int &b){
if(!x) return a = b = 0, void();
pushdown(x);
if(k >= t[x].x) a = x, split_pos(rs(x), k, rs(x), b);
else b = x, split_pos(ls(x), k, a, ls(x));
pushup(x);
}

inline void split_val(int x, int k, int &a, int &b){
if(!x) return a = b = 0, void();
pushdown(x);
if(k >= t[x].y) a = x, split_val(rs(x), k, rs(x), b);
else b = x, split_val(ls(x), k, a, ls(x));
pushup(x);
}

inline int merge(int x, int y){
if(!x || !y) return x | y;
if(t[x].wei <= t[y].wei){
pushdown(x);
rs(x) = merge(rs(x), y);
return pushup(x), x;
}else{
pushdown(y);
ls(y) = merge(x, ls(y));
return pushup(y), y;
}
}

inline int newnode(int a, int b){
t[++tot].x = a, t[tot].y = t[tot].val = b, t[tot].wei = rand();
}
}
using namespace FHQ_treap;

int main(){
for(int i = 1; i <= n; ++i)
int ans = 0, a, b, c;
root = newnode(0, 0);
for(int i = n; i >= 1; --i){
split_pos(root, S[i], a, b);
int res = t[a].val + S[i] + T[i];
ans = max(ans, res);
t[a].tag++, t[a].x--, t[a].y++, t[a].val++;//奶牛初始坐标向左依次减 1，对于 (a, b) 来说相当于变成了 (a - 1, b)
split_val(b, res + 1 - S[i], b, c);
root = merge(a, merge(newnode(S[i], res + 1 - S[i]), c));
}
write(ans), puts("");
return 0;
}

————————

Luogu portal

### $$Solution$$

I found this problem by chance.

When I first finished reading the question, I felt that it could only be simulated by violence

So after a shameless look at the problem solution, we can use some expressions to express the time when each cow reaches its position, so as to calculate the total time.

Specifically, the time taken for the \ (n \) cow to reach its position is \ (s_n + t_n \), and the time for the \ (n – 1 \) cow to reach \ (s_n + t_n + 1 \) (because the initial coordinate of \ (cow_{n – 1} \) is 1 to the left of the coordinate of \ (cow_n \)

Therefore, we can use the binary \ ((pos_i, time_i) \) to represent that the time taken for a cow to reach \ (pos_i \) is \ (time_i \), and there are many such binary for a cow to limit it.

Then the time when the cow reaches its destination is \ (\ Max \ {time_i + (s – pos_i) \} + T \), and the binary satisfies the condition \ (pos_i \ Leq s \).

We propose \ (s \) again, so what we are looking for is the maximum value of \ (time_i – pos_i \).

However, the complexity is still \ (n ^ 2 \), and we need to consider how to optimize it.

It is not difficult to find that for the two binary constraints \ ((a, b) \) and \ ((C, d) \), if \ (A & lt; C \) and \ (D – C & lt; B – a \), then \ ((C, D) \) is useless for all cows in the future.

$$D – C & lt; B – a$$ makes \ ((C, d) \) no contribution to the current cow. In addition, \ (A & lt; C \) makes \ ((C, d) \) no contribution to all the following cows.

So we can just delete this condition.

Maintain the values of \ (POS \) and \ (time – POS \) and the maximum value of \ (time – POS \) with the balance tree, and enumerate each cow in reverse order:

• Query: cut off the number of \ (POS \ Leq s_i \) and query.
• Modify: the currently inserted binary is \ ((a, b) \), and then delete all the points of \ (D – C > b – a \) in the tree.

Then there’s nothing else. See the code for details.

I wrote fhq Treap

### $$Code$$

#include <bits/stdc++.h>

using namespace std;

namespace IO{
int x = 0;
char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x;
}

template <typename T> inline void write(T x){
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;

const int N = 2e5 + 10;
int n;
int S[N], T[N];

namespace FHQ_treap{
#define ls(x) t[x].l
#define rs(x) t[x].r

struct tree{
int sum, wei, l, r, x, y, val, tag;
}t[N];
int root, tot;

inline void pushup(int x){
if(!x) return;
t[x].val = t[x].y;
if(ls(x)) t[x].val = max(t[x].val, t[ls(x)].val);
if(rs(x)) t[x].val = max(t[x].val, t[rs(x)].val);
}

inline void pushdown(int x){
if(!x || !t[x].tag) return;
int tag = t[x].tag;
if(ls(x)){
t[ls(x)].x -= tag, t[ls(x)].y += tag;
t[ls(x)].tag += tag, t[ls(x)].val += tag;
}
if(rs(x)){
t[rs(x)].x -= tag, t[rs(x)].y += tag;
t[rs(x)].tag += tag, t[rs(x)].val += tag;
}
t[x].tag = 0;
}

inline void split_pos(int x, int k, int &a, int &b){
if(!x) return a = b = 0, void();
pushdown(x);
if(k >= t[x].x) a = x, split_pos(rs(x), k, rs(x), b);
else b = x, split_pos(ls(x), k, a, ls(x));
pushup(x);
}

inline void split_val(int x, int k, int &a, int &b){
if(!x) return a = b = 0, void();
pushdown(x);
if(k >= t[x].y) a = x, split_val(rs(x), k, rs(x), b);
else b = x, split_val(ls(x), k, a, ls(x));
pushup(x);
}

inline int merge(int x, int y){
if(!x || !y) return x | y;
if(t[x].wei <= t[y].wei){
pushdown(x);
rs(x) = merge(rs(x), y);
return pushup(x), x;
}else{
pushdown(y);
ls(y) = merge(x, ls(y));
return pushup(y), y;
}
}

inline int newnode(int a, int b){
t[++tot].x = a, t[tot].y = t[tot].val = b, t[tot].wei = rand();
}
}
using namespace FHQ_treap;

int main(){
for(int i = 1; i <= n; ++i)
int ans = 0, a, b, c;
root = newnode(0, 0);
for(int i = n; i >= 1; --i){
split_pos(root, S[i], a, b);
int res = t[a].val + S[i] + T[i];
ans = max(ans, res);
t[a].tag++, t[a].x--, t[a].y++, t[a].val++;//奶牛初始坐标向左依次减 1，对于 (a, b) 来说相当于变成了 (a - 1, b)
split_val(b, res + 1 - S[i], b, c);
root = merge(a, merge(newnode(S[i], res + 1 - S[i]), c));
}
write(ans), puts("");
return 0;
}