hexo-blog/source/_posts/oi/destiny.md

---

title: Destiny tags:

• Persistent
• Prefix Sum
• Segment Tree id: "1484" categories:
• [OI, Common Skill]
• [OI, Data Structure] date: 2017-09-18 13:30:17 ---

题目描述

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