LOJ6285 数列分块入门9（分块）

昨天对着代码看了一晚上

然后今天终于在loj上过了

数列分块入门9题撒花★,°:.☆(￣▽￣)/$:.°★ 。

然后相当玄学

块的大小调成$\sqrt{n}$会TLE,改成150就过了

啧

然后就是用map离散化之后的值不能直接比较大小

锅锅锅

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <vector>

#include <map>

#include <cmath>

using namespace std;

int belong[100100],f[1000][1000],sz,blocknum,n,val[100100],id=0,cnt[100100],a[100100];

vector<int> Vec[100100];

map<int,int> To;

void calbe(int n){

    for(int i=1;i<=n;i++)

        belong[i]=(i-1)/sz+1;

}

void pre(int x){

    memset(cnt,0,sizeof(cnt));

    int ans=0,ansto=0;

    for(int i=(x-1)*sz+1;i<=n;i++){

        cnt[a[i]]++;

        if(cnt[a[i]]>ansto||(val[a[i]]<=val[ans]&&cnt[a[i]]>=ansto))

            ans=a[i],ansto=cnt[a[i]];

        f[x][belong[i]]=ans;

    }

}

int query(int l,int r,int c){

    return upper_bound(Vec[c].begin(),Vec[c].end(),r)-lower_bound(Vec[c].begin(),Vec[c].end(),l);

}

int query(int l,int r){

    int lsx=belong[l];

    int rex=belong[r];

    int ans=0,ansto=0,mid;

    for(int i=l;i<=min(lsx*sz,r);i++)

        if((mid=query(l,r,a[i]))>ansto||(val[a[i]]<=val[ans]&&mid>=ansto))

            ans=a[i],ansto=mid;

    if(lsx!=rex){

        for(int i=(rex-1)*sz+1;i<=r;i++)

            if((mid=query(l,r,a[i]))>ansto||(val[a[i]]<=val[ans]&&mid>=ansto))

                ans=a[i],ansto=mid;

        if(lsx+1<=rex-1)

            if((mid=query(l,r,f[lsx+1][rex-1]))>ansto||(val[f[lsx+1][rex-1]]<=val[ans]&&mid>=ansto))

                ans=f[lsx+1][rex-1],ansto=mid;

    }

    return ans;

}

int main(){

    // freopen("1.in","r",stdin);

    // freopen("test.out","w",stdout);

    scanf("%d",&n);

    sz=150;

    blocknum=n/sz;

    if(n%sz)

        blocknum++;

    calbe(n);

    for(int i=1;i<=n;i++){

        scanf("%d",&a[i]);

        if(!To[a[i]]){

            To[a[i]]=++id;

            val[id]=a[i];

        }

        a[i]=To[a[i]];

        Vec[a[i]].push_back(i);

    }

    for(int i=1;i<=blocknum;i++)

        pre(i);

    for(int i=1;i<=n;i++){

        int l,r;

        scanf("%d %d",&l,&r);

        printf("%d\n",val[query(l,r)]);

    }

    return 0;

}

巴特西

LOJ6285 数列分块入门9（分块）

最新文章

热门文章