P1972 [SDOI2009] HH的项链
TLE 52pts record
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m;
int a[N],ans[N],pos[N],cnt[N];
int block;
int res;
inline int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)){
x=x*10+ch-'0';
ch=getchar();
}
return x;
}
inline void write(int x){
if(x>9)write(x/10);
putchar(x%10+'0');
}
struct node{
int l,r,k;
}q[N];
inline bool cmp(node a,node b){
return pos[a.l]^pos[b.l]?pos[a.l]<pos[b.l]:pos[a.l]&1?a.r>b.r:a.r<b.r;
}
inline void add(int x){
cnt[a[x]]++;
if(cnt[a[x]]==1) res++;
}
inline void del(int x){
cnt[a[x]]--;
if(cnt[a[x]]==0) res--;
}
int main(){
n=read();
block=sqrt(n);
for(int i=1;i<=n;i++){
a[i]=read();
pos[i]=(i-1)/block+1;
}
m=read();
for(int i=1;i<=m;i++){
q[i].l=read();
q[i].r=read();
q[i].k=i;
}
sort(q+1,q+m+1,cmp);
int nl=1,nr=0;
for(int i=1;i<=m;i++){
while(nr < q[i].r){
nr++;
cnt[a[nr]]++;
if(cnt[a[nr]]==1) res++;
}
while(nl < q[i].l){
cnt[a[nl]]--;
if(cnt[a[nl]]==0) res--;
nl++;
}
while(nr > q[i].r){
cnt[a[nr]]--;
if(cnt[a[nr]]==0) res--;
nr--;
}
while(nl > q[i].l){
nl--;
cnt[a[nl]]++;
if(cnt[a[nl]]==1) res++;
}
ans[q[i].k]=res;
}
for(int i=1;i<=m;i++) write(ans[i]),puts("");
return 0;
}
吸氧了，register int也用过了，卡不过ww
