Just do it

時間限制：2000?ms ?|? 內存限制：65535?KB 難度：4 描述

螞蟻終于忍受不了宇宙總部要回地球了，它叮囑我不要再編它的故事了，
有啥事直接說，有啥問題直接問就好了，它相信大家都能替他解決的，
畢竟都解決了不少問題了。
好，這次就直接說問題
求一個序列的某個區間中出現了多少不相同的數字。對于一個序列會詢問很多很多次。

輸入

第一行一個整數T，表示T組數據 (T < 10)
每組數據第1行一個整數 N 表示第2行有 N 個整數ai (N <= 30000, 1 <= ai <= 1000000)
第3行一個整數 M 表示有 M 次詢問的區間(M <= 200000)
第4行開始往后M行每行兩個整數a b，表示詢問的區間[a,b] (1 <= a <= b <= n)

輸出

每組數據M行，輸出表示結果

樣例輸入

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

樣例輸出

3 2 3

提示

Huge inpiut ,please use scanf to read.

解題思路：區間問題，而且又沒有更新，莫隊算法正適合處理這類情況，如果比較熟悉莫隊的話就是水題啦。。

#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<cmath> #include<algorithm> using namespace std;const int maxn = 300005; const int maxm = 200005; int n,m,block,a[maxn],res[maxm]; int Map[1000005]; struct Node {int l,r,id;bool operator < (const Node &rhs) const{if(l / block == rhs.l / block)return r / block < rhs.r / block;return l / block < rhs.l / block;} }q[maxm];void solve() {block = sqrt(n + 0.5);sort(q+1,q+1+m);int ans = 0,l = 1,r = 0;for(int i = 1; i <= m; i++){if(q[i].l == q[i].r){res[q[i].id] = 1;continue;}while(l < q[i].l){Map[a[l]]--;if(Map[a[l]] == 0) ans--;l++;}while(l > q[i].l){l--;Map[a[l]]++;if(Map[a[l]] == 1) ans++;}while(r < q[i].r){r++;Map[a[r]]++;if(Map[a[r]] == 1) ans++;}while(r > q[i].r){Map[a[r]]--;if(Map[a[r]] == 0) ans--;r--;}res[q[i].id] = ans;}for(int i = 1; i <= m; i++)printf("%d\n",res[i]); }int main() {int t;scanf("%d",&t);while(t--){memset(Map,0,sizeof(Map));scanf("%d",&n);for(int i = 1; i <= n; i++)scanf("%d",&a[i]);scanf("%d",&m);for(int i = 1; i <= m; i++){scanf("%d %d",&q[i].l,&q[i].r);q[i].id = i;}solve();}return 0; }

總結

以上是生活随笔為你收集整理的nyoj 945 Just do it(莫队算法)的全部內容，希望文章能夠幫你解決所遇到的問題。

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