對于20%的數據，N ≤ 100，M ≤ 1000；對于40%的數據，N ≤ 3000，M ≤ 200000；對于100%的數據，N ≤ 50000，M ≤ 200000。
這題目很多人看第一眼會想到莫隊，這的確是一個莫隊的好題，但是這里介紹一種方法，直接樹狀數組+離線處理就能搞。首先讀入時，記錄每種顏色的第一次出現位置，在樹狀數組中加上，以及每一個貝殼下一個同色貝殼的位置，之后我們將詢問讀入，然后按左端點排序。之后考慮詢問，放一個標記一直往右加，也就是說將每次左端點前的貝殼的下一個同色貝殼激活（因為左邊的那些貝殼之后再也不會被詢問到。）然后樹狀數組求區間和就行了。#include <cstdio>#include <algorithm>using namespace std;const int maxx = 50000 + 100;const int maxn = 1000000 + 100;const int maxm = 200000 + 100;int n,m,tot;int a[maxx],t[maxx],next[maxx];int head[maxn];struct Que{ int l; int r; int id; int ans;}Q[maxm];inline int Read(){ int x=0,f=1;char c=getchar(); while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();} return x*f;}int lowbit(int x){ return x&(-x);}void Add(int x,int k){ for(int i=x;i<=n;i+=lowbit(i)) t[i] += k;}int Query(int x){ int tmp = 0; for(int i=x;i>=1;i-=lowbit(i)) tmp += t[i]; return tmp;}bool cmp1(Que a,Que b){ return a.l==b.l? a.r<b.r : a.l<b.l;}bool cmp2(Que a,Que b){ return a.id<b.id;}int main(){ n = Read(); for(int i=1;i<=n;i++) a[i]=Read(),a[i]++,tot=max(tot,a[i]); for(int i=n;i>=1;i--) next[i]=head[a[i]],head[a[i]]=i; for(int i=1;i<=tot;i++) if(head[i]) Add(head[i],1); m = Read(); for(int i=1;i<=m;i++) Q[i].l=Read(),Q[i].r=Read(),Q[i].id=i; sort(Q+1,Q+m+1,cmp1); int now=1; for(int i=1;i<=m;i++){ while(now<Q[i].l){ if(next[now]) Add(next[now],1); now++; } Q[i].ans=Query(Q[i].r)-Query(Q[i].l-1); } sort(Q+1,Q+m+1,cmp2); for(int i=1;i<=m;i++) PRintf("%d/n",Q[i].ans); return 0;}
新聞熱點
疑難解答
