題目鏈接

題意

長(zhǎng)度為N的數(shù)組，Q次詢問(wèn)，每次詢問(wèn)給兩個(gè)數(shù) L,R，求區(qū)間 [1, L] 和 [R, N]中一共有幾種數(shù)
1 <= N, Q <= 1e5
每次最多10個(gè)測(cè)試數(shù)據(jù)

AC

• 暴力肯定超時(shí)，用樹狀數(shù)組維護(hù)
  離線考慮沒出現(xiàn)的數(shù)字個(gè)數(shù)假設(shè) r > last[x]，那么當(dāng)l < first[x] 時(shí)，則x 沒出現(xiàn)
  有兩種實(shí)現(xiàn)方式：
  
• 按照查詢區(qū)間的右端點(diǎn)升序
  當(dāng)數(shù)字最后出現(xiàn)在這個(gè)右端點(diǎn)處，那么下面的區(qū)間的右側(cè)至少不會(huì)出現(xiàn)這個(gè)數(shù)字，因?yàn)橄聜€(gè)區(qū)間的右端點(diǎn)大于等于上個(gè)區(qū)間，只用判斷左區(qū)間就ok
• 按照查詢區(qū)間的左端點(diǎn)降序
  當(dāng)數(shù)字第一次出現(xiàn)在左端點(diǎn)處，那么下一個(gè)區(qū)間的左側(cè)至少不會(huì)出現(xiàn)這個(gè)數(shù)字，因?yàn)橄聜€(gè)區(qū)間的左端點(diǎn)小于上個(gè)區(qū)間，只用判斷右區(qū)間就ok
• 左端點(diǎn)降序

using namespace std;struct ac{int l, r, id;bool operator <(const ac &x) {return l > x.l;} }; int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endifint n, q;while (scanf("%d%d", &n, &q) != EOF) {// 記錄每個(gè)數(shù) 開始出現(xiàn)的位置 和 最后出現(xiàn)的位置vector<int> a(n + 1), first(n + 1), last(n + 1);// 統(tǒng)計(jì)數(shù)字種類int sum = 0;for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);last[a[i]] = i;if (!first[a[i]])first[a[i]] = i, sum++;}// queries 存放詢問(wèn)vector<ac> queries(q);for (int i = 0; i < q; ++i) {scanf("%d%d", &queries[i].l, &queries[i].r);queries[i].id = i;}// 按照詢問(wèn)左區(qū)間降序sort(queries.begin(), queries.end());// count 記錄不在范圍中的數(shù)// ans 記錄每次詢問(wèn)的結(jié)果vector<int> count(n + 1), ans(q);for (int i = n, k = 0; i >= 1; --i) {// 枚舉每個(gè)區(qū)間while (k < q && queries[k].l == i) {if (k == q) break;ans[queries[k].id] = sum;// 減去不在區(qū)間的數(shù)字， 向左枚舉for (int j = queries[k].r; j > 0; j -= lowbit(j)) {ans[queries[k].id] -= count[j];}k++;}// 更新不在區(qū)間的數(shù)字if (first[a[i]] == i) {for (int j = last[a[i]] + 1; j <= n; j += lowbit(j)) {count[j]++;}}}for (int i = 0; i < q; ++i) {printf("%d\n", ans[i]);}}return 0; }

• 右端點(diǎn)升序

using namespace std; struct ac{int l, r, id;bool operator <(const ac &a) {return r < a.r;} }; int main(){ #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endifint n, q;while (~scanf("%d%d", &n, &q)) {// 記錄每個(gè)數(shù) 開始出現(xiàn)的位置 和 最后出現(xiàn)的位置vector<int> a(n + 1), last(n + 1), first(n + 1);// 統(tǒng)計(jì)數(shù)字種類int sum = 0;for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);last[a[i]] = i;if (!first[a[i]]) {first[a[i]] = i;sum++;}}// count 記錄不在范圍中的數(shù)// ans 記錄每次詢問(wèn)的結(jié)果vector<int> count(n + 1), ans(q);// queries 存放詢問(wèn)vector<ac> queries(q);for (int i = 0; i < q; ++i) {scanf("%d%d", &queries[i].l, &queries[i].r);queries[i].id = i;}// 按照詢問(wèn)右端點(diǎn)升序sort(queries.begin(), queries.end());int k = 0;for (int i = 1; i <= n && k < q; ++i) {while (k < q && queries[k].r == i) {ans[queries[k].id] = sum;// 減去不在區(qū)間的數(shù)字， 向左枚舉for (int j = queries[k].l; j <= queries[k].r; j += lowbit(j)) {ans[queries[k].id] -= count[j];}++k;}// 更新不在區(qū)間的數(shù)字if (last[a[i]] == i) {for (int j = first[a[i]] - 1; j > 0; j -= lowbit(j)) {count[j]++;}}}for (int i = 0 ; i < q; ++i) {printf("%d\n", ans[i]);}}

總結(jié)

以上是生活随笔為你收集整理的牛客网暑期ACM多校训练营（第一场）J Different Integers的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。