HH有一串由各種漂亮的貝殼組成的項鏈。HH相信不同的貝殼會帶來好運，所以每次散步 完后，他都會隨意取出一

段貝殼，思考它們所表達的含義。HH不斷地收集新的貝殼，因此他的項鏈變得越來越長。有一天，他突然提出了一

個問題：某一段貝殼中，包含了多少種不同的貝殼？這個問題很難回答。。。因為項鏈實在是太長了。于是，他只

好求助睿智的你，來解決這個問題。

Input

第一行：一個整數N，表示項鏈的長度。

第二行：N個整數，表示依次表示項鏈中貝殼的編號（編號為0到1000000之間的整數）。

第三行：一個整數M，表示HH詢問的個數。

接下來M行：每行兩個整數，L和R（1 ≤ L ≤ R ≤ N），表示詢問的區間。

N ≤ 50000，M ≤ 200000。

Output

M行，每行一個整數，依次表示詢問對應的答案。

Sample Input

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

Sample Output

2 2 4

Hint

思路：

1、用莫隊的話就是一個模板題。

2、 用離線樹狀數組的話，將詢問區間按照L升序排序，然后對數組中，每一個數a[i] 記錄一個 Next [i] 代表這個數右邊再一次出現的下標。

然后維護一個當前下標L =1 開始，更新樹狀數組即可。

莫隊的代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2) { ans = ans * a % MOD; } a = a * a % MOD; b /= 2;} return ans;} inline void getInt(int *p); const int maxn = 1000010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ ll ans[maxn]; ll Ans = 0ll; int l = 0; int r = 0; int b[maxn]; int vis[maxn]; struct node {int l, r, id; } a[maxn]; int pos[maxn]; int n, m; int len; bool cmp(node aa, node bb) {if (pos[aa.l] == pos[bb.l]) {return aa.r < bb.r;} else {return pos[aa.l] < pos[bb.l];} } void add(int x) {if (!vis[x]) {Ans++;}vis[x]++; } void del(int x) {if (vis[x] == 1) {Ans--;}vis[x]--; } int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);gg(n);len = (int)(sqrt(n));repd(i, 1, n) {gg(b[i]);}gg(m);repd(i, 1, m) {gg(a[i].l);gg(a[i].r);a[i].id = i;pos[i] = i / len;}sort(a + 1, a + 1 + m, cmp);repd(i, 1, m) {while (l > a[i].l) {l--;add(b[l]);}while (r < a[i].r) {r++;add(b[r]);}while (l < a[i].l) {del(b[l]);l++;}while (r > a[i].r) {del(b[r]);r--;}ans[a[i].id] = Ans;}repd(i, 1, m) {printf("%lld\n", ans[i]);}return 0; }inline void getInt(int *p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}} else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

樹樁數組的代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2) { ans = ans * a % MOD; } a = a * a % MOD; b /= 2;} return ans;} inline void getInt(int *p); const int maxn = 1000010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ int tree[maxn]; int lowbit(int x) {return -x & x; } int n, m; void add(int x, int val) {while (x <= n) {tree[x] += val;x += lowbit(x);} } int ask(int x) {int res = 0;while (x) {res += tree[x];x -= lowbit(x);}return res; } struct node {int l, r, ans, id; } b[maxn]; bool cmp1(node aa, node bb) {if (aa.l != bb.l) {return aa.l < bb.l;} else {return aa.l < bb.l;} } bool cmp2(node aa, node bb) {return aa.id < bb.id; } int a[maxn]; int mx = -1; int Next[maxn]; int pos[maxn]; int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);gbtb;cin >> n;repd(i, 1, n) {cin >> a[i];}for (int i = n; i >= 1; i--) {Next[i] = pos[a[i]];pos[a[i]] = i;mx = max(mx, a[i]);}for (int i = 0; i <= mx; ++i) {if (pos[i]) {add(pos[i], 1);}}cin >> m;repd(i, 1, m) {cin >> b[i].l >> b[i].r;b[i].id = i;}sort(b + 1, b + 1 + m, cmp1);int l = 1;repd(i, 1, m) {while (l < b[i].l) {if (Next[l]) {add(Next[l], 1);// add(l, -1);可有可無。}l++;}b[i].ans = ask(b[i].r) - ask(b[i].l - 1);}sort(b + 1, b + 1 + m, cmp2);repd(i, 1, m) {printf("%d\n", b[i].ans );}return 0;}inline void getInt(int *p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}} else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

轉載于:https://www.cnblogs.com/qieqiemin/p/11516846.html

總結

以上是生活随笔為你收集整理的HH的项链 HYSBZ - 1878 （莫队/ 树状数组）的全部內容，希望文章能夠幫你解決所遇到的問題。

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