C++(g++ 7.5.0) 解法, 执行用时: 123ms, 内存消耗: 32924K, 提交时间: 2022-12-09 21:15:06

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+10;
int a[N],tr[N],ans[N],pre[N];
int n,m;

int lowbit(int x)
{
	return x&(-x);
}

int query(int x)
{
	int ans=0;
	for(;x;x-=lowbit(x))ans+=tr[x];
	return ans;
}

void modify(int x,int v)
{
	for(;x<=n;x+=lowbit(x))tr[x]+=v;
}

struct qn
{
	int l;
	int id;
};
vector<qn>q[N];

void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int l,r;
		cin>>l>>r;
		qn t;
		t.id=i;t.l=l;
		q[r].push_back(t);
	}
	for(int i=1;i<=n;i++)
	{
		modify(i,1);
		if(pre[a[i]])
		{
			modify(pre[a[i]],-1);
		}
		pre[a[i]]=i;
		for(auto u:q[i])
		{
			ans[u.id]=query(i)-query(u.l-1);
		}
	}
	for(int i=1;i<=m;i++)
	cout<<ans[i]<<"\n";
}

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	solve();
}

C++ 解法, 执行用时: 122ms, 内存消耗: 10872K, 提交时间: 2021-08-23 13:53:11

#include<bits/stdc++.h>
using namespace std;
int a[51000],pre[51000],fa[1000010];
int BIT[51000];
int n,m;
void upd(int id,int val)
{
	if (id<=0)return;
	for (id;id<=n;id+=id&-id)BIT[id]+=val;
}
int query(int id)
{
	int ans=0;
	for (id;id>0;id-=id&-id)ans+=BIT[id];
	return ans;
}
vector<array<int,2>> ques[51000];
int ans[200010];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		pre[i]=fa[a[i]];
		fa[a[i]]=i;
	}scanf("%d",&m);
	for (int i=1;i<=m;++i)
	{
		int l,r;cin>>l>>r;
		ques[r].push_back({l,i});
	}
	for (int i=1;i<=n;++i)
	{
		upd(i,1);
		upd(pre[i],-1);
		for (array<int,2>& ar:ques[i])
			ans[ar[1]]=query(i)-query(ar[0]-1);
	}
	for (int i=1;i<=m;++i)printf("%d\n",ans[i]);
}