1
#define add(x) {
2
  if(++vis[x]==1)sum++;
3
}
4
#define del(x) {
5
  if(--vis[x]==0)sum--;
6
}
7
void change(int x) {
8
  if(c[x].id>=l&&c[x].id<=r) {
9
    del(v[c[x].id]);
10
    add(c[x].val);
11
  }  //改变影响
12
  swap(c[x].val,v[c[x].id]);    //值更新 *
13
}
14
...
15
while(now<q[i].t)change(++now);  //修改
16
while(now>q[i].t)change(now--);  //修改

1
int n, m;
2
int len;
3
int mq, mr;
4
struct op {
5
  int l, r;
6
  int idx, tim;
7
  bool operator<(const op& that) const {
8
    if (l / len != that.l / len) return l < that.l;
9
    if (r / len != that.r / len) return r < that.r;
10
    return tim < that.tim;
11
  }
12
} q[N];
13
struct modify {
14
  int p, c;
15
} R[N];
16
int a[N], cnt[N];
17
int ans[N];
18
int res;
19
void add(int x) {
20
  if (cnt[x] == 0) res++;
21
  cnt[x]++;
22
}
23
void del(int x) {
24
  cnt[x]--;
25
  if (cnt[x] == 0) res--;
26
}
27
void solve() {
28
  cin >> n >> m;
29
  len = pow(n, 2.0 / 3.0);
30
  int l, r;
31
  char ch;
32
  for (int i = 1; i <= n; i++) {
33
    cin >> a[i];
34
  }
35
  for (int i = 1; i <= m; i++) {
36
    cin >> ch >> l >> r;
37
    if (ch == 'Q')
38
      q[++mq] = {l, r, mq, mr};
39
    else
40
      R[++mr] = {l, r};
41
  }
42
  sort(q + 1, q + 1 + mq);
43
  for (int i = 1, l = 1, r = 0, x = 0; i <= mq; i++) {
44
    while (q[i].l < l) add(a[--l]);
45
    while (r < q[i].r) add(a[++r]);
46
    while (l < q[i].l) del(a[l++]);
47
    while (q[i].r < r) del(a[r--]);
48

49
    // 时间戳
50
    // 要将 a[pos] 和 R[x].c 交换，而不能用其他变量代替，因为需要来回滚动
51
    while (x < q[i].tim) {
52
      ++x;  // 先加
53
      int pos = R[x].p;
54
      // 修改数在区间内
55
      if (l <= pos && pos <= r) {
56
        add(R[x].c);
57
        del(a[pos]);
58
      }
59
      swap(a[pos], R[x].c);
60
    }
61
    while (x > q[i].tim) {
62
      int pos = R[x].p;
63
      if (l <= pos && pos <= r) {
64
        add(R[x].c);
65
        del(a[pos]);
66
      }
67
      swap(a[pos], R[x].c);
68
      x--;  // 后减
69
    }
70
    ans[q[i].idx] = res;
71
  }
72

73
  for (int i = 1; i <= mq; i++) {
74
    cout << ans[i] << endl;
75
  }
76
}

1
int n, m, a[N], len, cnt1[N], cnt2[N], ans[N], st[N], ed[N], id[N], b[N], p;//cnt1 为统计数字个数的桶，cnt2 为处理暴力结果的桶，ans 为答案数组，b 为离散化后的数组，p 为离散化后的数组长度
2

3
struct query {
4
    int l, r, id;
5
    bool operator<(const query &rhs) const {
6
        if (::id[l] != ::id[rhs.l]) return l < rhs.l;
7
        return r < rhs.r;
8
    }
9
} q[N];
10

11
void add(int x, int &tmp) {
12
    ++cnt1[x];
13
    tmp = max(tmp, cnt1[x] * b[x]);
14
}
15

16
void del(int x) { --cnt1[x]; }
17

18
void solve() {
19
    cin >> n >> m;
20
    len = sqrt(n);
21
    for (int i = 1; i <= n; i++) {
22
        cin >> a[i];
23
        b[i] = a[i];
24
        id[i] = (i - 1) / len + 1;
25
        st[i] = (id[i] - 1) * len + 1;
26
        ed[i] = min(id[i] * len, n);
27
    }
28
    for (int i = 1; i <= m; i++) {
29
        cin >> q[i].l >> q[i].r;
30
        q[i].id = i;
31
    }
32
    sort(q + 1, q + m + 1);
33

34
    // 离散化
35
    sort(b + 1, b + n + 1);
36
    p = unique(b + 1, b + n + 1) - b - 1;
37
    for (int i = 1; i <= n; i++)
38
        a[i] = lower_bound(b + 1, b + p + 1, a[i]) - b;//a 数组现在存放的是离散化后的值
39
    int now = 0, last = 0, lstl = 0, tmp = 0;
40
    for (int i = 1, l = 1, r = 0; i <= m; i++) {
41
        if (id[q[i].l] == id[q[i].r]) {  // 左右区间属于同一块则进行暴力处理答案
42
            for (int j = q[i].l; j <= q[i].r; j++) ++cnt2[a[j]];
43
            for (int j = q[i].l; j <= q[i].r; j++)
44
                ans[q[i].id] = max(ans[q[i].id], cnt2[a[j]] * b[a[j]]);
45
            for (int j = q[i].l; j <= q[i].r; j++) --cnt2[a[j]];
46
            continue;
47
        }
48
        // 访问到了新的块，先把上一个块的答案清空
49
        if (id[q[i].l] != last) {
50
            while (r > ed[q[i].l]) del(a[r--]);   // 右指针移至上一个区间的右端点
51
            while (l <= ed[q[i].l]) del(a[l++]);  // 左指针右移至下一个区间的左端点
52
            tmp = 0;
53
            last = id[q[i].l];
54
        }
55
        // 扩展右指针
56
        while (r < q[i].r) add(a[++r], tmp);
57
        lstl = l;  // 准确来说 l 才是原先的左指针
58
        now = tmp;  // 非常重要
59
        // 扩展左指针
60
        while (lstl > q[i].l) add(a[--lstl], now);
61
        ans[q[i].id] = now;
62
        // 回滚左指针
63
        while (lstl < l) del(a[lstl++]);
64
    }
65
    for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
66
}

1
void solve() {
2
  auto dfs = [&](auto &&self, auto u, auto fa) -> auto {
3
    int t = top;
4
    for (int i = head[u]; i; i = nxt[i]) {
5
      int v = to[i];
6
      if (v != fa) {
7
        dfs(v, u);
8
        if (top - t >= B) {
9
          key[++tot] = u;
10
          while (top > t) bl[stk[top--]] = tot;
11
        }
12
      }
13
    }
14
    stk[++top] = u;
15
  };
16
  dfs(1, 0);
17
  if (!tot) ++tot;
18
  key[tot] = 1;
19
  while (top) bl[stk[top--]] = tot;
20
}