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

Kyoya and Train

题目描述

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?

题意概述

有$n$座城市和$m$条铁路,第$i$条铁路从$a_i$号城市出发,到达$b_i$号城市,票价为$c_i$。某人要在$t$个单位时间内从$1$号城市到$n$号城市,如果超过时间就会被罚款$x$。已知每次搭乘第$i$条铁路有$p_{i, k}$的概率需要$k \; (1 \le k \le t)$个单位时间。求在采取最优策略的情况下总花费的期望。
数据范围:$2 \le n \le 50, \; 1 \le m \le 100, \; 1 \le t \le 20000, \; 0 \le x \le 10^6$。

算法分析

首先考虑最暴力的DP。令$f_{i, j}$表示当前时刻为$j$,在最优策略下从$i$号城市到$n$号城市的总花费的期望。那么
$$
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}
$$
第二部分中的$d_{i, n}$表示在只考虑铁路票价的情况下从$i$号城市到$n$号城市的最小花费(因为已经超时了,所以不如走总票价最少的路)。
这样做的复杂度是$O(mt^2)$的,需要对它进行优化。令
$$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)$$
对于$S$,它类似于卷积,可以将其中一部分翻转后用FFT求值;对于$f$,可以用CDQ分治,统计较大的$j$对较小的$j$的贡献。
具体来说,假设我们要计算$l \le j \le r$的$f_{i, j}$,令$mid=\lfloor {l+r \over 2} \rfloor$,那么先计算$mid \lt j \le r$的$f_{i, j}$,用这些来更新$l \le j \le mid$的$S_{e, j}$($m$条边分别用FFT更新,复杂度$O(m(r-l)\log (r-l))$),最后计算$l \le j \le mid$的$f_{i, j}$。当$l=r$时$f$可以直接由$S$得到。总复杂度降至$O(mt\log^2t)$。
实现时细节很多,要注意DP边界条件和FFT下标变换。

代码

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

Goodbye Souvenir

题目描述

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.

题意概述

给定一个长度为$n$的序列$a_i$,有$m$次操作。操作有两种:给定$p, x$,将第$p$个数修改成$x$;给定$l, r$,求$[l, r]$内每种数字的长度之和。某种数字长度的定义是该数字在区间内第一次出现的位置与最后一次出现的位置之差。
数据范围:$1 \le n, m \le 10^5, \; 1 \le a_i, x \le n$。

算法分析

设区间$[l, r]$中某种数字出现的位置为$p_1, p_2, \ldots, p_k$,显然这个数字对答案的贡献为$p_k-p_1=(p_2-p_1)+(p_3-p_2)+ \cdots +(p_k-p_{k-1})$。令$pre_i$表示在$i$之前离$i$最近的等于$a_i$的数的位置,那么贡献就是$(p_2-pre_2)+(p_3-pre_3)+ \cdots +(p_k-pre_k)$。我们把每个数$a_i$想像成二维空间中的一个点$(pre_i, i)$,它的权值是$i-pre_i$。那么问题就变成了求在矩形$(l, l)-(r, r)$中的点权之和。这可以用传说中的CDQ分治来解决。

代码

#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>
  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 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, r, 1, 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;
}

Till I Collapse

题目描述

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.

题意概述

给定一个长度为$n$的数列,第$i$个数为$a_i$。要求将它们分成若干连续段。对于所有$k \in [1, n]$,问至少分成多少段,使得每一段中数字的种类数不超过$k$。
数据范围:$1 \le a_i \le n \le 10^5$。

算法分析1

有个显然的贪心策略:每一段越长越好。
容易发现答案一定单调不递增。对于$i \le j$,如果$ans_i=ans_j$,那么$ans_i=ans_{i+1}=ans_{i+2}= \cdots =ans_j$。因此我们可以贪心$O(n)$计算出左端点和右端点的$ans$,若它们相等,则将这个区间中的$ans$全都赋成左端点的$ans$;否则,取区间中点,并递归处理左右两个区间。

代码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

建可持久化线段树,第$i$个节点上的线段树维护区间$[j, i]$中数字的种类数。当遇到一个前面已经出现过的数字时,就在前面出现的位置上减一,在当前位置上加一。枚举$k$,并依据上述贪心策略,即可得到答案。

代码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;
    return tot;
  }
  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;
  return tot;
}
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;
}

Imbalanced Array

题目描述

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

题意概述

给定一个长度为$n$的$a$数组,求
$$\sum_{1 \le i \le j \le n} (max_{i, j}-min_{i, j})$$
其中$max_{i, j}$表示$a_i, a_{i+1}, a_{i+2}, \ldots, a_j$中的最大值,$min_{i, j}$表示$a_i, a_{i+1}, a_{i+2}, \ldots, a_j$中的最小值。
数据范围:$1 \le n \le 10^6, \; 1 \le a_i \le 10^6$。

算法分析1

考虑对于第$i$个数$a_i$,设它作为最大值出现的次数为$mx_i$,作为最小值出现的次数为$mn_i$。那么$ans=\sum_{i=1}^n(mx_i-mn_i)a_i$。接下来的问题就变成了求$mx_i, mn_i$。
对于区间$[l, r]$,我们找出其中的最大(小)值,设为$a_j$,那么$a_j$在$[l, r]$上的$mx_i$($mn_i$)就等于$(j-l+1)(r-j+1)$。可以发现,求解区间$[l, j-1]$和$[j+1, r]$是这个问题的子问题,而且规模更小,可以递归求解。只需在开始时先将数组从大到小(从小到大)排序,令$l=1, r=n$,即可解决原问题。
在求解时可以倒过来思考,即从小到大(从大到小)枚举,并将连续的区间合并,用并查集维护。理论时间复杂度为$O(n\log n)$。

代码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

设$l_i, r_i$分别表示$a_i$作为区间$[l, r]$中的最大(小)值时,$l$的最小值和$r$的最大值。那么对于$a_i$来讲,$mx_i(mn_i)=(i-l_i+1)(r_i-i+1)$。$l_i, r_i$均可以$O(n)$维护(DP或单调栈),从而避免了排序。
注意到有多个数相等时会有重复计算的区间。根据容斥原理,在判断时应一边取等号一边不取等号。

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