區間不同數

金牌導航 莫隊-1

題目大意

給出n個數，然后詢問m次，每次詢問一個區間內不同的數的個數

樣例輸入

6 1 2 3 4 3 5 3 1 2 3 5 2 6

樣例輸出

2 2 4

數據范圍

$1?n?5\times 10^4,1?m?2\times 10^5,0?a_i?10^6$

解題思路

先將原序列分塊，然后對每個查詢進行排序，排序以左端點所在塊為第一關鍵字，以右端點為第二關鍵字
然后每次在上一個查詢的前提下進行查詢
分塊和莫隊有效降低了時間復雜度，使時間復雜度是$O(n\sqrt{n})$

代碼

#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 50010 #define M 200021 #define NN 1000010 using namespace std; int n, m, w, g, l, r, s[N], p[NN], ans[M]; struct node {int v, b, l, r; }a[M]; bool cmp(node a, node b) {return a.b < b.b || a.b == b.b && a.r < b.r; } int main() {scanf("%d", &n);g = sqrt(n);for (int i = 1; i <= n; ++i)scanf("%d", &s[i]);scanf("%d", &m);for (int i = 1; i <= m; ++i){scanf("%d%d", &a[i].l, &a[i].r);a[i].v = i;a[i].b = (a[i].l - 1) / g + 1;//所在塊}sort(a + 1, a + 1 + m, cmp);for (int i = 1; i <= m; ++i){while(l < a[i].l) if (!--p[s[l++]]) w--;//移動指針while(l > a[i].l) if (!p[s[--l]]++) w++;while(r < a[i].r) if (!p[s[++r]]++) w++;while(r > a[i].r) if (!--p[s[r--]]) w--;ans[a[i].v] = w;}for (int i = 1; i <= m; ++i)printf("%d\n", ans[i]);return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【莫队】区间不同数（金牌导航 莫队-1）的全部內容，希望文章能夠幫你解決所遇到的問題。

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