题解 P1198 【[JSOI2008]最大数】

· · 题解

题解 P1198 【[JSOI2008]最大数】

\mathfrak{View\space it\space on\space my\space Blog}

思路

显而易见，后入队的结点如果比前面的大，那么前面的一定对答案没有贡献(如果查询的区间包括前面的，则一定包括后面的)

可以考虑维护单调性

算法1

维护一个递增的单调栈，每次询问二分查找第一个在询问范围内的

复杂度分析

  1. 每个元素只会入栈一次
  2. 每次查询的复杂度是O(log_2n)的
  3. 总复杂度O(n+qlog_2n)

期望得分100分

算法2

考虑对算法1进行优化

我们发现算法1的查询较慢，考虑是否能O(1)查询，考虑不将对答案无贡献的点删去，而是维护比他大的点中最新插入进序列的

发现可以用并查集维护，每次插入将和它相邻并比它小的合并

每个集合的集合代表设为最左边的，集合权值为最右边的值，这样下次维护时对于一个集合可以直接跳到它的左边，而查询末尾k个数的值就是从右往左第k个数所属集合代表的权值

复杂度分析

  1. 每个元素作为右端点只会被合并一次，所以一次插入的复杂度均摊为O(\alpha(n))
  2. 查询操作只需查询它所对应的集合的权值，所以一次查询的复杂度为O(\alpha(n))
  3. 总复杂度O(\alpha(n)\cdot(n+q))

期望得分100分

参考代码

此处只提供算法2的代码(省略预处理和快读快输)

const int N = 200005;

int find(int);
void uni(int, int);

int fa[N], maxi[N]; // 集合代表和权值
int id; // 数列的大小

int main () {
    int n, m;
    read(n), read(m);
  int lastans = 0;
  for (int i = 1; i <= n; ++i) {
    char ch = getchar();
    if (ch != 'A' && ch != 'Q') {
      ch = getchar();
    }
    ll a;
    read(a);
    if (ch == 'A') {
      ++id;
      fa[id] = id;
      maxi[id] = (a + lastans) % m;
      int fi = id; // 目前集合的最左端，fi - 1就是下次考虑是否合并的集合的最右端
      while (fi > 1 && maxi[fi] > maxi[find(fi - 1)]) {
        uni(fi - 1, fi);
        fi = find(id);
      }
    } else {
      lastans = maxi[find(id - a + 1)];
      write(lastans), EL;
    }
  }
  return 0;
}

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void uni(int x, int y) {
    int fx = find(x), fy = find(y);
    fa[fy] = fx; // 将集合代表设为左边的
    maxi[fx] = maxi[fy]; // 将集合权值设为右边的值
}