题链:https://www.luogu.com.cn/problem/P1972
思路1:如果考虑莫队的话就是模板题,只不过出题人卡常,会T。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+10;
const int M = 1e6+10;
int n,m,base;
int a[N],num[M],ans[N],belong[N],cnt=0;
struct node{
int id,l,r;
}q[N];
char buffer[100001],*S,*T;
inline char Get_Char()
{
if (S==T)
{
T=(S=buffer)+fread(buffer,1,100001,stdin);
if (S==T) return EOF;
}
return *S++;
}
inline int read()
{
char c;int re=0;
for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
while(c>='0'&&c<='9') re=re*10+(c-'0'),c=Get_Char();
return re;
}
inline char read_charA()
{
char c;
for(c=Get_Char();c<'A'||c>'Z';c=Get_Char());
return c;
}
inline char read_chara()
{
char c;
for(c=Get_Char();c<'a'||c>'z';c=Get_Char());
return c;
}
inline void Write(int a)
{
if(a>9)
Write(a/10);
putchar(a%10+'0');
}
//bool cmp(node a,node b){
// return belong[a.l]==belong[b.l]? a.r<b.r:belong[a.l]<belong[b.l];
//}
bool cmp(node a, node b) {
return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
void add(int x){
num[a[x]]++;
if(num[a[x]]==1) cnt++;
}
void del(int x){
num[a[x]]--;
if(num[a[x]]==0) cnt--;
}
int main(void){
n=read();
base=sqrt(n);
for(int i=1;i<=n;i++){
a[i]=read();
belong[i]=i/base;
}
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+1+m,cmp);
int l=1,r=0;
for(int i=1;i<=m;i++){
int ql=q[i].l,qr=q[i].r;
while(l < ql) cnt -= !--num[a[l++]];
while(l > ql) cnt += !num[a[--l]]++;
while(r < qr) cnt += !num[a[++r]]++;
while(r > qr) cnt -= !--num[a[r--]];
ans[q[i].id]=cnt;
}
for(int i=1;i<=m;i++){
Write(ans[i]);
putchar('\n');
}
return 0;
}
思路2:对于一个查询区间,我们发现从右往左第一次出现的数是有用的,所以,我们将询问按右边界从大到小排序,每插入一个数就将这一个数的上一个位置置为0,将该位置置为1,那么答案就是ask(qr)-ask(ql-1)。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+10;
const int M = 1e6+10;
int n,m;
int a[N],pre[N],num[N],ans[N];
struct node{
int id,l,r;
}q[N];
inline int Read()
{
int res=0,ch,flag=0;
if((ch=getchar())=='-')
flag=1;
else if(ch>='0'&&ch<='9')
res=ch-'0';
while((ch=getchar())>='0'&&ch<='9')
res=res*10+ch-'0';
return flag?-res:res;
}
inline void Write(int a)
{
if(a>9)
Write(a/10);
putchar(a%10+'0');
}
int lowbit(int x){ return x&(-x); }
bool cmp(node a, node b) {
return a.r<b.r;
}
void add(int x){
while(x<N){
num[x]++;
x+=lowbit(x);
}
}
void del(int x){
if(x==0) return ;
while(x<N){
num[x]--;
x+=lowbit(x);
}
}
int ask(int x){
int ans=0;
while(x){
ans+=num[x];
x-=lowbit(x);
}
return ans;
}
int main(void){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
int r=1;
for(int i=1;i<=m;i++){
while(r<=q[i].r){
del(pre[a[r]]);
add(r);
pre[a[r]]=r;
r++;
}
ans[q[i].id]=ask(q[i].r)-ask(q[i].l-1);
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}