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

Picnic Cows

题目描述

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

题意概述

有$N$头牛,每头牛有一个快乐值。要将牛分成若干组,使得每组至少有$T$头牛。分在一组中的牛的快乐值都会变成那组中最小的快乐值。求分组前后总快乐值之差的最小值。
数据范围:$1 \lt T \le N \le 4 \times 10^5$。

算法分析

将牛的快乐值$a_i$从小到大排序。根据贪心策略,一定存在最优分组方案是将排序后的牛分成若干连续段。
令$f_i$表示排序后前$i$头牛分组前后总快乐值之差的最小值,$s_i=\sum_{j=1}^i a_j$,$b_i=a_{i+1}$。可以得到转移方程
$$f_i=\min(f_j+(s_i-s_j)-(i-j)b_j \mid i-j \ge T)$$
假设$k \lt j \lt i$,且决策$j$比决策$k$更优,那么
$$
\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;
}

Print Article

题目描述

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.

题意概述

一篇文章中有$N$个单词,输入第$i$个单词的代价为$C_i$。将连续$k$个单词排在一行的总代价为$\left(\sum_{i=1}^k C_i\right)^2+M$。求输入这篇文章的最小代价。
数据范围:$0 \le N \le 5 \times 10^5, \; 0 \le M \le 1000$。

算法分析

令$f_i$表示输入前$i$个单词的最小代价,$s_i=\sum_{j=1}^i C_j$。考虑第$i$个单词的所在行,可以得到转移方程
$$f_i=\min(f_j+(s_i-s_j)^2+M)$$
假设$k \lt j \lt i$,且$j$这个决策更优,即
$$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}
$$
也就是说,在满足这个不等式时,对于状态$i$,决策$j$比决策$k$更优。
我们知道$s_i$单调不递减,即如果对于状态$i_0$,$k \lt j \lt i$且决策$j$更优,那么对于状态$i_1 \gt i_0$,决策$j$也一定更优,因此我们可以抛弃决策$k$。
对于每个$i$,假设平面中有点$(2s_i, f_i+s_i^2)$。对于不等式左侧这个东西,把它看成平面直角坐标系里直线的斜率。由于要最小化$f_i$,因此需要找到一个$k$使得不存在$k \lt j \lt i$满足不等式。可以发现我们只要用单调队列维护前$(i-1)$个点的下凸壳(斜率单调递增)。这样时间复杂度就是$O(N)$的了。

代码

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

排序

题意概述

给定一个$1$到$n$的全排列。有$m$次操作,每次操作将第$l$项到第$r$项之间的数按升序或降序排序。求所有操作完成后第$q$项的值。
数据范围:$1 \le n, m \le 10^5$。

算法分析

用set维护所有有序的区间,每个区间用一棵权值线段树来维护。这样就把排序操作变成了区间的分裂与合并(即线段树的分裂与合并)。
看起来线段树的复杂度很玄学,但可以大致证明一下:

初始时,线段树有$O(n\log n)$个节点。
分裂操作需要找到第$k$大的数,并把路径上的节点拆到两棵树上。一次分裂操作的时间复杂度为$O(\log n)$,新增节点数为$O(\log n)$。
合并操作每调用一次,都会删除一个节点。因此合并操作的总时间复杂度与最大点数相关,为$O((n+m)\log n)$。

由此得证。

代码

/*
 * Try to have as good a life as you can under the circumstances.
 */

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

static int const N = 100005;
static int const NM = 5000000;
int rt[N], top, buf[NM];
struct Interval {
  int l, r, ord;
  bool operator<(Interval const &a) const { return l < a.l; }
};
std::set<Interval> st;
struct SegmentTree {
  int ch[2], val, sum;
} nd[NM];

void update(int rt) {
  nd[rt].sum = nd[nd[rt].ch[0]].sum + nd[rt].val + nd[nd[rt].ch[1]].sum;
}

void insert(int &rt, int nl, int nr, int p) {
  if (!rt)
    nd[rt = buf[--top]] = nd[0];
  if (nl == nr) {
    nd[rt].val = nd[rt].sum = 1;
    return;
  }
  int mid = nl + nr >> 1;
  if (p <= mid)
    insert(nd[rt].ch[0], nl, mid, p);
  else
    insert(nd[rt].ch[1], mid + 1, nr, p);
  update(rt);
}

void merge(int &p, int &q) {
  if (!p || !q) {
    p = p + q, q = 0;
    return;
  }
  merge(nd[p].ch[0], nd[q].ch[0]), merge(nd[p].ch[1], nd[q].ch[1]);
  buf[top++] = q, q = 0, update(p);
}

int split(int &rt, int k) {
  if (!rt || nd[rt].sum == k)
    return 0;
  if (!k) {
    int rec = rt;
    return rt = 0, rec;
  }
  if (nd[nd[rt].ch[0]].sum >= k) {
    int sp = buf[--top];
    nd[sp].ch[0] = split(nd[rt].ch[0], k), nd[sp].ch[1] = nd[rt].ch[1],
    nd[rt].ch[1] = 0;
    return update(rt), update(sp), sp;
  }
  int sp = buf[--top];
  nd[sp].ch[0] = 0,
  nd[sp].ch[1] = split(nd[rt].ch[1], k - nd[nd[rt].ch[0]].sum);
  return update(rt), update(sp), sp;
}

int query(int rt, int nl, int nr, int k) {
  if (nl == nr)
    return nl;
  int mid = nl + nr >> 1;
  if (nd[nd[rt].ch[0]].sum >= k)
    return query(nd[rt].ch[0], nl, mid, k);
  else
    return query(nd[rt].ch[1], mid + 1, nr, k - nd[nd[rt].ch[0]].sum);
}

int main() {
  for (int i = 1; i < NM; ++i)
    buf[top++] = i;
  int n, m, q;
  scanf("%d%d", &n, &m);
  for (int i = 1, t; i <= n; ++i)
    scanf("%d", &t), insert(rt[i], 1, n, t), st.insert((Interval){i, i, 0});
  for (; m--;) {
    int op, l, r;
    scanf("%d%d%d", &op, &l, &r);
    std::set<Interval>::iterator L = st.upper_bound((Interval){l}),
                                 R = st.upper_bound((Interval){r});
    Interval recl = *(--L), recr = *(--R);
    if (L->l < l)
      if (L->ord == 0)
        rt[l] = split(rt[L->l], l - L->l);
      else
        rt[l] = split(rt[L->l], L->r - l + 1), std::swap(rt[l], rt[L->l]);
    if (L != R) {
      st.erase(L++);
      for (; L != R; st.erase(L++))
        merge(rt[l], rt[L->l]);
      if (r < R->r)
        if (R->ord == 0)
          rt[r + 1] = split(rt[R->l], r - R->l + 1);
        else
          rt[r + 1] = split(rt[R->l], R->r - r), std::swap(rt[r + 1], rt[R->l]);
      merge(rt[l], rt[R->l]);
    } else if (r < R->r)
      if (R->ord == 0)
        rt[r + 1] = split(rt[l], r - l + 1);
      else
        rt[r + 1] = split(rt[l], R->r - r), std::swap(rt[r + 1], rt[l]);
    st.erase(R), st.insert((Interval){l, r, op});
    if (recl.l < l)
      st.insert((Interval){recl.l, l - 1, recl.ord});
    if (r < recr.r)
      st.insert((Interval){r + 1, recr.r, recr.ord});
  }
  scanf("%d", &q);
  for (std::set<Interval>::iterator it = st.begin(); it != st.end(); ++it)
    if (q <= nd[rt[it->l]].sum) {
      if (it->ord == 0)
        printf("%d\n", query(rt[it->l], 1, n, q));
      else
        printf("%d\n", query(rt[it->l], 1, n, nd[rt[it->l]].sum - q + 1));
      break;
    } else
      q -= nd[rt[it->l]].sum;
  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;
}

Hide

题意概述

有一棵$N$个节点的树,每个节点都是黑色或白色。有$Q$次操作,动态修改点的颜色,询问最远黑点对之间的距离。
数据范围:$1 \le N \le 10^5, \; 1 \le Q \le 5 \times 10^5$。

算法分析

考虑点分治,构造一棵重心树。为了方便,下面所有距离均表示在原树上的距离,堆均为大根堆。
设节点$i$在重心树上的父亲为$p_i$。对于每个节点$u$维护两个堆,第一个堆用来维护重心树上$u$子树中的所有黑点到$p_u$的距离,第二个堆用来维护重心树上$u$各个子树中距离$u$最远的黑点到$u$的距离。那么第二个堆可以借助第一个堆来维护。
接着需要一个全局的堆,用来维护所有节点第二个堆的前两个元素之和(经过该点的路径)以及所有黑点第二个堆的第一个元素(以该点为端点的路径)。
修改时,沿着重心树往上依次处理经过的节点,先在全局的堆中删除,再在第二个堆中删除,在第一个堆中修改后,维护第二个堆和全局的堆。

代码

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

Little Pony and Lord Tirek

题目描述

Lord Tirek is a centaur and the main antagonist in the season four finale episodes in the series “My Little Pony: Friendship Is Magic”. In “Twilight’s Kingdom” (Part 1), Tirek escapes from Tartarus and drains magic from ponies to grow stronger.
The core skill of Tirek is called Absorb Mana. It takes all mana from a magic creature and gives them to the caster.
Now to simplify the problem, assume you have $n$ ponies (numbered from $1$ to $n$). Each pony has three attributes:

  • $s_i$: amount of mana that the pony has at time $0$;
  • $m_i$: maximum mana that the pony can have;
  • $r_i$: mana regeneration per unit time.

Lord Tirek will do $m$ instructions, each of them can be described with three integers: $t_i, l_i, r_i$. The instruction means that at time $t_i$, Tirek will use Absorb Mana on ponies with numbers from $l_i$ to $r_i$ (both borders inclusive). We’ll give you all the m instructions in order, count how much mana Tirek absorbs for each instruction.

题意概述

有$n$匹马,第$i$匹马初始时有$s_i$点魔法,魔法上限为$m_i$,每秒增加$r_i$点魔法。有$m$次操作,第$i$次操作在第$t_i$秒进行,将区间$[l_i, r_i]$中马的魔法清零。求每次操作清除了多少点魔法。
数据范围:$1 \le n, m \le 10^5, \; 0 \le s_i \le m_i \le 10^5, \; 0 \le r_i \le 10^5, \; 0 \le t_i \le 10^9$。

算法分析

显然,答案只与两次询问的时间差有关。
用set维护一些不相交的区间(它们的并是整个序列),每段区间内所有马的上次操作时间相同。每次操作就相当于切割一些区间然后合并一些区间。由于每次至多切割两个区间,因此总共操作的区间个数是$O(n)$的。
考虑区间询问。每匹马都可以表示为一个分段函数,我们用主席树来维护,第$i$棵线段树表示经过$i$秒后每匹马的函数。因为有些马有初始魔法,所以需要建两棵主席树,一棵表示第$i$匹马的初始魔法为$s_i$,另一棵表示所有马的初始魔法为$0$。
那么只要预处理出主席树,对于每次操作,在set中找到其对应的一些区间,在主席树上询问答案,并更新区间。

代码

/*
 * So, is the glass half empty, half full, or just twice as large as it needs to
 * be?
 */

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

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 long long ll;
typedef int const ic;

static ic N = 100005;
int numn, root[N << 1];
struct Pony {
  int s, m, r;
} p[N];
struct Event {
  int t, p, b;
} e[N];
struct Query {
  int t, l, r;
  bool operator<(Query const &a) const { return l < a.l; }
} q[N];
struct SegmentTree {
  int child[2];
  ll a, b;
} node[N << 6];
std::set<Query> st;

void update(ic &root) {
  if (!root)
    return;
  node[root].a = node[node[root].child[0]].a + node[node[root].child[1]].a;
  node[root].b = node[node[root].child[0]].b + node[node[root].child[1]].b;
}

void modify(int &root, ic &nl, ic &nr, ic &p, ic &a, ic &b, ic &flag) {
  if (p > nr || nl > p)
    return;
  if (flag)
    node[++numn] = node[root], root = numn;
  else if (!root)
    root = ++numn;
  if (nl == nr) {
    node[root].a = a, node[root].b = b;
    return;
  }
  ic mid = (nl + nr) >> 1;
  modify(node[root].child[0], nl, mid, p, a, b, flag);
  modify(node[root].child[1], mid + 1, nr, p, a, b, flag);
  update(root);
}

ll query(ic &root, ic &nl, ic &nr, ic &t, ic &l, ic &r) {
  if (!root || l > nr || nl > r)
    return 0;
  if (l <= nl && nr <= r)
    return node[root].a * t + node[root].b;
  ic mid = (nl + nr) >> 1;
  return query(node[root].child[0], nl, mid, t, l, r) +
         query(node[root].child[1], mid + 1, nr, t, l, r);
}

int main() {
  int n, m;
  read(n);
  for (int i = 0; i < n; ++i)
    read(p[i].s), read(p[i].m), read(p[i].r);
  read(m);
  for (int i = 0; i < m; ++i)
    read(q[i].t), read(q[i].l), read(q[i].r), --q[i].l, --q[i].r;
  for (int i = 0; i < n; ++i)
    modify(root[0], 0, n - 1, i, p[i].r, 0, 0),
        e[i] = (Event){p[i].r ? p[i].m / p[i].r + 1 : N, i, p[i].m};
  std::sort(e, e + n, [](Event const &a, Event const &b) { return a.t < b.t; });
  for (int i = 1, p = 0; i < N; ++i) {
    root[i] = root[i - 1];
    for (; p < n && e[p].t == i; ++p)
      modify(root[i], 0, n - 1, e[p].p, 0, e[p].b, 1);
  }
  for (int i = 0; i < n; ++i)
    modify(root[N], 0, n - 1, i, p[i].r, p[i].s, 0),
        e[i] = (Event){p[i].r ? (p[i].m - p[i].s) / p[i].r + 1 : N, i, p[i].m};
  std::sort(e, e + n, [](Event const &a, Event const &b) { return a.t < b.t; });
  for (int i = 1, p = 0; i < N; ++i) {
    root[N + i] = root[N + i - 1];
    for (; p < n && e[p].t == i; ++p)
      modify(root[N + i], 0, n - 1, e[p].p, 0, e[p].b, 1);
  }
  st.insert((Query){0, 0, n - 1});
  for (int i = 0; i < m; ++i) {
    auto rec = st.lower_bound((Query){q[i].t, q[i].l, q[i].r});
    if (rec == st.end())
      --rec;
    for (; rec != st.begin() && rec->r >= q[i].l; --rec)
      ;
    if (rec->r < q[i].l)
      ++rec;
    auto tmp = rec;
    Query l = (Query){rec->t, rec->l, q[i].l - 1};
    ll ans = 0;
    for (; rec != st.end() && rec->l <= q[i].r; ++rec)
      ans += rec->t ? query(root[std::min(q[i].t - rec->t, N - 1)], 0, n - 1,
                            q[i].t - rec->t, std::max(rec->l, q[i].l),
                            std::min(rec->r, q[i].r))
                    : query(root[std::min(q[i].t - rec->t, N - 1) + N], 0,
                            n - 1, q[i].t - rec->t, std::max(rec->l, q[i].l),
                            std::min(rec->r, q[i].r));
    printf("%lld\n", ans), --rec;
    Query r = (Query){rec->t, q[i].r + 1, rec->r};
    for (; tmp != st.end() && tmp->l <= q[i].r;)
      st.erase(tmp++);
    st.insert((Query){q[i].t, q[i].l, q[i].r});
    if (l.l <= l.r)
      st.insert(l);
    if (r.l <= r.r)
      st.insert(r);
  }
  return 0;
}

Similarity of Necklaces 2

题意概述

给定四个数组$M, P, L, R$,要求构造一个数组$T$,使得
$$\sum_{i=1}^N M_iT_i=0 \; (L_i \le T_i \le R_i)$$
求$\sum_{i=1}^N P_iT_i$的最大值。
数据范围:$1 \le N \le 200, \; 1 \le M_i \le 20, \; 0 \le P_i \le 10^5, \; -25 \le L_i \lt R_i \le 25$。

算法分析

令$D_i=T_i-L_i$,那么限制条件变为$\sum_{i=1}^N M_iD_i=-\sum_{i=1}^N M_iL_i \; (0 \le D_i \le R_i-L_i)$,要求的值变为$\sum_{i=1}^N P_iD_i+\sum_{i=1}^N P_iL_i$。这就相当于有$N$种物品,第$i$种物品有$(R_i-L_i)$个,每一个的体积为$M_i$,价值为$P_i$,背包的体积为$-\sum_{i=1}^N M_iL_i$,求物品恰好装满背包时的最大价值。这是分组背包问题,用单调队列优化DP即可。

代码

#include <cstdio>
#include <cstring>

int min(int a, int b) {
  return a < b ? a : b;
}

static const int N = 205;
int p[N], m[N], u[N], l[N];
int f[N << 10], q1[N << 10], q2[N << 10];

int main() {
  int n;
  while (~ scanf("%d", &n)) {
    int v = 0, w = 0;
    for (int i = 0; i < n; ++ i) {
      scanf("%d%d%d%d", &p[i], &m[i], &l[i], &u[i]);
      if (l[i]) u[i] -= l[i], v -= l[i] * m[i], w -= l[i] * p[i];
    }
    memset(f, -0x3f, sizeof f), f[0] = 0;
    for (int i = 0; i < n; ++ i) {
      u[i] = min(u[i], v / m[i]);
      for (int d = 0; d < m[i]; ++ d) {
        int l = 1, r = 0;
        for (int j = 0; j <= (v - d) / m[i]; ++ j) {
          int val = f[j * m[i] + d] - j * p[i];
          while (l <= r && q1[r] < val) -- r;
          q2[++ r] = j, q1[r] = val;
          if (j - q2[l] > u[i]) ++ l;
          f[j * m[i] + d] = q1[l] + j * p[i];
        }
      }
    }
    printf("%d\n", f[v] - w);
  }
  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;
}

Destiny

题目描述

Once, Leha found in the left pocket an array consisting of $n$ integers, and in the right pocket $q$ queries of the form $l$ $r$ $k$. If there are queries, then they must be answered. Answer for the query is minimal $x$ such that $x$ occurs in the interval $l$ $r$ strictly more than ${r-l+1 \over k}$ times or $-1$ if there is no such number. Help Leha with such a difficult task.

题意概述

给定包含$n$个数的序列,有$q$次询问,每次询问给定$l, r, k$,求区间$[l, r]$中出现次数严格大于${r-l+1 \over k}$的最小数字。
数据范围:$1 \le n, q \le 3 \times 10^5, \; 1 \le a_i \le n, \; 2 \le k \le 5$。

算法分析

建主席树,第$i$个位置上的线段树是前$i$个数的权值线段树。这样就可以用前缀和思想快速求出区间$[l, r]$中某个数出现的次数。对于每个询问,用第$r$个位置上线段树的值减去第$(l-1)$个位置上线段树的值,直接在主席树上暴力查找。由于$k$比较小,查找复杂度不会太高。

代码

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

using namespace std;

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 r(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 w(T x) {
    write(x); return *this;
  }
} io;

struct SegmentTree {
private:
  static const int N = 9000000;
  int tot;
  struct Node {
    int val, child[2];
  } node[N];
  int add_point(int root, int l, int r, int p) {
    if (l == r) {
      node[++ tot] = (Node) { node[root].val, 0, 0 };
      ++ node[tot].val; return tot;
    }
    int mid = l + r >> 1, rec = ++ tot;
    node[rec] = (Node) { 0, 0, 0 };
    if (p <= mid) {
      node[rec].child[1] = node[root].child[1];
      node[rec].child[0] = add_point(node[root].child[0], l, mid, p);
    } else {
      node[rec].child[0] = node[root].child[0];
      node[rec].child[1] = add_point(node[root].child[1], mid + 1, r, p);
    }
    node[rec].val = node[node[rec].child[0]].val + node[node[rec].child[1]].val;
    return rec;
  }
  int query_point(int root1, int root2, int l, int r, int p) {
    if (node[root2].val - node[root1].val < p) return -1;
    if (l == r) return node[root2].val - node[root1].val >= p ? l : -1;
    int mid = l + r >> 1, res = -1;
    if (node[node[root2].child[0]].val - node[node[root1].child[0]].val >= p)
      res = query_point(node[root1].child[0], node[root2].child[0], l, mid, p);
    if (~ res) return res;
    res = query_point(node[root1].child[1], node[root2].child[1], mid + 1, r, p);
    return res;
  }

public:
  int n, cnt, root[N];
  void add(int p) {
    root[cnt + 1] = add_point(root[cnt], 1, n, p), ++ cnt;
  }
  int find(int l, int r, int p) {
    return query_point(root[l - 1], root[r], 1, n, p);
  }
  void print() {
    cout << cnt << endl;
    for (int i = 1; i <= cnt; ++ i) cout << root[i] << ' ';
    cout << endl << tot << endl;
    for (int i = 1; i <= tot; ++ i) cout << i << ' ' << node[i].val << ' ' << node[i].child[0] << ' ' << node[i].child[1] << endl;
  }
};

struct Solver {
private:
  int n, q;
  SegmentTree tree;
  void input() {
    io.r(n).r(q);
    tree.n = n;
    for (int i = 1; i <= n; ++ i) {
      int t; io.read(t), tree.add(t);
    }
  }
  void process() {
    int l, r, k; io.r(l).r(r).r(k);
    int p = (r - l + 1) / k + 1;
    io.w(tree.find(l, r, p)).w('\n');
  }

public:
  void solve() {
    input(); while (q --) process();
  }
} solver;

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