## 题目描述

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


## 题目描述

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.

• 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
}
}
return 0;
}


## 题目描述

There is an equation $ax+by+c=0$. Given $a,b,c,x_1,x_2,y_1,y_2$ you must determine, how many integer roots of this equation are satisfy to the following conditions: $x_1 \le x \le x_2, \; y_1 \le y \le y_2$. Integer root of this equation is a pair of integer numbers $(x,y)$.

## 代码

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

#define int long long

using namespace std;

namespace std {
template <typename T>
void maxify(T &a, T b) { b > a && (a = b); }
template <typename T>
void minify(T &a, T 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 Solver {
private:
int a, b, c, x1, x2, y1, y2, x, y, gcd;
void input() { io > a > b > c > x1 > x2 > y1 > y2; }
int ex_gcd(int a, int b, int &x, int &y) {
if (! b) { x = 1, y = 0; return a; }
int ret = ex_gcd(b, a % b, y, x); y -= a / b * x; return ret;
}
void process() {
if (! b) swap(a, b), swap(x1, y1), swap(x2, y2);
if (! b) {
if (c) io < 0 < '\n';
else io < (x2 - x1 + 1) * (y2 - y1 + 1) < '\n';
return;
}
gcd = ex_gcd(a, b, x, y);
if (c % gcd) { io < 0 < '\n'; return; }
a /= gcd, b /= gcd, c /= gcd, x *= -c, y *= -c;
if (b < 0) b = -b, a = -a;
x += 1000000000 * b, y -= 1000000000 * a;
y += ((x - x1) / b + 1) * a, x -= ((x - x1) / b + 1) * b;
x += b, y -= a;
if (x > x2) { io < 0 < '\n'; return; }
int ans = (x2 - x) / b + 1;
if (! a) {
if (y < y1 || y > y2) ans = 0;
} else {
int l = -1000000000, r = 1000000000, cnt = 0;
while (l + 1 < r) {
int mid = l + r >> 1;
if (y - a * mid < y1) if (a > 0) r = mid; else l = mid;
else if (a < 0) r = mid; else l = mid;
}
if (a < 0 && y - a * l == y1) -- l, -- r;
if (a > 0 && y - a * r == y1) ++ r, ++ l;
int l1 = l, r1 = r; l = -1000000000, r = 1000000000;
while (l + 1 < r) {
int mid = l + r >> 1;
if (y - a * mid < y2) if (a > 0) r = mid; else l = mid;
else if (a < 0) r = mid; else l = mid;
}
if (a < 0 && y - a * r == y2) ++ r, ++ l;
if (a > 0 && y - a * l == y2) -- l, -- r;
if (l > l1) swap(l, l1), swap(r, r1);
maxify(r, 0ll), minify(l1, ans - 1);
ans = l1 - r + 1;
}
io < ans < '\n';
}

public:
void solve() { input(), process(); }
} solver;

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


## 题目描述

$n$ people are standing on a coordinate axis in points with positive integer coordinates strictly less than $10^6$. For each person we know in which direction (left or right) he is facing, and his maximum speed.
You can put a bomb in some point with non-negative integer coordinate, and blow it up. At this moment all people will start running with their maximum speed in the direction they are facing. Also, two strange rays will start propagating from the bomb with speed $s$: one to the right, and one to the left. Of course, the speed $s$ is strictly greater than people’s maximum speed.
The rays are strange because if at any moment the position and the direction of movement of some ray and some person coincide, then the speed of the person immediately increases by the speed of the ray.
You need to place the bomb is such a point that the minimum time moment in which there is a person that has run through point $0$, and there is a person that has run through point $10^6$, is as small as possible. In other words, find the minimum time moment $t$ such that there is a point you can place the bomb to so that at time moment $t$ some person has run through $0$, and some person has run through point $10^6$.

## 代码

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
const double eps = 1e-10;
long long n, s;
long long x[100001], v[100001], t[100001];
double l, r;
bool check(double p) {
bool flag1 = false, flag2 = false;
for (int i = 1; i <= n; ++i)
if (t[i] == 1 && 1.0 * x[i] / v[i] <= p) flag1 = true;
else if (t[i] == 2 && (1e6 - x[i]) / v[i] <= p) flag2 = true;
if (flag1 && flag2) return true;
if (flag1) {
for (int i = 1; i <= n; ++i)
if (t[i] == 2 && (1e6 - x[i]) / (s + v[i]) <= p) return true;
return false;
}
if (flag2) {
for (int i = 1; i <= n; ++i)
if (t[i] == 1 && 1.0 * x[i] / (s + v[i]) <= p) return true;
return false;
}
long long before = 0, after = 1e6;
for (int i = 1; i <= n; ++i)
if (t[i] == 1 && 1.0 * x[i] / v[i] > p && 1.0 * x[i] / (s + v[i]) <= p) after = min(after, x[i]);
else if (t[i] == 2 && (1e6 - x[i]) / v[i] > p && (1e6 - x[i]) / (s + v[i]) <= p) before = max(before, x[i]);
if (before < after) return false;
long long ma = -1e18, mi = 1e18;
for (int i = 1; i <= n; ++i)
if (t[i] == 1 && 1.0 * x[i] / v[i] > p && 1.0 * x[i] / (s + v[i]) <= p)
ma = max(ma, (long long) floor((x[i] * v[i] + p * (s + v[i]) * (s - v[i])) / s));
else if (t[i] == 2 && (1e6 - x[i]) / v[i] > p && (1e6 - x[i]) / (s + v[i]) <= p)
mi = min(mi, (long long) ceil((1e6 * (s - v[i]) + x[i] * v[i] - p * (s + v[i]) * (s - v[i])) / s));
return mi <= ma;
}
int main()
{
cin >> n >> s;
for (int i = 1; i <= n; ++i)
cin >> x[i] >> v[i] >> t[i];
l = 0, r = 1e6;
while (r - l > eps) {
double mid = (l + r) / 2;
if (!check(mid)) l = mid; else r = mid;
}
cout << setprecision(10) << fixed << l << endl;
return 0;
}


## 题目描述

One night, having had a hard day at work, Petya saw a nightmare. There was a binary search tree in the dream. But it was not the actual tree that scared Petya. The horrifying thing was that Petya couldn’t search for elements in this tree. Petya tried many times to choose key and look for it in the tree, and each time he arrived at a wrong place. Petya has been racking his brains for long, choosing keys many times, but the result was no better. But the moment before Petya would start to despair, he had an epiphany: every time he was looking for keys, the tree didn’t have the key, and occured exactly one mistake. “That’s not a problem!”, thought Petya. “Why not count the expectation value of an element, which is found when I search for the key”. The moment he was about to do just that, however, Petya suddenly woke up.
Thus, you are given a binary search tree, that is a tree containing some number written in the node. This number is called the node key. The number of children of every node of the tree is equal either to $0$ or to $2$. The nodes that have $0$ children are called leaves and the nodes that have $2$ children, are called inner. An inner node has the left child, that is the child whose key is less than the current node’s key, and the right child, whose key is more than the current node’s key. Also, a key of any node is strictly larger than all the keys of the left subtree of the node and strictly smaller than all the keys of the right subtree of the node.
Also you are given a set of search keys, all of which are distinct and differ from the node keys contained in the tree. For each key from the set its search in the tree is realised. The search is arranged like this: initially we are located in the tree root, if the key of the current node is larger that our search key, then we move to the left child of the node, otherwise we go to the right child of the node and the process is repeated. As it is guaranteed that the search key is not contained in the tree, the search will always finish in some leaf. The key lying in the leaf is declared the search result.
It is known for sure that during the search we make a mistake in comparing exactly once, that is we go the wrong way, but we won’t make any mistakes later. All possible mistakes are equiprobable, that is we should consider all such searches where exactly one mistake occurs. Your task is to find the expectation (the average value) of the search result for every search key, considering that exactly one mistake occurs in the search. That is, for a set of paths containing exactly one mistake in the given key search, you should count the average value of keys containing in the leaves of those paths.

## 代码

#include <cstdio>
#include <algorithm>
using namespace std;
struct node_type {
long long val, min, max, child[2];
} node[100001];
long long n, k, cnt, times, root, top, id[100001];
double ans[100001];
void dfs(long long t) {
if (!node[t].child[0]) {
node[t].min = node[t].max = node[t].val; return;
}
dfs(node[t].child[0]), dfs(node[t].child[1]);
node[t].min = node[node[t].child[0]].min, node[t].max = node[node[t].child[1]].max;
}
void find(long long t) {
if (!node[t].child[0]) {
id[top] = node[t].val, ans[top++] = 1.0 * cnt / times; return;
}
cnt += node[node[t].child[1]].min, ++times, find(node[t].child[0]), id[top++] = node[t].val;
cnt += node[node[t].child[0]].max - node[node[t].child[1]].min, find(node[t].child[1]);
cnt -= node[node[t].child[0]].max, --times;
}
int main()
{
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
long long a; scanf("%lld%lld", &a, &node[i].val);
if (a == -1) root = i;
else if (!node[a].child[0]) node[a].child[0] = i;
else {
node[a].child[1] = i;
if (node[node[a].child[0]].val > node[node[a].child[1]].val)
node[a].child[0] ^= node[a].child[1] ^= node[a].child[0] ^= node[a].child[1];
}
}
dfs(root), find(root), scanf("%lld", &k);
for (int i = top - 2; i >= 0; --i) if (!ans[i]) ans[i] = ans[i + 1];
while (k--) {
long long a, l = 0, r = top; scanf("%lld", &a);
while (l + 1 < r) {
long long mid = l + r >> 1; if (id[mid] < a) l = mid; else r = mid;
}
printf("%.10lf\n", ans[l]);
}
return 0;
}


## 题目描述

Ivan likes to learn different things about numbers, but he is especially interested in really big numbers. Ivan thinks that a positive integer number $x$ is really big if the difference between $x$ and the sum of its digits (in decimal representation) is not less than $s$. To prove that these numbers may have different special properties, he wants to know how rare (or not rare) they are – in fact, he needs to calculate the quantity of really big numbers that are not greater than $n$.
Ivan tried to do the calculations himself, but soon realized that it’s too difficult for him. So he asked you to help him in calculations.

## 算法分析

$$\overline{a_1a_2a_3 \ldots a_{t-1}a_t}$$

$$\overline{a_1a_2a_3 \ldots (a_{t-1}+1)0}$$
$g(x+1)=g(x)-8$。如果$a_{t-1}=9$，那么就再向前进位使$g(x+1)=g(x)-17$…易知$g(x+1) \le g(x)+1$。所以
\begin{align} f(x+1)-f(x)&=(x+1)-g(x+1)-(x-g(x)) \\ &=g(x)+1-g(x+1) \ge 0 \end{align}

## 代码

#include <iostream>
using namespace std;
long long n, s, l, r;
bool check(long long t) {
long long p = t, sum = 0;
while (p) {
sum += p % 10;
p /= 10;
}
if (t - sum < s) return false;
return true;
}
int main()
{
cin >> n >> s;
l = 0, r = n + 1;
while (l + 1 < r) {
long long mid = l + r >> 1;
if (!check(mid)) l = mid;
else r = mid;
}
cout << n - l << endl;
return 0;
}