A – The Fair Nut and the Best Path
sb 树形 DP。
// CF1083A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5 + 200;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, current, head[MAX_N], wi[MAX_N];
ll dp[MAX_N], gans;
struct edge
{
int to, nxt, weight;
} edges[MAX_N << 1];
void addpath(int src, int dst, int weight)
{
edges[current].to = dst, edges[current].nxt = head[src];
edges[current].weight = weight, head[src] = current++;
}
void dfs(int u, int fa)
{
ll biggest = -1, sbiggest = -1;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa)
{
dfs(edges[i].to, u);
ll tmp = dp[edges[i].to] - edges[i].weight;
if (tmp > biggest)
swap(biggest, sbiggest), biggest = tmp;
else if (tmp > sbiggest)
sbiggest = tmp;
}
dp[u] = wi[u];
if (biggest != -1 && sbiggest != -1)
gans = max(gans, wi[u] + biggest + sbiggest);
if (biggest != -1)
dp[u] += biggest;
gans = max(gans, dp[u]);
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &wi[i]), gans = max(gans, 1LL * wi[i]);
for (int i = 1, u, v, w; i <= n - 1; i++)
scanf("%d%d%d", &u, &v, &w), addpath(u, v, w), addpath(v, u, w);
dfs(1, 0), printf("%lld\n", gans);
return 0;
}
// CF1083A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5 + 200;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, current, head[MAX_N], wi[MAX_N];
ll dp[MAX_N], gans;
struct edge
{
int to, nxt, weight;
} edges[MAX_N << 1];
void addpath(int src, int dst, int weight)
{
edges[current].to = dst, edges[current].nxt = head[src];
edges[current].weight = weight, head[src] = current++;
}
void dfs(int u, int fa)
{
ll biggest = -1, sbiggest = -1;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa)
{
dfs(edges[i].to, u);
ll tmp = dp[edges[i].to] - edges[i].weight;
if (tmp > biggest)
swap(biggest, sbiggest), biggest = tmp;
else if (tmp > sbiggest)
sbiggest = tmp;
}
dp[u] = wi[u];
if (biggest != -1 && sbiggest != -1)
gans = max(gans, wi[u] + biggest + sbiggest);
if (biggest != -1)
dp[u] += biggest;
gans = max(gans, dp[u]);
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &wi[i]), gans = max(gans, 1LL * wi[i]);
for (int i = 1, u, v, w; i <= n - 1; i++)
scanf("%d%d%d", &u, &v, &w), addpath(u, v, w), addpath(v, u, w);
dfs(1, 0), printf("%lld\n", gans);
return 0;
}
// CF1083A.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 3e5 + 200; typedef long long ll; const ll INF = 0x3f3f3f3f3f3f3f3f; int n, current, head[MAX_N], wi[MAX_N]; ll dp[MAX_N], gans; struct edge { int to, nxt, weight; } edges[MAX_N << 1]; void addpath(int src, int dst, int weight) { edges[current].to = dst, edges[current].nxt = head[src]; edges[current].weight = weight, head[src] = current++; } void dfs(int u, int fa) { ll biggest = -1, sbiggest = -1; for (int i = head[u]; i != -1; i = edges[i].nxt) if (edges[i].to != fa) { dfs(edges[i].to, u); ll tmp = dp[edges[i].to] - edges[i].weight; if (tmp > biggest) swap(biggest, sbiggest), biggest = tmp; else if (tmp > sbiggest) sbiggest = tmp; } dp[u] = wi[u]; if (biggest != -1 && sbiggest != -1) gans = max(gans, wi[u] + biggest + sbiggest); if (biggest != -1) dp[u] += biggest; gans = max(gans, dp[u]); } int main() { memset(head, -1, sizeof(head)); scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &wi[i]), gans = max(gans, 1LL * wi[i]); for (int i = 1, u, v, w; i <= n - 1; i++) scanf("%d%d%d", &u, &v, &w), addpath(u, v, w), addpath(v, u, w); dfs(1, 0), printf("%lld\n", gans); return 0; }
B – The Fair Nut and Strings
可以很容易发现这东西最后等于 Trie 树的节点个数,然后我们就可以利用 01 Trie 的性质,不停地扩充节点个数即可。
// CF1083B.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5e5 + 200;
typedef long long ll;
int n, k;
char S[MAX_N], T[MAX_N];
int main()
{
scanf("%d%d%s%s", &n, &k, S + 1, T + 1);
ll gans = 0, pans = 1;
for (int i = 1; i <= n; i++)
{
pans <<= 1;
if (S[i] == 'b')
pans--;
if (T[i] == 'a')
pans--;
if (pans >= k)
{
gans += 1LL * k * (n - i + 1);
break;
}
gans += pans;
}
printf("%lld\n", gans);
return 0;
}
// CF1083B.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5e5 + 200;
typedef long long ll;
int n, k;
char S[MAX_N], T[MAX_N];
int main()
{
scanf("%d%d%s%s", &n, &k, S + 1, T + 1);
ll gans = 0, pans = 1;
for (int i = 1; i <= n; i++)
{
pans <<= 1;
if (S[i] == 'b')
pans--;
if (T[i] == 'a')
pans--;
if (pans >= k)
{
gans += 1LL * k * (n - i + 1);
break;
}
gans += pans;
}
printf("%lld\n", gans);
return 0;
}
// CF1083B.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 5e5 + 200; typedef long long ll; int n, k; char S[MAX_N], T[MAX_N]; int main() { scanf("%d%d%s%s", &n, &k, S + 1, T + 1); ll gans = 0, pans = 1; for (int i = 1; i <= n; i++) { pans <<= 1; if (S[i] == 'b') pans--; if (T[i] == 'a') pans--; if (pans >= k) { gans += 1LL * k * (n - i + 1); break; } gans += pans; } printf("%lld\n", gans); return 0; }
C – Max Mex
我们可以搞一颗线段树,关键字为 mex 值。这颗线段树需要维护每一个 mex 区间所能代表的路径。这个东西可以通过 LCA + 深度判断进行操作。询问和修改直接在线段树上做正常操作即可。
// CF1083C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 4e5 + 200;
int n, q, head[MAX_N], current, dep[MAX_N], st[20][MAX_N], wi[MAX_N], ptot, up[MAX_N], pos[MAX_N], log2_[MAX_N], bucket[MAX_N];
struct edge
{
int to, nxt;
} edges[MAX_N << 1];
struct node
{
int u, v;
} nodes[MAX_N << 2];
char nc()
{
static char buffer[1 << 20], *p1, *p2;
return p1 == p2 && (p2 = (p1 = buffer) + fread(buffer, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
int read()
{
int x = 0, f = 1;
char c = nc();
while (!isdigit(c))
f = (c == '-' ? -1 : f), c = nc();
while (isdigit(c))
x = (x << 3) + (x << 1) + c - '0', c = nc();
return x * f;
}
void addpath(int src, int dst)
{
edges[current].to = dst, edges[current].nxt = head[src];
head[src] = current++;
}
void dfs(int u)
{
dep[u] = dep[up[u]] + 1, st[0][++ptot] = u, pos[u] = ptot;
for (int i = head[u]; i != -1; i = edges[i].nxt)
dfs(edges[i].to), st[0][++ptot] = u;
}
int getLCA(int x, int y)
{
if (pos[x] > pos[y])
swap(x, y);
int len = pos[y] - pos[x] + 1, d = log2_[len];
int lft = st[d][pos[x]], rig = st[d][pos[y] - (1 << d) + 1];
return dep[lft] < dep[rig] ? lft : rig;
}
int getDist(int x, int y) { return dep[x] + dep[y] - (dep[getLCA(x, y)] << 1); }
node mergeNode(node u, int w)
{
if (u.u == -1 || w == -1)
return node{-1, -1};
int d1 = getDist(u.u, u.v), d2 = getDist(u.u, w), d3 = getDist(u.v, w);
return d1 == d2 + d3 ? u : ((d1 + d3 == d2) ? node{u.u, w} : (d1 + d2 == d3 ? node{u.v, w} : node{-1, -1}));
}
node pushup(node lson, node rson) { return mergeNode(mergeNode(lson, rson.u), rson.v); }
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)
void build(int l, int r, int p)
{
if (l == r)
return (void)(nodes[p] = node{bucket[l], bucket[l]});
build(l, mid, lson), build(mid + 1, r, rson);
nodes[p] = pushup(nodes[lson], nodes[rson]);
}
void update(int qx, int l, int r, int p)
{
if (l == r)
return (void)(nodes[p] = node{bucket[l], bucket[l]});
if (qx <= mid)
update(qx, l, mid, lson);
else
update(qx, mid + 1, r, rson);
nodes[p] = pushup(nodes[lson], nodes[rson]);
}
int query(node &tmp, int l, int r, int p)
{
if (nodes[p].u != -1)
{
if (tmp.u == -1)
return tmp = nodes[p], r + 1;
node curt = pushup(tmp, nodes[p]);
if (curt.u != -1)
return tmp = curt, r + 1;
}
if (l == r)
return l;
int ls = query(tmp, l, mid, lson);
if (ls <= mid)
return ls;
else
return query(tmp, mid + 1, r, rson);
}
#undef mid
#undef rson
#undef lson
int main()
{
memset(head, -1, sizeof(head)), n = read();
for (int i = 1; i <= n; i++)
wi[i] = read(), bucket[wi[i]] = i;
for (int i = 2; i <= n; i++)
up[i] = read(), addpath(up[i], i);
dfs(1);
for (int i = 1; i < 20; i++)
for (int j = 1; j + (1 << i) - 1 <= ptot; j++)
st[i][j] = (dep[st[i - 1][j]] < dep[st[i - 1][j + (1 << (i - 1))]]) ? st[i - 1][j] : st[i - 1][j + (1 << (i - 1))];
for (int i = 2; i <= ptot; i++)
log2_[i] = (log2_[i >> 1] + 1);
build(0, n - 1, 1), q = read();
while (q--)
{
int opt = read(), u, v;
if (opt == 1)
{
u = read(), v = read(), swap(bucket[wi[u]], bucket[wi[v]]), swap(wi[u], wi[v]);
update(wi[u], 0, n - 1, 1), update(wi[v], 0, n - 1, 1);
}
else
{
node tmp = node{-1, -1};
printf("%d\n", query(tmp, 0, n - 1, 1));
}
}
return 0;
}
// CF1083C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 4e5 + 200;
int n, q, head[MAX_N], current, dep[MAX_N], st[20][MAX_N], wi[MAX_N], ptot, up[MAX_N], pos[MAX_N], log2_[MAX_N], bucket[MAX_N];
struct edge
{
int to, nxt;
} edges[MAX_N << 1];
struct node
{
int u, v;
} nodes[MAX_N << 2];
char nc()
{
static char buffer[1 << 20], *p1, *p2;
return p1 == p2 && (p2 = (p1 = buffer) + fread(buffer, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
int read()
{
int x = 0, f = 1;
char c = nc();
while (!isdigit(c))
f = (c == '-' ? -1 : f), c = nc();
while (isdigit(c))
x = (x << 3) + (x << 1) + c - '0', c = nc();
return x * f;
}
void addpath(int src, int dst)
{
edges[current].to = dst, edges[current].nxt = head[src];
head[src] = current++;
}
void dfs(int u)
{
dep[u] = dep[up[u]] + 1, st[0][++ptot] = u, pos[u] = ptot;
for (int i = head[u]; i != -1; i = edges[i].nxt)
dfs(edges[i].to), st[0][++ptot] = u;
}
int getLCA(int x, int y)
{
if (pos[x] > pos[y])
swap(x, y);
int len = pos[y] - pos[x] + 1, d = log2_[len];
int lft = st[d][pos[x]], rig = st[d][pos[y] - (1 << d) + 1];
return dep[lft] < dep[rig] ? lft : rig;
}
int getDist(int x, int y) { return dep[x] + dep[y] - (dep[getLCA(x, y)] << 1); }
node mergeNode(node u, int w)
{
if (u.u == -1 || w == -1)
return node{-1, -1};
int d1 = getDist(u.u, u.v), d2 = getDist(u.u, w), d3 = getDist(u.v, w);
return d1 == d2 + d3 ? u : ((d1 + d3 == d2) ? node{u.u, w} : (d1 + d2 == d3 ? node{u.v, w} : node{-1, -1}));
}
node pushup(node lson, node rson) { return mergeNode(mergeNode(lson, rson.u), rson.v); }
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)
void build(int l, int r, int p)
{
if (l == r)
return (void)(nodes[p] = node{bucket[l], bucket[l]});
build(l, mid, lson), build(mid + 1, r, rson);
nodes[p] = pushup(nodes[lson], nodes[rson]);
}
void update(int qx, int l, int r, int p)
{
if (l == r)
return (void)(nodes[p] = node{bucket[l], bucket[l]});
if (qx <= mid)
update(qx, l, mid, lson);
else
update(qx, mid + 1, r, rson);
nodes[p] = pushup(nodes[lson], nodes[rson]);
}
int query(node &tmp, int l, int r, int p)
{
if (nodes[p].u != -1)
{
if (tmp.u == -1)
return tmp = nodes[p], r + 1;
node curt = pushup(tmp, nodes[p]);
if (curt.u != -1)
return tmp = curt, r + 1;
}
if (l == r)
return l;
int ls = query(tmp, l, mid, lson);
if (ls <= mid)
return ls;
else
return query(tmp, mid + 1, r, rson);
}
#undef mid
#undef rson
#undef lson
int main()
{
memset(head, -1, sizeof(head)), n = read();
for (int i = 1; i <= n; i++)
wi[i] = read(), bucket[wi[i]] = i;
for (int i = 2; i <= n; i++)
up[i] = read(), addpath(up[i], i);
dfs(1);
for (int i = 1; i < 20; i++)
for (int j = 1; j + (1 << i) - 1 <= ptot; j++)
st[i][j] = (dep[st[i - 1][j]] < dep[st[i - 1][j + (1 << (i - 1))]]) ? st[i - 1][j] : st[i - 1][j + (1 << (i - 1))];
for (int i = 2; i <= ptot; i++)
log2_[i] = (log2_[i >> 1] + 1);
build(0, n - 1, 1), q = read();
while (q--)
{
int opt = read(), u, v;
if (opt == 1)
{
u = read(), v = read(), swap(bucket[wi[u]], bucket[wi[v]]), swap(wi[u], wi[v]);
update(wi[u], 0, n - 1, 1), update(wi[v], 0, n - 1, 1);
}
else
{
node tmp = node{-1, -1};
printf("%d\n", query(tmp, 0, n - 1, 1));
}
}
return 0;
}
// CF1083C.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 4e5 + 200; int n, q, head[MAX_N], current, dep[MAX_N], st[20][MAX_N], wi[MAX_N], ptot, up[MAX_N], pos[MAX_N], log2_[MAX_N], bucket[MAX_N]; struct edge { int to, nxt; } edges[MAX_N << 1]; struct node { int u, v; } nodes[MAX_N << 2]; char nc() { static char buffer[1 << 20], *p1, *p2; return p1 == p2 && (p2 = (p1 = buffer) + fread(buffer, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++; } int read() { int x = 0, f = 1; char c = nc(); while (!isdigit(c)) f = (c == '-' ? -1 : f), c = nc(); while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = nc(); return x * f; } void addpath(int src, int dst) { edges[current].to = dst, edges[current].nxt = head[src]; head[src] = current++; } void dfs(int u) { dep[u] = dep[up[u]] + 1, st[0][++ptot] = u, pos[u] = ptot; for (int i = head[u]; i != -1; i = edges[i].nxt) dfs(edges[i].to), st[0][++ptot] = u; } int getLCA(int x, int y) { if (pos[x] > pos[y]) swap(x, y); int len = pos[y] - pos[x] + 1, d = log2_[len]; int lft = st[d][pos[x]], rig = st[d][pos[y] - (1 << d) + 1]; return dep[lft] < dep[rig] ? lft : rig; } int getDist(int x, int y) { return dep[x] + dep[y] - (dep[getLCA(x, y)] << 1); } node mergeNode(node u, int w) { if (u.u == -1 || w == -1) return node{-1, -1}; int d1 = getDist(u.u, u.v), d2 = getDist(u.u, w), d3 = getDist(u.v, w); return d1 == d2 + d3 ? u : ((d1 + d3 == d2) ? node{u.u, w} : (d1 + d2 == d3 ? node{u.v, w} : node{-1, -1})); } node pushup(node lson, node rson) { return mergeNode(mergeNode(lson, rson.u), rson.v); } #define lson (p << 1) #define rson ((p << 1) | 1) #define mid ((l + r) >> 1) void build(int l, int r, int p) { if (l == r) return (void)(nodes[p] = node{bucket[l], bucket[l]}); build(l, mid, lson), build(mid + 1, r, rson); nodes[p] = pushup(nodes[lson], nodes[rson]); } void update(int qx, int l, int r, int p) { if (l == r) return (void)(nodes[p] = node{bucket[l], bucket[l]}); if (qx <= mid) update(qx, l, mid, lson); else update(qx, mid + 1, r, rson); nodes[p] = pushup(nodes[lson], nodes[rson]); } int query(node &tmp, int l, int r, int p) { if (nodes[p].u != -1) { if (tmp.u == -1) return tmp = nodes[p], r + 1; node curt = pushup(tmp, nodes[p]); if (curt.u != -1) return tmp = curt, r + 1; } if (l == r) return l; int ls = query(tmp, l, mid, lson); if (ls <= mid) return ls; else return query(tmp, mid + 1, r, rson); } #undef mid #undef rson #undef lson int main() { memset(head, -1, sizeof(head)), n = read(); for (int i = 1; i <= n; i++) wi[i] = read(), bucket[wi[i]] = i; for (int i = 2; i <= n; i++) up[i] = read(), addpath(up[i], i); dfs(1); for (int i = 1; i < 20; i++) for (int j = 1; j + (1 << i) - 1 <= ptot; j++) st[i][j] = (dep[st[i - 1][j]] < dep[st[i - 1][j + (1 << (i - 1))]]) ? st[i - 1][j] : st[i - 1][j + (1 << (i - 1))]; for (int i = 2; i <= ptot; i++) log2_[i] = (log2_[i >> 1] + 1); build(0, n - 1, 1), q = read(); while (q--) { int opt = read(), u, v; if (opt == 1) { u = read(), v = read(), swap(bucket[wi[u]], bucket[wi[v]]), swap(wi[u], wi[v]); update(wi[u], 0, n - 1, 1), update(wi[v], 0, n - 1, 1); } else { node tmp = node{-1, -1}; printf("%d\n", query(tmp, 0, n - 1, 1)); } } return 0; }
E – The Fair Nut and Rectangles
首先有性质:矩形不会互相包含。也就是意味着随着 x 增大,y是单调递减的。我们可以设计出一个很 SB 的方程:
dp[i] = \max_{j \in [1, i)} \{ dp[j] + S_i – S_i \cap S_j – a_i \}
设计出来之后,发现 S_i \cap S_j 随着 j 的递增而增大,所以上斜率优化即可。
// CF1083E.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200;
const double eps = 1e-10;
typedef pair<int, int> pii;
typedef long long ll;
int n, q[MAX_N];
ll gans, f[MAX_N];
struct node
{
ll x, y, cost;
bool operator<(const node &rhs) const { return y > rhs.y; }
} nodes[MAX_N];
double X(int i) { return nodes[i].x; }
double Y(int i) { return f[i]; }
double slope(int i, int j) { return fabs(X(j) - X(i)) < eps ? 1e10 : double(Y(j) - Y(i)) / double(X(j) - X(i)); }
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lld%lld%lld", &nodes[i].x, &nodes[i].y, &nodes[i].cost);
sort(nodes + 1, nodes + 1 + n);
int head = 0, tail = 0;
for (int i = 1; i <= n; i++)
{
while (head < tail && slope(q[head], q[head + 1]) >= nodes[i].y)
head++;
f[i] = 1LL * nodes[i].x * nodes[i].y - nodes[i].cost;
if (head <= tail)
f[i] = max(f[i], f[q[head]] + 1LL * (nodes[i].x - nodes[q[head]].x) * nodes[i].y - nodes[i].cost);
gans = max(gans, f[i]);
while (head < tail && slope(q[tail - 1], q[tail]) <= slope(q[tail], i))
tail--;
q[++tail] = i;
}
printf("%lld\n", gans);
return 0;
}
// CF1083E.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200;
const double eps = 1e-10;
typedef pair<int, int> pii;
typedef long long ll;
int n, q[MAX_N];
ll gans, f[MAX_N];
struct node
{
ll x, y, cost;
bool operator<(const node &rhs) const { return y > rhs.y; }
} nodes[MAX_N];
double X(int i) { return nodes[i].x; }
double Y(int i) { return f[i]; }
double slope(int i, int j) { return fabs(X(j) - X(i)) < eps ? 1e10 : double(Y(j) - Y(i)) / double(X(j) - X(i)); }
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lld%lld%lld", &nodes[i].x, &nodes[i].y, &nodes[i].cost);
sort(nodes + 1, nodes + 1 + n);
int head = 0, tail = 0;
for (int i = 1; i <= n; i++)
{
while (head < tail && slope(q[head], q[head + 1]) >= nodes[i].y)
head++;
f[i] = 1LL * nodes[i].x * nodes[i].y - nodes[i].cost;
if (head <= tail)
f[i] = max(f[i], f[q[head]] + 1LL * (nodes[i].x - nodes[q[head]].x) * nodes[i].y - nodes[i].cost);
gans = max(gans, f[i]);
while (head < tail && slope(q[tail - 1], q[tail]) <= slope(q[tail], i))
tail--;
q[++tail] = i;
}
printf("%lld\n", gans);
return 0;
}
// CF1083E.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 1e6 + 200; const double eps = 1e-10; typedef pair<int, int> pii; typedef long long ll; int n, q[MAX_N]; ll gans, f[MAX_N]; struct node { ll x, y, cost; bool operator<(const node &rhs) const { return y > rhs.y; } } nodes[MAX_N]; double X(int i) { return nodes[i].x; } double Y(int i) { return f[i]; } double slope(int i, int j) { return fabs(X(j) - X(i)) < eps ? 1e10 : double(Y(j) - Y(i)) / double(X(j) - X(i)); } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%lld%lld%lld", &nodes[i].x, &nodes[i].y, &nodes[i].cost); sort(nodes + 1, nodes + 1 + n); int head = 0, tail = 0; for (int i = 1; i <= n; i++) { while (head < tail && slope(q[head], q[head + 1]) >= nodes[i].y) head++; f[i] = 1LL * nodes[i].x * nodes[i].y - nodes[i].cost; if (head <= tail) f[i] = max(f[i], f[q[head]] + 1LL * (nodes[i].x - nodes[q[head]].x) * nodes[i].y - nodes[i].cost); gans = max(gans, f[i]); while (head < tail && slope(q[tail - 1], q[tail]) <= slope(q[tail], i)) tail--; q[++tail] = i; } printf("%lld\n", gans); return 0; }