BZOJ-3339: Rmq Problem

Description

n<=200000,q<=200000,a<=200000

主席树的话好像统计不了数的出现的种数。
莫队+分块。时间复杂度O(n√n+m√a)。分块的话在块内统计出现数的种数，一直扫就好了，最后进入块中找元素。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,w[201000],num[201000],lz[2000],blo,col;
inline void read(int &x)
{
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
}
struct node
{
    int l,r,id;
}a[201000];
bool cmp(node x,node y){return x.l/blo==y.l/blo?x.r<y.r:x.l<y.l;}
int ans[201000];
int getans()
{
    int i=0;
    while(lz[i]==col) ++i; i=i*col;
    while(num[i]) ++i; return i;
}
int main()
{
    read(n); read(m); int i,mx=1; blo=sqrt(1.0*n);
    for(i=1;i<=n;++i) read(w[i]),mx=max(mx,w[i]);
    col=sqrt((double)mx);
    for(i=1;i<=m;++i) {read(a[i].l); read(a[i].r); a[i].id=i; }
    sort(a+1,a+m+1,cmp);
    int l=1,r=0;
    for(i=1;i<=m;++i)
    {
        while(r<a[i].r){r++; lz[w[r]/col]+=!num[w[r]]; num[w[r]]++;}
        while(l>a[i].l){l--; lz[w[l]/col]+=!num[w[l]]; num[w[l]]++;}
        while(r>a[i].r){num[w[r]]--; lz[w[r]/col]-=!num[w[r]]; r--;}
        while(l<a[i].l){num[w[l]]--; lz[w[l]/col]-=!num[w[l]]; l++;}
        ans[a[i].id]=getans();
    }
    for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}