题目描述

Consider $n$ distinct points on a plane.
Two points from that set are said to be friends, when there exists a rectangle with sides parallel to coordinate axes that contains those two points and doesn’t contain any other point from the given set. A rectangle is said to contain a point if the point lies within the rectangle or on its border.
How many pairs of friends are there among the given points?

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 100005;
static int const MAX = 1000000001;
long long ans;
struct Point {
int x, y;
friend bool operator<(Point const &a, Point const &b) {
return a.x < b.x;
}
} p[N], s1[N], s2[N], tmp[N];

void calc(int l, int r) {
if (l == r)
return;
int mid = (l + r) >> 1, L = mid - 1, R = mid + 1;
for (; l <= L && p[L].y == p[mid].y; --L)
;
for (; R <= r && p[R].y == p[mid].y; ++R)
;
if (l > L && R > r) {
std::sort(p + l, p + r + 1);
return void(ans += r - l);
}
mid = l <= L ? L : R - 1;
int p1 = l, p2 = mid + 1, p3 = l, t1 = 0, t2 = 0;
calc(l, mid), calc(mid + 1, r);
for (; p1 <= mid && p2 <= r;) {
int x = std::min(p[p1].x, p[p2].x), mx = -MAX, mn = MAX;
for (; p1 <= mid && p[p1].x == x; tmp[p3++] = p[p1++])
mx = std::max(mx, p[p1].y);
for (; p2 <= r && p[p2].x == x; tmp[p3++] = p[p2++])
mn = std::min(mn, p[p2].y);
for (; t1 && s1[t1 - 1].y < mx; --t1)
;
for (; t2 && s2[t2 - 1].y > mn; --t2)
;
Point r1 = t1 ? s1[t1 - 1] : (Point){-MAX, 0}, r2 = t2 ? s2[t2 - 1] : (Point){-MAX, 0};
for (; t1 && s1[t1 - 1].y == mx; --t1)
;
for (; t2 && s2[t2 - 1].y == mn; --t2)
;
if (mx > -MAX)
ans += s2 + t2 - std::upper_bound(s2, s2 + t2, r1), s1[t1++] = (Point){x, mx};
if (mn < MAX)
ans += s1 + t1 - std::upper_bound(s1, s1 + t1, r2), s2[t2++] = (Point){x, mn};
}
for (; p1 <= mid;) {
int x = p[p1].x, mx = -MAX;
for (; p1 <= mid && p[p1].x == x; tmp[p3++] = p[p1++])
mx = std::max(mx, p[p1].y);
for (; t1 && s1[t1 - 1].y < mx; --t1)
;
Point r1 = t1 ? s1[t1 - 1] : (Point){-MAX, 0};
for (; t1 && s1[t1 - 1].y == mx; --t1)
;
ans += s2 + t2 - std::upper_bound(s2, s2 + t2, r1), s1[t1++] = (Point){x, mx};
}
for (; p2 <= r;) {
int x = p[p2].x, mn = MAX;
for (; p2 <= r && p[p2].x == x; tmp[p3++] = p[p2++])
mn = std::min(mn, p[p2].y);
for (; t2 && s2[t2 - 1].y > mn; --t2)
;
Point r2 = t2 ? s2[t2 - 1] : (Point){-MAX, 0};
for (; t2 && s2[t2 - 1].y == mn; --t2)
;
ans += s1 + t1 - std::upper_bound(s1, s1 + t1, r2), s2[t2++] = (Point){x, mn};
}
for (int i = l; i <= r; ++i)
p[i] = tmp[i];
}

int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d%d", &p[i].x, &p[i].y);
std::sort(p, p + n, [](Point const &a, Point const &b) { return a.y < b.y; });
calc(0, n - 1), printf("%I64d\n", ans);
return 0;
}


题目描述

Traveller Gregory is famous for his ability to always choose the shortest path for his journey. Ostap is a journalist who seeks for information about the recent Gregory’s trip. He managed to get the evidence that during this trip Gregory visited a number of cities. However, there is no information about the order in which they were visited, and no information about the starting city and the ending city of Gregory’s trip (the entire trip is (one of) the shortest path between these cities). Help Ostap to find any shortest path that contains all specified cities.
Country in which Gregory traveled consists of $n$ cities and $m$ undirected roads between them. For each road Ostap knows the time it takes to travel it, and the “shortest” word above is with respect to those times.
It is guaranteed that there exists some shortest path going through all specified cities.

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 100005;
int ne = 1, top, h[N], d[N], que[N], id[N], lst[N], pre[N], ans[N];
bool in[N], v[N];
struct Edge {
int u, v, w, nxt;
} e[N << 1];

void add_edge(int u, int v, int w) {
e[++ne] = (Edge){u, v, w, h[u]}, h[u] = ne;
e[++ne] = (Edge){v, u, w, h[v]}, h[v] = ne;
}

void spfa(int s) {
int qb = 0, qe = 1;
memset(d, 0x3f, sizeof d), d[s] = 0, que[0] = s, in[s] = 1;
for (; qb != qe;) {
int u = que[qb++];
in[u] = 0, qb == N && (qb = 0);
for (int i = h[u]; i; i = e[i].nxt)
if (d[e[i].v] > d[u] + e[i].w) {
d[e[i].v] = d[u] + e[i].w;
if (!in[e[i].v]) {
if (qb == qe || d[e[i].v] > d[que[qb]])
que[qe++] = e[i].v, in[e[i].v] = 1, qe == N && (qe = 0);
else
!~--qb && (qb = N - 1), que[qb] = e[i].v, in[e[i].v] = 1;
}
}
}
}

int main() {
int n, m, k, t;
scanf("%d%d", &n, &m);
for (int i = 1, u, v, w; i <= m; ++i)
scanf("%d%d%d", &u, &v, &w), add_edge(u, v, w);
scanf("%d%d", &k, &t), v[t] = 1, spfa(t);
int s = t;
for (int i = 2; i <= k; ++i)
scanf("%d", &t), v[t] = 1, d[s] < d[t] && (s = t);
spfa(s);
for (int i = 1; i <= n; ++i)
id[i] = i;
std::sort(id + 1, id + n + 1, [&](int const &i, int const &j) { return d[i] < d[j]; });
for (int i : id) {
lst[i] += v[i];
for (int j = h[i]; j; j = e[j].nxt)
if (d[e[j].v] == d[i] + e[j].w && lst[e[j].v] < lst[i])
lst[e[j].v] = lst[i], pre[e[j].v] = j;
}
for (int i = 1; i <= n; ++i)
if (lst[i] == k) {
for (int j = pre[i]; j; j = pre[e[j].u])
ans[top++] = j >> 1;
break;
}
printf("%d\n", top);
for (int i = 0; i < top; ++i)
printf("%d ", ans[i]);
puts("");
return 0;
}


题目描述

The main street of Berland’s capital is a segment with length $s$. The main street has traffic lights installed along it. The traffic lights have been functioning since time immemorial, cyclically changing colors from red to green and vice versa. Each traffic light can be described by four numbers $x_i, r_i, g_i, d_i$, which stand for:

• $x_i$ – the distance from the beginning of the street to the traffic light ($1 \le x_i \lt s$),
• $r_i$ – the duration of the red light illumination ($10 \le r_i \le 20$),
• $g_i$ – the duration of the green light illumination ($10 \le g_i \le 20$),
• $d_i$ – the minimum non-negative moment of time when the traffic light changes the light from green to red ($0 \le d_i \lt r_i+g_i$).

Each traffic light retains its light cycle from the ancient past.
The King of Berland asked the transport minister to customize the traffic lights according to a “green wave” principle. That means that if you start driving from the beginning of the street at the recommended speed, you can drive through the entire street without stopping, that is, you pass each traffic light when it has the green light on.
Now it is time to show the “green wave” to the King, but the work is not even started yet. You may assume that the King starts driving at the moment of time $0$ from the beginning of the street. So the minister decided to choose some speed $v_0$ and tell the king that the “green wave” works specifically for this speed. Moreover, they can switch any number of traffic lights to the “always green” mode. The minister’ aim is to ensure that if the King drives through the street at the recommended speed $v_0$ he encounters no red traffic light. Driving exactly at the moment when the colors are changed is not considered driving through the red light.
Any transport’s maximum speed is limited in Berland: it should not exceed $v_{\max}$. On the other hand, the King will be angry if the recommended speed is less than $v_{\min}$. Thus, the minister should choose such value of $v_0$, which satisfies the inequation $v_{\min} \le v_0 \le v_{\max}$.
Help the minister to find such $v_0$ value, that the number of traffic lights to switch to the “always green” mode is minimum. If $v_0$ is not uniquely defined, choose the maximum possible value of $v_0$.

代码

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>

static int const N = 20005;
static double const EPS = 1e-12;

int pm(double const &n) {
return fabs(n) < EPS ? 0 : n < 0 ? -1 : 1;
}

std::bitset<N> ans, cur;
struct Query {
int id, op;
double x;
friend bool operator<(Query const &a, Query const &b) {
return pm(a.x - b.x) ? !~pm(a.x - b.x) : a.op < b.op;
}
} itv[N * 100];

int main() {
int n, s, vmn, vmx, top = 0;
scanf("%d%d%d%d", &n, &s, &vmn, &vmx);
for (int i = 0, x, r, g, d; i < n; ++i) {
scanf("%d%d%d%d", &x, &r, &g, &d);
if (d > g) {
double l = 1. * x / (d - g);
itv[top++] = (Query){i, 1, l};
}
for (;; d += r + g) {
double l = 1. * x / (d + r), r = d ? 1. * x / d : 1e9;
if (pm(r - vmn) < 1) {
break;
}
if (pm(vmx - l) < 1) {
continue;
}
itv[top++] = (Query){i, 1, l}, itv[top++] = (Query){i, -1, r};
}
}
itv[top++] = (Query){n, 1, 0. + vmx};
std::sort(itv, itv + top);
int ac = n, cc = 0;
double vc = 0;
for (int i = 0; i < n; ++i) {
ans.set(i);
}
for (int i = 0; i < top && pm(itv[i].x - vmx) < 1; ++i) {
if (itv[i].op == 1) {
if (cc <= ac && pm(vmn - itv[i].x) < 1) {
ans = cur, ac = cc, vc = itv[i].x;
}
if (itv[i].id < n) {
cur.set(itv[i].id), ++cc;
}
} else {
cur.reset(itv[i].id), --cc;
}
}
printf("%.10lf\n%d\n", vc, ac);
for (int i = 0; i < n; ++i) {
if (ans.test(i)) {
printf("%d ", i + 1);
}
}
puts("");
return 0;
}


题目描述

Chess Championship is set up in the New Basyuki City. Two national teams, of Berland and Byteland, are going to have a match there. Each team is represented by $n$ players. The championship consists of $n$ games – in each game a pair of players from different teams meets. A game victory brings $1$ point to the team and a game defeat doesn’t add or subtract points.
The championship starts with the sortition – the process that determines opponent pairs. Each player from the first team plays with exactly one player from the second team (and vice versa).
A recent research conducted by Berland scientists showed that every player of either team is characterized by a single number – the level of his chess mastership. No two people among the $2n$ players play at the same level. Funny as it is, the game winner always is the player with the higher level.
The contest organizers received information that a high-ranking Berland official Mr. B. bet $100500$ burles on the victory of his team with a $k$ points gap. Immediately an unofficial “recommendation” came from very important people to “organize” the sortition so that the Berland team gets exactly $k$ points more than the Byteland team.
Write a program that finds the number of distinct sortition results after which Berland gets exactly $k$ points more than Byteland. Two sortitions are considered distinct if there is such player, that gets different opponents by the sortitions’ results.

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 505;
static int const MOD = 1000000009;
int f[2][N][N];
std::pair<int, int> a[N << 1];

int main() {
int n, k;
scanf("%d%d", &n, &k);
if ((n & 1) != (k & 1))
return puts("0"), 0;
for (int i = 0; i < n; ++i)
scanf("%d", &a[i].first);
for (int i = n; i < n << 1; ++i)
scanf("%d", &a[i].first), a[i].second = 1;
std::sort(a, a + (n << 1));
int cur = 0, s[2] = {0, 0};
f[0][0][0] = 1;
for (int i = 0; i < n << 1; ++i, cur ^= 1) {
for (int j = 0; j <= n; ++j)
for (int k = 0; j + k <= n; ++k)
if (f[cur][j][k]) {
(f[!cur][j][k] += f[cur][j][k]) %= MOD;
int c[2] = {s[0] - j - k, s[1] - j - k};
(f[!cur][j + !a[i].second][k + a[i].second] += 1ll * f[cur][j][k] * c[!a[i].second] % MOD) %= MOD;
f[cur][j][k] = 0;
}
++s[a[i].second];
}
printf("%d\n", f[cur][n + k >> 1][n - k >> 1]);
return 0;
}


题目描述

Gena and Petya love playing the following game with each other. There are $n$ piles of stones, the $i$-th pile contains $a_i$ stones. The players move in turns, Gena moves first. A player moves by choosing any non-empty pile and taking an arbitrary positive number of stones from it. If the move is impossible (that is, all piles are empty), then the game finishes and the current player is considered a loser.
Gena and Petya are the world famous experts in unusual games. We will assume that they play optimally.
Recently Petya started to notice that Gena wins too often. Petya decided that the problem is the unjust rules as Gena always gets to move first! To even their chances, Petya decided to cheat and take and hide some stones before the game begins. Since Petya does not want Gena to suspect anything, he will take the same number of stones $x$ from each pile. This number $x$ can be an arbitrary non-negative integer, strictly less that the minimum of $a_i$ values.
Your task is to find the number of distinct numbers $x$ such that Petya will win the game.

算法分析

Nim游戏后手胜利的条件是所有数的异或和为$0$。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

static int const N = 200005;
static int const M = 65;
int a[N], cnt[M], f[M][N], s[2][N];

signed main() {
int n;
scanf("%lld", &n);
for (int i = 0; i < n; ++i) {
scanf("%lld", a + i);
for (int j = 0; j < M; ++j)
cnt[j] += a[i] >> j & 1;
}
f[0][0] = 1;
for (int i = 0; i < M - 1; ++i) {
int c0 = n - cnt[i], c1 = cnt[i], c = 0;
for (int j = 0; j <= n; ++j) {
if (j)
if (a[j - 1] >> i & 1)
++c0, --c1;
else
--c0, ++c1, ++c;
if (!(c0 & 1))
f[i + 1][c + c0] += f[i][j];
if (!(c1 & 1))
f[i + 1][c] += f[i][j];
}
*s[0] = *s[1] = 0;
for (int j = 0; j < n; ++j)
s[a[j] >> i & 1][++*s[a[j] >> i & 1]] = a[j];
for (int j = 1; j <= *s[0]; ++j)
a[j - 1] = s[0][j];
for (int j = 1; j <= *s[1]; ++j)
a[*s[0] + j - 1] = s[1][j];
}
int sum = 0;
for (int i = 1; i < n; ++i)
sum ^= a[i] - a[0];
printf("%lld\n", f[M - 1][0] - (sum == 0));
return 0;
}


题目描述

Kyoya Ootori wants to take the train to get to school. There are $n$ train stations and $m$ one-way train lines going between various stations. Kyoya is currently at train station $1$, and the school is at station $n$. To take a train, he must pay for a ticket, and the train also takes a certain amount of time. However, the trains are not perfect and take random amounts of time to arrive at their destination. If Kyoya arrives at school strictly after $t$ time units, he will have to pay a fine of $x$.
Each train line is described by a ticket price, and a probability distribution on the time the train takes. More formally, train line $i$ has ticket cost $c_i$, and a probability distribution $p_{i, k}$ which denotes the probability that this train will take $k$ time units for all $1 \le k \le t$. Amounts of time that each of the trains used by Kyouya takes are mutually independent random values (moreover, if Kyoya travels along the same train more than once, it is possible for the train to take different amounts of time and those amounts are also independent one from another).
Kyoya wants to get to school by spending the least amount of money in expectation (for the ticket price plus possible fine for being late). Of course, Kyoya has an optimal plan for how to get to school, and every time he arrives at a train station, he may recalculate his plan based on how much time he has remaining. What is the expected cost that Kyoya will pay to get to school if he moves optimally?

算法分析

$$f_{i, j}= \begin{cases} \min(c_e+\sum_{k=1}^t p_{e, k} \cdot f_{b_e, j+k} \mid e \in [1, m] \land a_e=i), & i \lt n \land j \le t \\ d_{i, n}+x , & i \lt n \land j \gt t \\ 0, & i=n \land j \le t \\ x, & i=n \land j \gt t \end{cases}$$

$$S_{e, j}=\sum_{k=1}^t p_{e, k} \cdot f_{b_e, j+k}$$

$$f_{i, j}=\min(c_e+S_{e, j} \mid e \in [1, m] \land a_e=i)$$

代码

/*
* Your nature demands love and your happiness depends on it.
*/

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>

static int const N = 55;
static int const M = 105;
static int const T = 100000;
static double const PI = acos(-1);
int rev[T];

class Point {
public:
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
std::pair<double, double> pair() {
return std::make_pair(x, y);
}
friend Point operator+(Point const &a, Point const &b) {
return Point(a.x + b.x, a.y + b.y);
}
friend Point operator-(Point const &a, Point const &b) {
return Point(a.x - b.x, a.y - b.y);
}
friend Point operator*(Point const &a, Point const &b) {
return Point(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
Point operator/(double const &n) {
return Point(x / n, y / n);
}
} wn[T], A[T], B[T];

int init(int n) {
int m = n, l = 0;
for (n = 1; n <= m; n <<= 1, ++l)
;
for (int i = 1; i < n; ++i)
rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
for (int i = 0; i < n >> 1; ++i)
wn[i] = Point(cos(2 * PI / n * i), sin(2 * PI / n * i));
return n;
}

void fft(Point *a, int n, int inv = 0) {
for (int i = 0; i < n; ++i)
if (i < rev[i])
std::swap(a[i], a[rev[i]]);
for (int i = 1; i < n; i <<= 1)
for (int j = 0; j < n; j += i << 1)
for (int k = 0; k < i; ++k) {
Point x = a[j + k], y = wn[n / (i << 1) * k] * a[j + k + i];
a[j + k] = x + y, a[j + k + i] = x - y;
}
if (inv) {
std::reverse(a + 1, a + n);
for (int i = 0; i < n; ++i)
a[i] = a[i] / n;
}
}

int n, m, t, x, mp[N][N];
double p[M][T], s[M][T], f[N][T];
struct Line {
int a, b, c;
} li[M];

void update(int l, int r) {
int mid = l + r >> 1, len = init(r - l + r - mid - 2);
for (int i = 1; i <= m; ++i) {
for (int j = 0; j < len; ++j)
A[j] = B[j] = 0;
for (int j = mid + 1; j <= r; ++j)
A[j - mid - 1] = f[li[i].b][r - j + mid + 1];
for (int j = 1; j <= r - l; ++j)
B[j - 1] = p[i][j];
fft(A, len), fft(B, len);
for (int j = 0; j < len; ++j)
A[j] = A[j] * B[j];
fft(A, len, 1);
for (int j = l; j <= mid; ++j)
s[i][j] += A[r - j - 1].x;
}
}

void solve(int l, int r) {
if (l == r) {
for (int i = 1; i <= m; ++i)
f[li[i].a][l] = std::min(f[li[i].a][l], s[i][l] + li[i].c);
return;
}
int mid = l + r >> 1;
solve(mid + 1, r), update(l, r), solve(l, mid);
}

int main() {
scanf("%d%d%d%d", &n, &m, &t, &x);
memset(mp, 0x3f, sizeof mp);
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d", &li[i].a, &li[i].b, &li[i].c);
mp[li[i].a][li[i].b] = std::min(mp[li[i].a][li[i].b], li[i].c);
for (int j = 1; j <= t; ++j)
scanf("%lf", &p[i][j]), p[i][j] /= 100000;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k)
mp[j][k] = std::min(mp[j][k], mp[j][i] + mp[i][k]);
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= t << 1; ++j)
if (i == n)
if (j <= t)
f[i][j] = 0;
else
f[i][j] = x;
else
if (j <= t)
f[i][j] = 1e9;
else
f[i][j] = x + mp[i][n];
update(0, t << 1), solve(0, t), printf("%.8lf\n", f[1][0]);
return 0;
}


题目描述

It’s summer vocation now. After tedious milking, cows are tired and wish to take a holiday. So Farmer Carolina considers having a picnic beside the river. But there is a problem, not all the cows consider it’s a good idea! Some cows like to swim in West Lake, some prefer to have a dinner in Shangri-la, and others want to do something different. But in order to manage expediently, Carolina coerces all cows to have a picnic!
Farmer Carolina takes her $N$ cows to the destination, but she finds every cow’s degree of interest in this activity is so different that they all loss their interests. So she has to group them to different teams to make sure that every cow can go to a satisfied team. Considering about the security, she demands that there must be no less than $T$ cows in every team. As every cow has its own interest degree of this picnic, we measure this interest degree’s unit as “Moo~“. Cows in the same team should reduce their Moo~ to the one who has the lowest Moo~ in this team – It’s not a democratical action! So Carolina wishes to minimize the TOTAL reduced Moo~s and groups $N$ cows into several teams.
For example, Carolina has $7$ cows to picnic and their Moo~ are ‘$8 \; 5 \; 6 \; 2 \; 1 \; 7 \; 6$’ and at least $3$ cows in every team. So the best solution is that cow No. $2, 4, 5$ in a team (reduce $((2-1)+(5-1))$ Moo~) and cow No. $1, 3, 6, 7$ in a team (reduce $((7-6)+(8-6))$ Moo~), the answer is $8$.

算法分析

$$f_i=\min(f_j+(s_i-s_j)-(i-j)b_j \mid i-j \ge T)$$

\begin{align} f_j+(s_i-s_j)-(i-j)b_j &\le f_k+(s_i-s_k)-(i-k)b_k \\ (f_j-s_j+j \cdot b_j)-(f_k-s_k+k \cdot b_k) &\le i(b_j-b_k) \end{align}
$i$单调递增，因此可以斜率优化。但要注意两点：当$i-j \lt T$时$f_j$不能转移到$f_i$；当$i \lt T$时$f_i$没有意义。

代码

/*
* You attempt things that you do not even plan because of your extreme
* stupidity.
*/

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

static int const N = 400005;
int a[N], f[N], s[N], b[N], que[N];

int dety(int i, int j) {
return f[j] - s[j] + b[j] * j - (f[i] - s[i] + b[i] * i);
}

int detx(int i, int j) { return b[j] - b[i]; }

signed main() {
for (int n, k; ~scanf("%lld%lld", &n, &k);) {
for (int i = 1; i <= n; ++i)
scanf("%lld", &a[i]);
std::sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i)
s[i] = s[i - 1] + a[i], b[i - 1] = a[i];
int qb = 0, qe = 1;
que[0] = 0;
for (int i = 1; i <= n; ++i) {
for (; qb + 1 < qe &&
dety(que[qb], que[qb + 1]) <= i * detx(que[qb], que[qb + 1]);
++qb)
;
f[i] = f[que[qb]] + s[i] - s[que[qb]] - b[que[qb]] * (i - que[qb]);
if (i - k + 1 >= k) {
for (;
qb + 1 < qe &&
dety(que[qe - 2], que[qe - 1]) * detx(que[qe - 1], i - k + 1) >=
dety(que[qe - 1], i - k + 1) * detx(que[qe - 2], que[qe - 1]);
--qe)
;
que[qe++] = i - k + 1;
}
}
printf("%lld\n", f[n]);
}
return 0;
}


题目描述

Zero has an old printer that doesn’t work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero use a cost to evaluate this degree.
One day Zero want to print an article which has $N$ words, and each word $i$ has a cost $C_i$ to be printed. Also, Zero know that print $k$ words in one line will cost
$$\left(\sum_{i=1}^k C_i\right)^2+M$$
$M$ is a const number.
Now Zero want to know the minimum cost in order to arrange the article perfectly.

算法分析

$$f_i=\min(f_j+(s_i-s_j)^2+M)$$

$$f_j+(s_i-s_j)^2+M \le f_k+(s_i-s_k)^2+M$$

\begin{align} f_j-2s_is_j+s_j^2 &\le f_k-2s_is_k+s_k^2 \\ f_j+s_j^2-(f_k+s_k^2) &\le 2s_i(s_j-s_k) \\ {f_j+s_j^2-(f_k+s_k^2) \over 2s_j-2s_k} &\le s_i \end{align}

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 500005;
int a[N], s[N], f[N], que[N];

int detx(int i, int j) { return s[j] - s[i] << 1; }

int dety(int i, int j) { return f[j] + s[j] * s[j] - f[i] - s[i] * s[i]; }

int main() {
for (int n, m; ~scanf("%d%d", &n, &m);) {
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i)
s[i] = s[i - 1] + a[i];
int qb = 0, qe = 1;
for (int i = 1; i <= n; ++i) {
for (; qb + 1 < qe &&
dety(que[qb], que[qb + 1]) <= s[i] * detx(que[qb], que[qb + 1]);
++qb)
;
f[i] = f[que[qb]] + (s[i] - s[que[qb]]) * (s[i] - s[que[qb]]) + m;
for (; qb + 1 < qe &&
dety(que[qe - 2], que[qe - 1]) * detx(que[qe - 1], i) >=
dety(que[qe - 1], i) * detx(que[qe - 2], que[qe - 1]);
--qe)
;
que[qe++] = i;
}
printf("%d\n", f[n]);
}
return 0;
}


题目描述

The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the $k$-th smallest number of the given $N$ numbers. They have developed a more powerful system such that for $N$ numbers $a_1, a_2, \ldots, a_N$, you can ask it like: what is the $k$-th smallest number of $a_i, a_{i+1}, \ldots, a_j$? (For some $i \le j$, $0 \lt k \le j+1-i$ that you have given to it). More powerful, you can even change the value of some $a_i$, and continue to query, all the same.
Your task is to write a program for this computer, which

• Reads $N$ numbers from the input.
• Processes $M$ instructions of the input. These instructions include querying the $k$-th smallest number of $a_i, a_{i+1}, \ldots, a_j$ and change some $a_i$ to $t$.

代码

/*
* Beware of Bigfoot!
*/

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>

static int const N = 60005;
static int const NM = 2000000;
int n, m, nn, a[N], arr_rt[N], bit_rt[N], rec[N];
struct Query {
int o, i, j, k;
} q[N];
struct SegmentTree {
int ch[2], sum;
} nd[NM];

int create(int rt = 0) { return nd[++nn] = nd[rt], nn; }

int arr_insert(int rt, int p) {
rt = create(rt), ++nd[rt].sum;
int L = 0, R = N;
for (int cur = rt; L < R;) {
int MID = L + R >> 1, b = p > MID;
nd[cur].ch[b] = create(nd[cur].ch[b]), ++nd[nd[cur].ch[b]].sum,
cur = nd[cur].ch[b];
b ? L = MID + 1 : R = MID;
}
return rt;
}

void bit_insert(int &rt, int p, int v) {
if (rt == 0)
rt = create();
nd[rt].sum += v;
int L = 0, R = N;
for (int cur = rt; L < R;) {
int MID = L + R >> 1, b = p > MID;
if (nd[cur].ch[b] == 0)
nd[cur].ch[b] = create();
nd[nd[cur].ch[b]].sum += v;
int tmp = nd[cur].ch[b];
cur = tmp, b ? L = MID + 1 : R = MID;
}
}

int bit_add(int p, int v, int c) {
for (; p <= n; p += p & -p)
bit_insert(bit_rt[p], v, c);
}

int main() {
int T;
scanf("%d", &T);
for (; T--;) {
std::map<int, int> mp;
memset(arr_rt, nn = 0, sizeof arr_rt), memset(bit_rt, 0, sizeof bit_rt);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]), mp[a[i]] = 0;
for (int i = 1; i <= m; ++i) {
char c;
scanf(" %c", &c);
if (c == 'Q')
q[i].o = 0, scanf("%d%d%d", &q[i].i, &q[i].j, &q[i].k);
else
q[i].o = 1, scanf("%d%d", &q[i].i, &q[i].j), mp[q[i].j] = 0;
}
int cnt = 0;
for (std::map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it)
rec[cnt] = it->first, it->second = cnt++;
for (int i = 1; i <= n; ++i)
arr_rt[i] = arr_insert(arr_rt[i - 1], mp[a[i]]);
for (int i = 1; i <= m; ++i) {
if (q[i].o == 0) {
std::vector<int> a, b;
a.push_back(arr_rt[q[i].i - 1]), b.push_back(arr_rt[q[i].j]);
for (int p = q[i].i - 1; p; p -= p & -p)
a.push_back(bit_rt[p]);
for (int p = q[i].j; p; p -= p & -p)
b.push_back(bit_rt[p]);
int L = 0, R = N;
for (; L < R;) {
int sum = 0;
for (int i = 0; i < a.size(); ++i)
sum -= nd[nd[a[i]].ch[0]].sum;
for (int i = 0; i < b.size(); ++i)
sum += nd[nd[b[i]].ch[0]].sum;
int MID = L + R >> 1;
if (sum < q[i].k) {
L = MID + 1, q[i].k -= sum;
for (int i = 0; i < a.size(); ++i)
a[i] = nd[a[i]].ch[1];
for (int i = 0; i < b.size(); ++i)
b[i] = nd[b[i]].ch[1];
} else {
R = MID;
for (int i = 0; i < a.size(); ++i)
a[i] = nd[a[i]].ch[0];
for (int i = 0; i < b.size(); ++i)
b[i] = nd[b[i]].ch[0];
}
}
printf("%d\n", rec[L]);
} else
bit_add(q[i].i, mp[a[q[i].i]], -1),
bit_add(q[i].i, mp[a[q[i].i] = q[i].j], 1);
}
}
return 0;
}


代码

/*
* Computer programmers do it byte by byte.
*/

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

template <typename T> void read(T &n) {
char c;
for (; (c = getchar()) < '0' || c > '9';)
;
for (n = c - '0'; (c = getchar()) >= '0' && c <= '9'; (n *= 10) += c - '0')
;
}

typedef int const ic;

static ic N = 100005;

class heap {
private:
std::priority_queue<int> que, buf;

void clear() {
for (; !que.empty() && !buf.empty() && que.top() == buf.top();
que.pop(), buf.pop())
;
}

public:
void push(ic &n) {
if (n)
que.push(n);
}

void erase(ic &n) {
if (n)
buf.push(n);
}

void pop() {
clear();
if (!que.empty())
que.pop();
}

int top() {
clear();
return que.empty() ? 0 : que.top();
}

int top2() {
clear();
if (que.empty())
return 0;
int tmp = que.top(), ret = tmp;
que.pop(), clear();
if (que.empty()) {
que.push(tmp);
return 0;
}
ret += que.top(), que.push(tmp);
return ret;
}
} global;

namespace tree {
int n, nume, h[N], col[N];
int tim, fi[N], dep[N], lca[N << 1][20];
int power[N << 1];
int root, up[N], size[N], mx[N], vis[N];
heap toup[N], me[N];
struct Edge {
int v, nxt;
} e[N << 1];

void add_edge(ic &u, ic &v) {
e[++nume] = (Edge){v, h[u]}, h[u] = nume;
e[++nume] = (Edge){u, h[v]}, h[v] = nume;
}

void dfs(ic &t, ic &fa) {
lca[++tim][0] = t, fi[t] = tim, dep[t] = dep[fa] + 1;
for (int i = h[t]; i; i = e[i].nxt)
if (e[i].v != fa)
dfs(e[i].v, t), lca[++tim][0] = t;
}

void init() {
for (int i = 2; i <= tim; i <<= 1)
++power[i];
for (int i = 1; i <= tim; ++i)
power[i] += power[i - 1];
for (int i = 1; i < 20; ++i)
for (int j = 1; j <= tim; ++j) {
ic k = std::min(tim, j + (1 << i - 1));
lca[j][i] = dep[lca[j][i - 1]] < dep[lca[k][i - 1]] ? lca[j][i - 1]
: lca[k][i - 1];
}
}

int get_lca(ic &u, ic &v) {
ic l = std::min(fi[u], fi[v]), r = std::max(fi[u], fi[v]);
ic len = power[r - l + 1], k = r - (1 << len) + 1;
return dep[lca[l][len]] < dep[lca[k][len]] ? lca[l][len] : lca[k][len];
}

int get_dist(ic &u, ic &v) {
ic lca = get_lca(u, v);
return dep[u] + dep[v] - 2 * dep[lca];
}

int get_size(ic &t, ic &fa) {
int ret = 1;
for (int i = h[t]; i; i = e[i].nxt)
if (!vis[e[i].v] && e[i].v != fa)
ret += get_size(e[i].v, t);
return ret;
}

void get_root(ic &t, ic &fa, ic &tot) {
size[t] = 1, mx[t] = 0;
for (int i = h[t]; i; i = e[i].nxt)
if (!vis[e[i].v] && e[i].v != fa)
get_root(e[i].v, t, tot), size[t] += size[e[i].v],
mx[t] = std::max(mx[t], size[e[i].v]);
(mx[t] = std::max(mx[t], tot - size[t])) < mx[root] && (root = t);
}

void init_heap(ic &t, ic &fa, ic &dep, heap &hp) {
hp.push(dep);
for (int i = h[t]; i; i = e[i].nxt)
if (!vis[e[i].v] && e[i].v != fa)
init_heap(e[i].v, t, dep + 1, hp);
}

void build(int t) {
vis[t] = true;
for (int i = h[t]; i; i = e[i].nxt)
if (!vis[e[i].v])
root = 0,
get_root(e[i].v, 0,
size[e[i].v] < size[t] ? size[e[i].v] : get_size(e[i].v, t)),
up[root] = t, init_heap(e[i].v, t, 1, toup[root]),
me[t].push(toup[root].top()), build(root);
global.push(me[t].top()), global.push(me[t].top2());
}

void modify(int t) {
ic p = t;
if (col[t])
global.erase(me[t].top());
else
global.push(me[t].top());
for (; up[t]; t = up[t]) {
if (col[up[t]])
global.erase(me[up[t]].top());
global.erase(me[up[t]].top2());
me[up[t]].erase(toup[t].top());
if (col[p])
toup[t].erase(get_dist(p, up[t]));
else
toup[t].push(get_dist(p, up[t]));
me[up[t]].push(toup[t].top());
if (col[up[t]])
global.push(me[up[t]].top());
global.push(me[up[t]].top2());
}
col[p] = !col[p];
}
} // namespace tree

int main() {
read(tree::n), tree::mx[0] = tree::n;
for (int i = 1, u, v; i < tree::n; ++i)
read(u), read(v), tree::add_edge(u, v);
tree::dfs(1, 0), tree::init(), tree::get_root(1, 0, tree::n),
tree::build(tree::root);
for (int i = 1; i <= tree::n; ++i)
tree::col[i] = 1;
int q;
for (read(q); q--;) {
char c;
scanf(" %c", &c);
if (c == 'G')
printf("%d\n", global.top());
else {
int p;
read(p), tree::modify(p);
}
}
return 0;
}