[BZOJ1878][SDOI2009]HH的项链

2019-04-14 21:32发布

站内文章 / 模拟电子
10189 0 982
原题地址 十几分钟码完T了差不多一个小时，最后发现分块那里除写成模……这个状态真是没救了…… AC code: #include #include #include using namespace std; const int N=200010; int n,m,k,tot,L,R; int a[N],cnt[N],ans[N]; struct Query{ int l,r,num; friend bool operator<(Query x,Query y){ if(x.l/k!=y.l/k) return x.l/k<y.l/k; return x.r<y.r; } }q[N]; struct D{ int val,pos; friend bool operator<(D x,D y){ return x.val<y.val; } }; void discre(){ D d[N]; for(int i=1;i<=n;i++) d[i].val=a[i],d[i].pos=i; sort(d+1,d+n+1); for(int i=1,j=0;i<=n;i++){ if(i==1||d[i].val!=d[i-1].val) j++; a[d[i].pos]=j; } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); discre(); scanf("%d",&m); for(int i=1;i<=m;i++){ q[i].num=i; scanf("%d%d",&q[i].l,&q[i].r); } k=(int)sqrt(n); sort(q+1,q+m+1); L=q[1].l;R=q[1].r; for(int i=L;i<=R;i++){ if(!cnt[a[i]]) tot++; cnt[a[i]]++; } ans[q[1].num]=tot; for(int i=2;i<=m;i++){ if(q[i].lfor(int j=q[i].l;jif(!cnt[a[j]]) tot++; cnt[a[j]]++; } } else{ for(int j=L;j<q[i].l;j++){ if(cnt[a[j]]==1) tot--; cnt[a[j]]--; } } if(R<q[i].r){ for(int j=R+1;j<=q[i].r;j++){ if(!cnt[a[j]]) tot++; cnt[a[j]]++; } } else{ for(int j=q[i].r+1;j<=R;j++){ if(cnt[a[j]]==1) tot--; cnt[a[j]]--; } } L=q[i].l;R=q[i].r; ans[q[i].num]=tot; } for(int i=1;i<=m;i++) printf("%d ",ans[i]); return 0; }

热门文章