Sequence II

題目大意是有$m$次詢問，每次詢問一段區間$[l,r]$，從左到右，如果這個數是在這個區間第一次出現，則記錄下其下標，

我們會得到一個新的數組，要求這個數組的中位數是什么。

考慮使用主席樹來寫，我們倒序插入這些數的信息并記錄下這個數上一次是出現在哪，對于每個點我們將其下標在主席樹中$+1$，然后對于上一次出現的下標，在主席樹中$?1$，所以我們直接在第$l$棵主席樹中查詢區間$[l,r]$的權值即是這個區間的不同數字個數，在這個區間里，對于相同的數字，我們只會認定最右邊的那個一個數字，所以重復的數字會消除。

然后再在第$l$棵主席樹中查找第$k$大即可得到答案了。

#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 10;int a[N], pos[N], n, m, ans;int root[N], ls[N << 6], rs[N << 6], sum[N << 6], num;void update(int &rt, int pre, int l, int r, int x, int v) {rt = ++num, ls[rt] = ls[pre], rs[rt] = rs[pre], sum[rt] = sum[pre] + v;if (l == r) {return ;}int mid = l + r >> 1;if (x <= mid) {update(ls[rt], ls[pre], l, mid, x, v);}else {update(rs[rt], rs[pre], mid + 1, r, x, v);} }int query_sum(int rt, int l, int r, int L, int R) {if (!rt) {return 0;}if (l >= L && r <= R) {return sum[rt];}int mid = l + r >> 1, ans = 0;if (L <= mid) {ans += query_sum(ls[rt], l, mid, L, R);}if (R > mid) {ans += query_sum(rs[rt], mid + 1, r, L, R);}return ans; }int query_k(int rt, int l, int r, int k) {if (l == r) {return l;}int cur = sum[ls[rt]], mid = l + r >> 1;if (cur >= k) {return query_k(ls[rt], l, mid, k);}else {return query_k(rs[rt], mid + 1, r, k - cur);} }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int T;scanf("%d", &T);for (int cas = 1; cas <= T; cas++) {printf("Case #%d:", cas);memset(pos, 0, sizeof pos);for (int i = 0; i <= n; i++) {root[i] = 0;}for (int i = 0; i <= num; i++) {ls[i] = rs[i] = sum[i] = 0;}num = ans = 0;scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}for (int i = n; i >= 1; i--) {update(root[i], root[i + 1], 1, n, i, 1);if (pos[a[i]]) {update(root[i], root[i], 1, n, pos[a[i]], -1);}pos[a[i]] = i;}for (int i = 1; i <= m; i++) {int l, r;scanf("%d %d", &l, &r);l = (l + ans) % n + 1, r = (r + ans) % n + 1;if (l > r) {swap(l, r);}int sum = query_sum(root[l], 1, n, l, r);ans = query_k(root[l], 1, n, sum + 1 >> 1);printf(" %d", ans);}puts("");}return 0; }

總結

以上是生活随笔為你收集整理的Sequence II (HDU 5919)(主席树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。