对于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;}
新闻热点
疑难解答
