洛谷 P4396 [AHOI2013]作业（莫队+值域分块）

抱歉，一开始读错题了

由于最后统计 [a,b] 中有多少数出现过，以及位于 [a,b] 内的数值个数

由于这两个是相关联的，所以不好一起统计，所以采用暴力的方法，但是暴力一定超时，所以在这里使用分块

写分块的时候到底需要几个参数，首先对于非整块，vis[x] x出现的次数；对于整块 tag[x] x出现的次数，cnt[x] x 出现的种数

const int N=1e5+5;int n,m;int i,j,k;int a[N];struct Query {int l,r;int a,b;int id;void read(){ sdd(l,r); sdd(a,b); }}q[N];pii ans[N],now;int vis[N];int block,num,bel[N],tag[(int)1e3],cnt[(int)1e3];bool cmp(Query a,Query b)
{return bel[a.l]^bel[b.l]?a.l<b.l:a.r<b.r;
}   void build()
{block=sqrt(n); num=n/block;if(n%block)  num++;for(int i=1;i<=num;i++){int l=(i-1)*block+1,r=i*block;for(int j=l;j<=min(r,n);j++) bel[j]=i;}for(int i=1;i<=m;i++) q[i].id=i;sort(q+1,q+1+m,cmp);
}void add(int pos)
{int x=a[pos];if(!vis[x]) ++cnt[bel[x]];++vis[x]; ++tag[bel[x]];
}void del(int pos)
{int x=a[pos];--vis[x]; --tag[bel[x]];if(!vis[x]) --cnt[bel[x]];
}pii getans(int l,int r)
{pii now=mp(0,0);for(int i=l;i<=min(r,bel[l]*block);i++)if(vis[i]) now.fr+=vis[i],now.sc++;if(bel[l]-bel[r])for(int i=(bel[r]-1)*block+1;i<=r;i++)if(vis[i]) now.fr+=vis[i],now.sc++;for(int i=bel[l]+1;i<bel[r];i++)if(tag[i]) now.fr+=tag[i],now.sc+=cnt[i];return now;
}signed main()
{//IOS;while(~sdd(n,m)){for(int i=1;i<=n;i++) sd(a[i]);for(int i=1;i<=m;i++) q[i].read();build();int l=1,r=0;for(int i=1;i<=m;i++){while(q[i].l<l) add(--l);while(q[i].r>r) add(++r);while(q[i].l>l) del(l++);while(q[i].r<r) del(r--);ans[q[i].id]=getans(q[i].a,q[i].b);}for(int i=1;i<=m;i++) printf("%d %d\n",ans[i].fr,ans[i].sc);}//PAUSE;return 0;
}