BZOJ 2724: [Violet 6]蒲公英 [分块 区间众数]

时间：2023-03-08 15:35:56

传送门

题面太美不忍不放

BZOJ 2724: [Violet 6]蒲公英 [分块 区间众数]

分块分块

这种题的一个特点是只有查询，通常需要预处理；加入修改的话需要暴力重构预处理

预处理$f[i][j]$为第i块到第j块的众数，显然$f[i][j]=max{f[i][j-1],j中出现的数}$，复杂度$O(N^2/S)$，常数比较小吧

最近用$pair$上瘾了...

然后查询$[l,r]$时，整块直接查，两边不完整的枚举出现的数，然后加上整块里出现次数来更新

求整块的出现次数，可以用$v[i]$表示数字$i$出现位置，二分来找，复杂度$O(NSlogN)$

或者clj orz的论文里还有预处理的方法，预处理$s[i][x]$前i个块x的次数和$ss[i][j][x]$第i块前j个中k出现次数，貌似代码量会很大....

所以说这种vector+二分来找一个区间内某个数出现次数还是比较巧妙的呀....

然后分块一定要分$\sqrt{\frac{N}{logN}}$大小，比根号快了1倍多.....

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <vector>

using namespace std;

#define pii pair<int, int>

#define MP make_pair

#define fir first

#define sec second

const int N=4e4+,M=;

typedef unsigned long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,Q,x,y,a[N],mp[N];

vector<int> v[N];

int pos[N],m,block;

struct _blo{int l,r;} b[M];

inline void ini(){

    if(n==) block=;

    else block=sqrt(n/log2(n));

    m=(n-)/block+;

    for(int i=;i<=n;i++) pos[i]=(i-)/block+;

    for(int i=;i<=m;i++) b[i].l=(i-)*block+,b[i].r=i*block;

    b[m].r=n;

}

//struct I{int x; bool operator <(const I &r) const{return x>r.x;} I(int a=0):x(a){} };

pii f[M][M];

int c[N];

struct Block{

    void set(int x){

        memset(c,,sizeof(c));

        pii now(,);

        for(int i=b[x].l;i<=n;i++){

            c[a[i]]++; int t=pos[i];

            now=max(now,MP( c[a[i]],-a[i] ) );//-a[i]

            f[x][t]=now;

        }

    }

    int cou(int l,int r,int x){

        return upper_bound(v[x].begin(),v[x].end(),r) - lower_bound(v[x].begin(),v[x].end(),l);

    }

    int que(int l,int r){//printf("que %d %d\n",l,r);

        pii re=f[pos[l]+][pos[r]-];

        if(pos[l]==pos[r])

            for(int i=l;i<=r;i++) re=max(re,MP( cou(l,r,a[i]),-a[i] ) );

        else{

            for(int i=l;i<=b[pos[l]].r;i++) re=max(re,MP( cou(l,r,a[i]),-a[i] ) );

            for(int i=b[pos[r]].l;i<=r;i++) re=max(re,MP( cou(l,r,a[i]),-a[i] ) );

        }

        return -re.sec;

    }

}B;

int main(){

    freopen("in","r",stdin);

    n=read();Q=read();

    for(int i=;i<=n;i++) a[i]=mp[i]=read();

    sort(mp+,mp++n); mp[]=unique(mp+,mp++n)-mp-;

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

        a[i]=lower_bound(mp+,mp++mp[],a[i])-mp , v[a[i]].push_back(i);

    ini();

    for(int i=;i<=m;i++) B.set(i);

    int last=;

    while(Q--){

        int l=(read()+last-)%n+,r=(read()+last-)%n+;

        if(l>r) swap(l,r);

        last=mp[ B.que(l,r) ];

        printf("%d\n",last);

    }

}

7796ms

[2017-03-15 16:41:05]

又想了一下，$ss$其实不用预处理，查询的时候暴力算就行了

然后来享受没有$log$的优越，3372ms到第一页啦啦啦

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

#define pii pair<int, int>

#define MP make_pair

#define fir first

#define sec second

const int N=4e4+,M=;

typedef unsigned long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,Q,x,y,a[N],mp[N];

int pos[N],m,block;

struct _blo{int l,r;} b[M];

inline void ini(){

    block=sqrt(n);

    m=(n-)/block+;

    for(int i=;i<=n;i++) pos[i]=(i-)/block+;

    for(int i=;i<=m;i++) b[i].l=(i-)*block+,b[i].r=i*block;

    b[m].r=n;

}

pii f[M][M];

int c[N],s[M][N];

struct Block{

    void set(int x){

        memset(c,,sizeof(c));

        pii now(,);

        for(int i=b[x].l;i<=n;i++){

            c[a[i]]++; int t=pos[i];

            now=max(now,MP( c[a[i]],-a[i] ) );

            f[x][t]=now;

        }

        for(int i=;i<=mp[];i++) s[x][i]=s[x-][i];

        for(int i=b[x].l;i<=b[x].r;i++) s[x][a[i]]++;

    }

    int t[N];

    int que(int l,int r){

        pii re=f[pos[l]+][pos[r]-];

        if(pos[l]==pos[r]){

            for(int i=l;i<=r;i++) t[a[i]]=;

            for(int i=l;i<=r;i++) re=max(re,MP( ++t[a[i]],-a[i] ) );

        }else{

            int L=pos[l],R=pos[r]-;

            for(int i=l;i<=b[pos[l]].r;i++) t[a[i]]=s[R][ a[i] ] - s[L][ a[i] ];

            for(int i=b[pos[r]].l;i<=r;i++) t[a[i]]=s[R][ a[i] ] - s[L][ a[i] ];

            for(int i=l;i<=b[pos[l]].r;i++) re=max(re,MP( ++t[a[i]],-a[i] ) );

            for(int i=b[pos[r]].l;i<=r;i++) re=max(re,MP( ++t[a[i]],-a[i] ) );

        }

        return -re.sec;

    }

}B;

int main(){

    freopen("in","r",stdin);

    n=read();Q=read();

    for(int i=;i<=n;i++) a[i]=mp[i]=read();

    sort(mp+,mp++n); mp[]=unique(mp+,mp++n)-mp-;

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

        a[i]=lower_bound(mp+,mp++mp[],a[i])-mp;

    ini();

    for(int i=;i<=m;i++) B.set(i);

    int last=;

    while(Q--){

        int l=(read()+last-)%n+,r=(read()+last-)%n+;

        if(l>r) swap(l,r);

        last=mp[ B.que(l,r) ];

        printf("%d\n",last);

    }

}

相关文章