洛谷P5048 [Ynoi2019模拟赛]Yuno loves sqrt technology III（分块）

众所周知lxl是个毒瘤，Ynoi道道都是神仙题

用蒲公英那个分块的方法做结果两天没卡过去→_→

首先我们分块，预处理块与块之间的答案，然后每次询问的时候拆成整块和两边剩下的元素

整块的答案很简单，那么只有两边剩下的元素有可能更新答案

我们对于每一个元素用\(vector\)记录所有的出现位置，设\(dep_i\)为位置为\(i\)的元素在\(vector\)中的位置，那么如果\(a_i\)在这段区间中的出现次数超过\(res\)，那么\(vector\)中第\(i+res\)个元素就要小于等于\(r\)

不难发现\(res\)的改变次数小于\(2S\)，其中\(S\)为块的大小

然后就没有然后了

//minamoto

#include<bits/stdc++.h>

#define R register

#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

char sr[1<<21],z[20];int C=-1,Z=0;

inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}

void print(R int x){

    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;

    while(z[++Z]=x%10+48,x/=10);

    while(sr[++C]=z[Z],--Z);sr[++C]='\n';

}

const int N=5e5+5,M=1005;

int ans[M][M],a[N],b[N],cnt[N],rt[N],vis[N],sz[N],dep[N],nxt[N];

vector<int>pos[N];

int n,m,q,lastans=0,s,l,r;

void init(){

    fp(i,1,rt[n]){

        int bg=s*(i-1)+1,res=0;

        fp(j,bg,n){

            cmax(res,++cnt[a[j]]);

            ans[i][rt[j]]=res;

        }

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

    }

}

int query(){

    if(r-l+1<=(s<<2)){

    	int res=0;

    	fp(i,l,r)cmax(res,++cnt[a[i]]);

    	fp(i,l,r)cnt[a[i]]=0;

        return res;

    }

    int ll=rt[l]+1,rr=rt[r]-1;

    int LL=(ll-1)*s+1,RR=rr*s;

    int res=ans[ll][rr];

    fp(i,l,LL-1)

    	while(dep[i]+res<sz[a[i]]&&pos[a[i]][dep[i]+res]<=r)++res;

    fp(i,RR+1,r)

    	while(dep[i]-res>=0&&pos[a[i]][dep[i]-res]>=l)++res;

    return res;

}

int main(){

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

    n=read(),q=read(),s=sqrt(n)-1;

    fp(i,1,n)a[i]=b[i]=read(),rt[i]=(i-1)/s+1;

    sort(b+1,b+1+n),m=unique(b+1,b+1+n)-b-1;

    dep[0]=-1;

    fp(i,1,n){

    	a[i]=lower_bound(b+1,b+1+m,a[i])-b,pos[a[i]].push_back(i);

    	dep[i]=dep[nxt[a[i]]]+1,nxt[a[i]]=i;

	}

    fp(i,1,m)sz[i]=pos[i].size();

    init();

    while(q--){

        l=read()^lastans,r=read()^lastans;

        print(lastans=query());

    }

    Ot();

    return 0;

}

巴特西

洛谷P5048 [Ynoi2019模拟赛]Yuno loves sqrt technology III（分块）

最新文章

热门文章