## 题目描述

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;
}


## 题目描述

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)$$

## 代码

/*
*/

#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;
}


## 题目描述

I won’t feel lonely, nor will I be sorrowful… not before everything is buried.
A string of $n$ beads is left as the message of leaving. The beads are numbered from $1$ to $n$ from left to right, each having a shape numbered by integers between $1$ and $n$ inclusive. Some beads may have the same shapes.
The memory of a shape $x$ in a certain subsegment of beads, is defined to be the difference between the last position and the first position that shape $x$ appears in the segment. The memory of a subsegment is the sum of memories over all shapes that occur in it.
From time to time, shapes of beads change as well as the memories. Sometimes, the past secreted in subsegments are being recalled, and you are to find the memory for each of them.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>

#define int long long

using namespace std;

void maxify(int &a, int b) { b > a && (a = b); }
void minify(int &a, int b) { b < a && (a = b); }

struct IOManager {
template <typename T>
char c; bool flag = false; x = 0;
while (~ c && ! isdigit(c = getchar()) && c != '-') ;
c == '-' && (flag = true, c = getchar());
if (! ~ c) return false;
while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
return (flag && (x = -x), true);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
char c; int len = 0;
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
if (! ~ c) return 0;
while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
return (s[len] = '\0', len);
}
template <typename T>
inline IOManager operator > (T &x) {
}
template <typename T>
inline void write(T x) {
x < 0 && (putchar('-'), x = -x);
x > 9 && (write(x / 10), true);
putchar(x % 10 + '0');
}
inline void write(char c) {
putchar(c);
}
inline void write(char s[]) {
int pos = 0;
while (s[pos] != '\0') putchar(s[pos ++]);
}
template <typename T>
inline IOManager operator < (T x) {
write(x); return *this;
}
} io;

struct BinaryIndexedTree {
private:
static const int N = 200000;
int n, a[N];

public:
void init(int t) {
n = t, memset(a, 0, sizeof a);
}
void add(int p, int v) {
for (; p <= n; p += p & -p) a[p] += v;
}
int get(int p) {
int ret = 0;
for (; p; p -= p & -p) ret += a[p];
return ret;
}
};

struct Set {
private:
static const int N = 200000;
int a[N];
set <int> s[N];
set <int> :: iterator it;

public:
void modify(int p, int v) {
if (a[p]) s[a[p]].erase(p);
a[p] = v;
s[a[p]].insert(p);
}
int prev(int p) {
it = s[a[p]].find(p);
return it == s[a[p]].begin() ? *it : *(-- it);
}
int next(int p) {
it = ++ s[a[p]].find(p);
return it == s[a[p]].end() ? *(-- it) : *it;
}
};

#define MODIFY 1
#define QUERY 2

struct Solver {
private:
static const int N = 200000;
int n, m, numq, top, pos[N], pre[N], ans[N];
BinaryIndexedTree tree;
Set s;
struct Query {
int type, x, y, w, id;
bool operator < (const Query &q) const {
return x == q.x ? type < q.type : x < q.x;
}
} q[N << 2], tmp[N << 2];
void add_query(int type, int x, int y, int w, int id) {
q[++ numq] = (Query) { type, x, y, w, id };
}
void input() {
io > n > m;
for (int i = 2; i <= n + 1; ++ i) {
int t; io > t, s.modify(i, t);
int prev = s.prev(i);
add_query(MODIFY, prev, i, i - prev, 0);
}
for (int i = 1; i <= m; ++ i) {
int o; io > o;
if (o == 1) {
int p, x; io > p > x; ++ p;
int prev = s.prev(p), next = s.next(p);
if (prev < p) add_query(MODIFY, prev, p, prev - p, 0);
if (next > p) add_query(MODIFY, p, next, p - next, 0);
if (prev < p && next > p) add_query(MODIFY, prev, next, next - prev, 0);
s.modify(p, x);
prev = s.prev(p), next = s.next(p);
if (prev < p && next > p) add_query(MODIFY, prev, next, prev - next, 0);
if (prev < p) add_query(MODIFY, prev, p, p - prev, 0);
if (next > p) add_query(MODIFY, p, next, next - p, 0);
} else {
int l, r; io > l > r, ++ l, ++ r, ++ top;
add_query(QUERY, r, l - 1, -1, top);
add_query(QUERY, l - 1, r, -1, top);
add_query(QUERY, l - 1, l - 1, 1, top);
}
}
}
void process(int l, int r) {
if (l == r) return;
int mid = l + r >> 1;
process(l, mid), process(mid + 1, r);
int s = l, t = mid + 1, pnt = l;
while (s <= mid && t <= r) {
if (q[s] < q[t]) {
if (q[s].type == MODIFY) tree.add(q[s].y, q[s].w);
tmp[pnt ++] = q[s ++];
} else {
if (q[t].type == QUERY) ans[q[t].id] += q[t].w * tree.get(q[t].y);
tmp[pnt ++] = q[t ++];
}
}
while (t <= r) {
if (q[t].type == QUERY) ans[q[t].id] += q[t].w * tree.get(q[t].y);
tmp[pnt ++] = q[t ++];
}
for (int i = l; i < s; ++ i) if (q[i].type == MODIFY) tree.add(q[i].y, -q[i].w);
while (s <= mid) tmp[pnt ++] = q[s ++];
for (int i = l; i <= r; ++ i) q[i] = tmp[i];
}

public:
void solve() {
input(), tree.init(n + 1), process(1, numq);
for (int i = 1; i <= top; ++ i) io < ans[i] < '\n';
}
} solver;

signed main() {
solver.solve();
return 0;
}


## 题目描述

Rick and Morty want to find MR. PBH and they can’t do it alone. So they need of Mr. Meeseeks. They Have generated $n$ Mr. Meeseeks, standing in a line numbered from $1$ to $n$. Each of them has his own color. $i$-th Mr. Meeseeks’ color is $a_i$.
Rick and Morty are gathering their army and they want to divide Mr. Meeseeks into some squads. They don’t want their squads to be too colorful, so each squad should have Mr. Meeseeks of at most $k$ different colors. Also each squad should be a continuous subarray of Mr. Meeseeks in the line. Meaning that for each $1 \le i \le e \le j \le n$, if Mr. Meeseeks number $i$ and Mr. Meeseeks number $j$ are in the same squad then Mr. Meeseeks number $e$ should be in that same squad.
Also, each squad needs its own presidio, and building a presidio needs money, so they want the total number of squads to be minimized.
Rick and Morty haven’t finalized the exact value of $k$, so in order to choose it, for each $k$ between $1$ and $n$ (inclusive) need to know the minimum number of presidios needed.

## 代码1

#include <cstdio>
#include <cstring>
using namespace std;
int n, last, a[100001], c[100001], ans[100001];
int get(int t) {
memset(c, 0, sizeof(c));
int p = 0, q = 1, ret = 0;
while (q <= n) {
int cnt = 1; c[a[q]] = 1;
while (q < n) {
if (cnt < t || c[a[q + 1]]) {
cnt += !c[a[++q]], ++c[a[q]];
} else break;
}
while (p < q) --c[a[++p]];
++q, ++ret;
}
return ret;
}
void solve(int l, int r) {
if (l > r) return;
ans[l] = get(l), ans[r] = get(r);
if (ans[l] == ans[r]) {
for (int i = l + 1; i < r; ++i) ans[i] = ans[l];
return;
}
int mid = l + r >> 1;
solve(l + 1, mid), solve(mid + 1, r - 1);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
solve(1, n);
for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
printf("\n");
return 0;
}


## 代码2

#include <cstdio>
using namespace std;
struct node_type {
int val, child[2];
} node[4000001];
int n, tot, ans, a[100001], root[100001], pre[100001];
int insert_line(int root, int l, int r, int p, int val) {
if (l == r) {
node[++tot].val = node[root].val + val;
node[tot].child[0] = node[tot].child[1] = 0;
}
int mid = l + r >> 1, ch;
if (p <= mid) {
ch = insert_line(node[root].child[0], l, mid, p, val);
node[++tot].child[0] = ch, node[tot].child[1] = node[root].child[1];
} else {
ch = insert_line(node[root].child[1], mid + 1, r, p, val);
node[++tot].child[0] = node[root].child[0], node[tot].child[1] = ch;
}
node[tot].val = node[node[tot].child[0]].val + node[node[tot].child[1]].val;
}
int query(int root, int l, int r, int p) {
if (l == r) if (p >= node[root].val) return l; else return l + 1;
int mid = l + r >> 1;
if (p >= node[node[root].child[1]].val) return query(node[root].child[0], l, mid, p - node[node[root].child[1]].val);
else return query(node[root].child[1], mid + 1, r, p);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
pre[a[1]] = 1, root[1] = insert_line(0, 1, n, 1, 1);
for (int i = 2; i <= n; ++i) {
int rt = root[i - 1];
if (pre[a[i]]) rt = insert_line(rt, 1, n, pre[a[i]], -1);
pre[a[i]] = i, root[i] = insert_line(rt, 1, n, i, 1);
}
for (int i = 1; i <= n; ++i) {
if (ans != 1) {
ans = 0;
int l = n, r;
while (l) r = l, l = query(root[r], 1, n, i) - 1, ++ans;
}
printf("%d ", ans);
}
printf("\n");
return 0;
}


## 题目描述

You are given an array $a$ consisting of $n$ elements. The imbalance value of some subsegment of this array is the difference between the maximum and minimum element from this segment. The imbalance value of the array is the sum of imbalance values of all subsegments of this array.
For example, the imbalance value of array $[1, 4, 1]$ is $9$, because there are $6$ different subsegments of this array:

• $[1]$ (from index $1$ to index $1$), imbalance value is $0$;
• $[1, 4]$ (from index $1$ to index $2$), imbalance value is $3$;
• $[1, 4, 1]$ (from index $1$ to index $3$), imbalance value is $3$;
• $[4]$ (from index $2$ to index $2$), imbalance value is $0$;
• $[4, 1]$ (from index $2$ to index $3$), imbalance value is $3$;
• $[1]$ (from index $3$ to index $3$), imbalance value is $0$.

You have to determine the imbalance value of the array $a$.

## 题意概述

$$\sum_{1 \le i \le j \le n} (max_{i, j}-min_{i, j})$$

## 代码1

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct number {
long long num, id, rec;
} a[1000001];
bool cmp(number a, number b) {return a.num < b.num;}
long long n, fa[1000002], s[1000002], ans;
int get_fa(long long t) {
return t == fa[t] || fa[t] == 0 ? fa[t] : fa[t] = get_fa(fa[t]);
}
void process(int t) {
int i, j;
if (t == 1) i = 1, j = n + 1;
else i = n, j = 0;
for (; i != j; i += t) {
fa[a[i].id] = a[i].id;
s[a[i].id] = 1;
long long p = get_fa(a[i].id - 1), q = get_fa(a[i].id + 1);
a[i].rec = (s[p] + 1) * (s[q] + 1);
if (s[p]) {
s[p] += s[get_fa(a[i].id)];
fa[get_fa(a[i].id)] = p;
}
if (s[q]) {
s[q] += s[get_fa(a[i].id)];
fa[get_fa(a[i].id)] = q;
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i].num;
a[i].id = i;
}
sort(a + 1, a + n + 1, cmp);
process(1);
for (int i = 1; i <= n; ++i) {
ans += a[i].num * a[i].rec;
}
memset(fa, 0, sizeof(fa));
memset(s, 0, sizeof(s));
process(-1);
for (int i = 1; i <= n; ++i) {
ans -= a[i].num * a[i].rec;
}
cout << ans << endl;
return 0;
}


## 代码2

#include <iostream>
using namespace std;
long long n, a[1000001], l[1000001], r[1000001], ans;
void process(int t) {
for (int i = 1; i <= n; ++i) {
l[i] = r[i] = i;
}
for (int i = 2; i <= n; ++i) {
int now = i;
while (now > 1 && a[i] * t >= a[now - 1] * t) now = l[now - 1];
l[i] = now;
}
for (int i = n - 1; i; --i) {
int now = i;
while (now < n && a[i] * t > a[now + 1] * t) now = r[now + 1];
r[i] = now;
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
process(1);
for (int i = 1; i <= n; ++i) {
ans += a[i] * (i - l[i] + 1) * (r[i] - i + 1);
}
process(-1);
for (int i = 1; i <= n; ++i) {
ans -= a[i] * (i - l[i] + 1) * (r[i] - i + 1);
}
cout << ans << endl;
return 0;
}