bzoj1878/洛谷1972 [SDOI2009]HH的項鍊

這題想着用線段樹對于我這個蒟蒻來說太難了啊。。

然後看了題解知道是莫隊算法。。貌似還有一個【小Z的襪子】這麼一個例題

實際上我覺得這題比較容易入門吧

莫隊算法就是優化之後的暴力，離線處理區間問題

通過分塊把區間進行排序，然後枚舉區間，隻要知道[L,R]中的ans，那麼就可以得出[L+1,R],[L,R+1],[L,R-1],[L-1,R]的ans，不過我們可以直接通過兩個下标來進行對區間的求解

這是沒有修改的莫隊算法

帶修改的還沒來得及看～

一般來說隻要滿足詢問區間内相同元素的個數都可以用莫隊算法，【小Z的襪子】的話需要轉換一下，順便就看了一下

直接上代碼吧：

//Decision's template
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<set>
using namespace std;

#define DP_maxn 16
#define maxn 1000000+10
#define INF 10000007
#define mod 1000000007
#define mst(s,k) memset(s,k,sizeof(s))

typedef long long ll;

struct Edge{
    int from,to,dist;
    Edge(int u,int v,int d):from(u),to(v),dist(d){}
};

/*-------------------------------template End--------------------------------*/

int pl = 500;

struct node{
	int l,r,id;
	
	bool operator < (const node &a) const{
		return (l/pl==a.l/pl)?(r<a.r):(l/pl<a.l/pl);
	}
};

int n,m,l = 1,r = 0;
int tid[maxn];
int ans[maxn],ansd[maxn],num[maxn];
node all[maxn];
ll sum = 0;

void add(int x)
{
	num[x]++;
	if(num[x]==1) sum++;
}

void del(int x)
{
	num[x]--;
	if(num[x]==0) sum--;
}

int main()
{
    //freopen("std.in","r",stdin);
    //freopen("std.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i<=n;i++) cin>>tid[i];
    scanf("%d",&m);
    for(int i = 1;i<=m;i++)
    {
		scanf("%d %d",&all[i].l,&all[i].r);
		all[i].id = i;
	}
	sort(all+1,all+1+m);
	mst(num,0);
	for(int i = 1;i<=m;i++)
	{
		while(r<all[i].r)
		{
			r++;
			add(tid[r]);
		}
		while(r>all[i].r)
		{
			del(tid[r]);
			r--;
		}
		while(l<all[i].l)
		{
			del(tid[l]);
			l++;
		}
		while(l>all[i].l)
		{
			l--;
			add(tid[l]);
		}
		ans[all[i].id] = sum;
		
	}
	for(int i = 1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}