JSOI2085 最大数

原题链接:https://www.luogu.org/problem/P1198

收录于 NOI 系列题解集


思路

查询区间最值,可以写一个简单的线段树。一开始区间内没有值,无需建树;单点直接修改,无需传懒惰标记。常数似乎有点大,为了更保险些,用了快读快写,时间优化不明显。

注意查询中max无需写两次,第一次直接给res赋值就行了,否则会TLE

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#define max(a, b) ((a) < (b) ? (b) : (a))

const int MAXM = 200005, INF = 2000000005;
int sgt[MAXM << 2], M, D, L, id, t;
long long n;
char opt;

template <typename T>
inline void read(T &x) {
  x = 0;
  register char ch = getchar();
  register bool f = false;
  while (!isdigit(ch)) f = ch == '-', ch = getchar();
  do x = x * 10 + (ch - '0'); while (isdigit(ch = getchar()));
  if (f) x = -x;
}

inline void write(int x) {
  static char s[10];
  register int cnt = 0;
  if (x < 0) putchar('-'), x = -x;
  do s[cnt++] = x % 10; while (x /= 10);
  while (cnt--) putchar(s[cnt] + '0');
  putchar('\n');
}

inline int lc(int p) { return p << 1; }
inline int rc(int p) { return p << 1 | 1; }

inline void push_up(int p) {
  sgt[p] = max(sgt[lc(p)], sgt[rc(p)]);
}

void update(int u, int v, int p = 1, int l = 1, int r = M) {
  if (l == r) {
    sgt[p] = v;
    return;
  }
  int mid = (l + r) >> 1;
  if (u <= mid) update(u, v, lc(p), l, mid);
  else update(u, v, rc(p), mid + 1, r);
  push_up(p);
}

int query(int ql, int qr, int p = 1, int l = 1, int r = M) {
  if (ql <= l && r <= qr) {
    return sgt[p];
  }
  int res = -INF;
  int mid = (l + r) >> 1;
  if (ql <= mid) res = query(ql, qr, lc(p), l, mid);
  if (qr > mid) res = max(res, query(ql, qr, rc(p), mid + 1, r));
  return res;
}

int main() {
  read(M);
  read(D);
  id = 0, t = 0;
  for (int i = 0; i < M; ++i) {
    do opt = getchar(); while (opt != 'A' && opt != 'Q');
    switch (opt) {
      case 'A':
      read(n);
      update(++id, (n + t) % D);
      break;

      case 'Q':
      read(L);
      t = query(id - L + 1, id);
      write(t);
      break;
    }
  }
  return 0;
}

优化思路

线段树做法 AC 得太惊险了,考虑优化。

我们可以通过(反向)ST 表存储区间最值。st[i][j]表示右边界为i,大小为2^j的区间最大值。因为每次在最后插入新值, 我们只需要更新以新值为右边界的区间最大值就行了。这样反向存储 ST 表就不会影响之前存的值。

每次更新的时间复杂度为 O(\log (n)),而回答询问则为 O(1),跑得很快。

优化代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#define max(a, b) ((a) < (b) ? (b) : (a))

const int MAXM = 200005;
int st[MAXM][20], lb[MAXM], M, D, L, id, t;
long long n;
char opt;

void update(int i, int v) {
  st[i][0] = v;
  for (int j = 1; j <= lb[i]; ++j) {
    st[i][j] = max(st[i][j - 1], st[i - (1 << (j - 1))][j - 1]);
  }
}

int query(int l, int r) {
  int j = lb[r - l + 1];
  return max(st[r][j], st[l + (1 << j) - 1][j]);
}

int main() {
  scanf("%d%d", &M, &D);

  for (int i = 2; i <= M; ++i) lb[i] = lb[i >> 1] + 1;

  id = 0, t = 0;
  for (int i = 0; i < M; ++i) {
    scanf("%s", &opt);
    switch (opt) {
      case 'A':
      scanf("%lld", &n);
      update(++id, (n + t) % D);
      break;

      case 'Q':
      scanf("%d", &L);
      t = query(id - L + 1, id);
      printf("%d\n", t);
      break;
    }
  }
  return 0;
}
点赞

Leave a Reply