Friendly Points

题目描述

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?

题意概述

给定平面上的$n$个点。定义一对点是友好点对当且仅当存在一个各边平行于坐标轴的矩形仅包含这两个点。一个点被一个矩形包含当且仅当该点在矩形内部或边界上。求有多少对友好点对。
数据范围:$1 \le n \le 10^5$。

算法分析

用CDQ分治,把平面上的问题转化为序列上的问题。将点分成上下两个部分,考虑属于不同部分的点对有多少,递归处理两个部分。
对$y$坐标分治,把两个部分中的点按$x$坐标从小到大排序,依次处理。假设处理到一个上半部分的点,当上半部分只有这个点时,下半部分可以与它构成友好点对的点的$y$坐标严格下降。因此我们可以对上半部分维护一个$y$坐标严格上升的单调栈,对下半部分维护一个$y$坐标严格下降的单调栈。在处理上半部分的某个点$p$时,用上半部分的单调栈找出$x$坐标最大的$y$坐标不大于它的点$q$,在下半部分的单调栈里二分出$x$坐标大于$q$的点有多少个,即是与$p$构成友好点对的点的个数。下半部分同理。
有一些细节:$y$坐标相同的点需放在同一部分,若某一部分中所有点的$y$坐标相同,则直接加上这一部分的答案,不递归处理;若有多个$x$坐标相同的点,上半部分只考虑$y$坐标最小的,下半部分只考虑$y$坐标最大的;两个部分中$x$坐标相同的点需同时处理。

代码

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

Dynamic Rankings

题目描述

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

题意概述

有一个长度为$N$的数列。有$M$次操作,每次操作询问数列第$i$项到第$j$项之间的第$k$小值,或者将第$i$项修改为$t$。
数据范围:$1 \le N \le 50000, \; 1 \le M \le 10000$。
内存限制:$32$M。

算法分析

对于这种询问区间第$k$小值的题目,很容易想到主席树。但由于主席树是一种类似前缀和的结构,一次修改操作需要修改$O(N)$棵线段树。这显然不是我们所希望的。
既然主席树类似前缀和,那么就可以借用维护前缀和的工具——树状数组。把树状数组的每个节点看成一棵线段树,这样一次修改操作就只需要修改$O(\log N)$棵线段树,时间复杂度为$O(\log^2N)$。而询问操作需要先把该询问在树状数组上用到的节点提取出来(有$O(\log N)$个),然后利用类似主席树的方法二分,时间复杂度也是$O(\log^2N)$。
但是!这题的内存限制非常小,接受不了$O((N+M)\log^2N)$的空间复杂度。再考虑主席树,它的空间复杂度是$O(N\log N)$的。因此可以对原序列建立静态的主席树,对修改操作利用树状数组维护,这样空间复杂度降至$O(N\log N+M\log^2N)$,可以通过。

代码

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

The Equation

题目描述

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

题意概述

求二元一次方程$ax+by+c=0$满足$x_1 \le x \le x_2 \land y_1 \le y \le y_2$的整数解的个数。
数据范围:$-10^8 \le a, b, c, x_1, x_2, y_1, y_2 \le 10^8$。

算法分析

先判断是否有解。若$a=b=0 \land c \neq 0 \lor (a, b) \nmid c$则无解。
之后我们计算出$g=(a, b)$,令$a’={a \over g}, \; b’={b \over g}, \; c’={c \over g}$,方程变为$a’x+b’y=-c’$,用扩展GCD求出它的一组解$(x, y)$,那么该方程的通解为$(x+kb’, y-ka’)$。
分别计算使$x, y$满足要求的$k$的范围,其交集的大小就是答案。在计算范围时可以二分查找。

代码

#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>
  inline bool read(T &x) {
    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);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline int read(char s[]) {
    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) {
    read(x); return *this;
  }
  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;
}

Strange Radiation

题目描述

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

题意概述

在一条数轴上有$n$个人,第$i$个人的位置是$x_i$,速度是$v_i$。每个人初始时都面朝数轴正方向或负方向。现在你可以在数轴某一整点上放置一个炸弹。炸弹爆炸后,所有人都会向他当前面朝的方向奔跑。同时,炸弹会从放置点向数轴正负两侧分别发射出一道激光,速度是$s$。当一道激光碰到一个运动方向相同的人时,这个人的速度会立刻加上$s$。求放置炸弹后,至少有一个人到达$0$且至少有一个人到达$10^6$的最小时间。
数据范围:$2 \le n \le 10^5, \; 0 \le x_i \le 10^6, \; 1 \le v_i \lt s \le 10^6$。

算法分析

答案的范围在$0$到$10^6$之间,考虑二分答案。对于一个时间$t$,分别考虑面向负方向和面向正方向的人。对于负方向的情况,如果某个人不用借助激光就能在时间$t$内到达$0$,则直接考虑正方向;如果某个人借助了激光仍无法在时间$t$内到达$0$,则跳过这个人;否则,计算出在这个人到达$0$的情况下炸弹位置的最大值。右边同理,但求的是最小值。这就相当于求出了若干区间,若它们的交为空,则$t$不满足要求。另外还要考虑炸弹的位置比一个面向负方向的人的位置小或比一个面向正方向的人的位置大的情况。

代码

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

Petya and Tree

题目描述

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.

题意概述

给定一棵包含$n$个节点的二叉搜索树,每个节点都有$0$个或$2$个儿子。如果一个节点有儿子,那么它左子树中的所有节点的值都严格小于这个节点,它右子树中的所有节点的值都严格大于这个节点。由于一些差错,这棵搜索树在查找一个值时总是会犯恰好一次错误——应该往左查找时却往右查找,应该往右查找时却往左查找。现有$k$个树中不存在的值待查找,求每一次查找得到的数的期望。
数据范围:$3 \le n \lt 10^5, \; 1 \le k \le 10^5$。

算法分析

很容易想到暴力的方法:先DFS预处理出每棵子树中的最大值和最小值,接着对于每一个待查找的值,直接在树中查找;若应该往左子树走,则将答案加上右子树中的最小值,否则加上左子树中的最大值,然后往正确的方向走。由于这并不是一棵平衡树,因此最坏情况的时间复杂度为$O(n^2)$。
搜索树中的数将数字划分成了$(n+1)$个区间。对于每一个区间而言,其答案都是一样的。因此,我们可以再进行一次DFS,处理出每个区间的答案。处理方法类似于暴力,但是搜索完一棵子树后需要回溯。最后查找$k$个数时,只需对每个数二分查找属于哪个区间,并输出那个区间的答案。

代码

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

Really Big Numbers

题目描述

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.

题意概述

问区间$[1, n]$中有多少个数$t$满足$t-sum_t \ge s$,其中$sum_t$表示$t$各位数字之和。
数据范围:$1 \le n, s \le 10^{18}$。

算法分析

定义函数$g(x)$表示$x$各位数字之和,$f(x)=x-g(x)$。可以发现$f(x)$在$N^*$上单调不递减。因此直接二分找出满足$f(x) \lt s$的$x$的最大值,再与$n$作差即可。
下面来证明$f(x)$在$N^*$上单调不递减。

将$x$表示成
$$\overline{a_1a_2a_3 \ldots a_{t-1}a_t}$$
研究$g(x)$的增减性。如果$a_t \lt 9$,那么$g(x+1)=g(x)+1$;否则,可以将$x+1$表示成
$$\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;
}