「Violet」蒲公英

题目链接:洛谷 4168

Description

让你求静态区间$[l,r]$的最小众数。

Data Range

结合数列分块$9$的数据范围。
$n\leq 10^5, m\leq 10^5, -10^9\leq a_i\leq 10^9$

Solution

先离散化一下。
用分块边角暴力的思想。
首先把问题分成边角和整段讨论。
我们设$cnt[l][r][x]$表示的第$l$段到第$r$段中$x$出现的次数。
暴力求解是$tot^2\times n$,$tot$是块的个数。
维护$f[i][j]$表示的是整段$i$到$j$的众数出现的次数,并且记录$d[i][j]$为该数为多少。
以上所有操作的复杂度为$tot^2\times n$。
差不多完成了整段的任务了。
那么考虑边角暴力。
如果相邻在一起,那么就直接暴力求解。
如果不是相邻,那么就修改在当前的整段答案上。
什么意思
假如说你现在要查询的区间是$[l,r]$
整段的区间是$[bl,br]$
很明显我们已经求出了$[bl,br]$。
那么在边角暴力查询的时候我们就把答案累加在$[bl,br]$的答案上就可以了,之后不要忘记还原。
注意一点,不要非常傻的累加答案后暴力,因为插入一个数只有这个数改变,换句话说就是只有这个数原来的答案会对答案产生影
响,只需要判断这个数的改变量就可以了。
以上的复杂度为$\frac{mn}{tot}$,设$n$和$m$是同阶的,那么可得当$tot$为$^3\sqrt{n}$运行最快。
以上是解法$1$,然后我们可以很明显的发现这个做法可以前缀和优化,然后块的大小改成$\sqrt n$,这样复杂度就变成了$n\sqrt n$。

Code

无前缀和优化版

#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x) {
    x = 0;
    T fl = 1;
    char ch = 0;
    for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') fl = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    x *= fl;
}
const int N = 40000 + 5;
int n, m, blo, dn, ans, tot, L, R, ANS1, ANS2;
int disc[N], a[N], b[N], cnt[45][45][N], pos[N], num[45][45], f[45][45];
int st(int x) {
    return x * blo - blo + 1;
}
int ed(int x) {
    return x * blo;
}
void read_disc() {
    read(n);
    read(m);
    tot = (int) pow(n * 1.0, 1.0 / 3);
    if (tot) blo = n / tot;
    if (n % blo != 0) tot ++;
    for (int i = 1; i <= n; i ++)
        read(a[i]), disc[i] = a[i], pos[i] = (i - 1) / blo + 1;
    sort(disc + 1, disc + 1 + n);
    dn = unique(disc + 1, disc + 1 + n) - disc - 1;
    for (int i = 1; i <= n; i ++)
        b[i] = lower_bound(disc + 1, disc + 1 + dn, a[i]) - disc;
}
void pre() {
    for (int i = 1; i <= tot; i ++)
        for (int j = i; j <= tot; j ++) {
            for (int k = st(i); k <= ed(j); k ++) cnt[i][j][b[k]] ++;
            for (int k = 1; k <= dn; k ++)
                if (cnt[i][j][k] > f[i][j] || (cnt[i][j][k] == f[i][j] && num[i][j] > k))
                    f[i][j] = cnt[i][j][k], num[i][j] = k;
        }
}
void add(int x) {
    cnt[L][R][b[x]] ++;
    if (cnt[L][R][b[x]] > ANS1 || (cnt[L][R][b[x]] == ANS1 && b[x] < ANS2))
        ANS1 = cnt[L][R][b[x]], ANS2 = b[x];
}
int query(int ql, int qr) {
    int px = pos[ql], py = pos[qr];
    L = px + 1, R = py - 1;
    if (L > R) L = R = 0;
    ANS1 = f[L][R], ANS2 = num[L][R];
    if (px == py) {
        for (int i = ql; i <= qr; i ++) add(i);
        for (int i = ql; i <= qr; i ++) cnt[L][R][b[i]] --;
    } else {
        for (int i = ql; i <= ed(px); i ++) add(i);
        for (int i = st(py); i <= qr; i ++) add(i);
        for (int i = ql; i <= ed(px); i ++) cnt[L][R][b[i]] --;
        for (int i = st(py); i <= qr; i ++) cnt[L][R][b[i]] --;
    }
    return disc[ANS2];
}
int main() {
    read_disc();
    pre();
    ans = 0;
    for (int i = 1; i <= m; i ++) {
        int x, y, ql, qr;
        read(x);
        read(y);
        ql = (x + ans - 1) % n + 1, qr = (y + ans - 1) % n + 1;
        if (ql > qr) swap(ql, qr);
        ans = query(ql, qr);
        printf("%d\n", ans);
    }
    return 0;
}

前缀和优化版

#include <bits/stdc++.h>

using namespace std;

template <typename T> void read(T &x) {
  x = 0; char ch = 0; bool flg = 0;
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') flg = 1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  flg ? x *= -1 : 233;
}

template <typename T> void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}

const int N = 100005;

int n, m;
int a[N], d[N], belong[N];
int dc, block_len, block_tot;
int prefix[360][N];
int tmp[N];
pair<int, int> ans[360][360];

int block_st(int id) {
  return (id - 1) * block_len + 1;
}

int block_ed(int id) {
  return min(n, id * block_len);
}

void block_init() {
  memset(tmp, 0, sizeof tmp);
  for (int i = 1; i <= block_tot; i++) {
    memcpy(prefix[i], prefix[i - 1], sizeof prefix[i]);
    for (int j = block_st(i); j <= block_ed(i); j++) {
      prefix[i][a[j]]++;
    }
  }
  for (register int i = 1; i <= block_tot; i++) {
    memset(tmp, 0, sizeof tmp);
    ans[i][i - 1] = {0, 1e9};
    for (int j = i; j <= block_tot; j++) {
      ans[i][j] = ans[i][j - 1];
      for (int k = block_st(j); k <= block_ed(j); k++) {
        tmp[a[k]]++;
        if (tmp[a[k]] > ans[i][j].first) {
          ans[i][j] = {tmp[a[k]], a[k]};
        } else if (tmp[a[k]] == ans[i][j].first && a[k] < ans[i][j].second) {
          ans[i][j].second = a[k];
        }
      }
    }
  }
}

void modify(int i, int j, pair<int, int>& res, int num) {
  tmp[num]++;
  if (prefix[j][num] - prefix[i - 1][num] + tmp[num] > res.first) {
    res = {prefix[j][num] - prefix[i - 1][num] + tmp[num], num};
  } else if (prefix[j][num] - prefix[i - 1][num] + tmp[num] == res.first && num < res.second) {
    res.second = num;
  }
}

int solve(int ql, int qr) {
  pair<int, int> res = {0, 1e9};
  if (belong[ql] + 1 >= belong[qr]) {
    for (register int i = ql; i <= qr; i++) {
      tmp[a[i]]++;
      if (tmp[a[i]] > res.first) {
        res = {tmp[a[i]], a[i]};
      } else if (tmp[a[i]] == res.first && a[i] < res.second) {
        res.second = a[i];
      }
    }
    for (int i = ql; i <= qr; i++) {
      tmp[a[i]]--;
    }
    return res.second;
  }
  res = ans[belong[ql] + 1][belong[qr] - 1];
  for (register int i = ql; i <= block_ed(belong[ql]); i++) {
    modify(belong[ql] + 1, belong[qr] - 1, res, a[i]);
  }
  for (register int i = block_st(belong[qr]); i <= qr; i++) {
    modify(belong[ql] + 1, belong[qr] - 1, res, a[i]);
  }
  for (register int i = ql; i <= block_ed(belong[ql]); i++) {
    tmp[a[i]]--;
  }
  for (register int i = block_st(belong[qr]); i <= qr; i++) {
    tmp[a[i]]--;
  }
  return res.second;
}

int main() {
  read(n); read(m);
  block_len = sqrt(n);
  for (register int i = 1; i <= n; i++) {
    read(a[i]);
    d[++ dc] = a[i];
    belong[i] = (i - 1) / block_len + 1;
  }
  block_tot = belong[n];
  sort(d + 1, d + 1 + dc);
  dc = unique(d + 1, d + 1 + dc) - d - 1;
  for (register int i = 1; i <= n; i++) {
    a[i] = lower_bound(d + 1, d + 1 + dc, a[i]) - d;
  } 
  block_init();
  memset(tmp, 0, sizeof tmp);
  int last_ans = 0;
  while (m--) {
    int l, r;
    read(l); read(r);
    l = (l + last_ans - 1) % n + 1;
    r = (r + last_ans - 1) % n + 1;
    if (l > r) {
      swap(l, r);
    }
    int res = solve(l, r);
    write(last_ans = d[res]);
    puts("");
  }
  return 0; 
}
最后修改:2019 年 09 月 07 日 08 : 04 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论