分块

用户头像 发布于 9 小时前 9 次阅读 OI

分块

P2801 教主的魔法

分块即可，复制一个数组保持块内有序，然后用一个数组记录块整体的加减情况，就可以了。

代码：

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e6+5;
int n,x,m,q;
int a[N],b[N];
struct node{
    int st,ed,tag;
}k[N];

void change(int l,int r,int w){
    int lx=(l-1)/x+1,rx=(r-1)/x+1;
    if(lx==rx){
        for(int i=l;i<=r;i++) a[i]+=w;
        for(int i=k[lx].st;i<=k[lx].ed;i++) b[i]=a[i];
        sort(b+k[lx].st,b+k[lx].ed+1);
        return;
    }
    for(int i=l;i<=k[lx].ed;i++) a[i]+=w;
    for(int i=k[lx].st;i<=k[lx].ed;i++) b[i]=a[i];
    sort(b+k[lx].st,b+k[lx].ed+1);
    for(int i=k[rx].st;i<=r;i++) a[i]+=w;
    for(int i=k[rx].st;i<=k[rx].ed;i++) b[i]=a[i];
    sort(b+k[rx].st,b+k[rx].ed+1);
    for(int i=lx+1;i<rx;i++) k[i].tag+=w;
}

int query(int l,int r,int c){
    int res=0;
    int lx=(l-1)/x+1,rx=(r-1)/x+1;
    if(lx==rx){
        for(int i=l;i<=r;i++) if(a[i]+k[lx].tag>=c) res++;
        return res;
    }
    for(int i=l;i<=k[lx].ed;i++) if(a[i]+k[lx].tag>=c) res++;
    for(int i=k[rx].st;i<=r;i++) if(a[i]+k[rx].tag>=c) res++;
    for(int i=lx+1;i<rx;i++){
        int id=lower_bound(b+k[i].st,b+k[i].ed+1,c-k[i].tag)-b;
        if(id>=k[i].st&&id<=k[i].ed) res+=k[i].ed-id+1;
    }
    return res;
}

signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
    x=sqrt(1.0*n);
    m=ceil(1.0*n/(1.0*x));
    for(int i=1;i<=m;i++){
        k[i].st=(i-1)*x+1,k[i].ed=min(i*x,n);
        sort(b+k[i].st,b+k[i].ed+1);
    }
    while(q--){
        char op;
        int l,r,w;
        cin>>op>>l>>r>>w;
        if(op=='M') change(l,r,w);
        else cout<<query(l,r,w)<<"\n";
    }
	return 0;
}

P4168 [Violet] 蒲公英

预处理一下每两个块之间的众数以及前几个块每个值的个数，

先算出中间块的众数加上两边相等的数量，在看两边散块的值加上中间的值是否比当前答案大，都可以用预处理来的数据计算。

代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=3e5+5;
const int M=sqrt(N)+3;
int n,x,m,q,ans;
int a[N],b[N];
int cnt[N],f[M][N],g[M][M];
struct node{int st,ed;} k[N];

void init(){
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++) f[i][j]=f[i-1][j];             
		for(int j=k[i].st;j<=k[i].ed;j++) f[i][a[j]]++;
    }
    for(int i=1;i<=m;i++){
        memset(cnt,0,sizeof cnt);
		int res=0,sum=0;
        for(int i2=i;i2<=m;i2++){
            for(int j=k[i2].st;j<=k[i2].ed;j++){
                cnt[a[j]]++;
                if(cnt[a[j]]>sum||(cnt[a[j]]==sum&&a[j]<res)) res=a[j],sum=cnt[a[j]];
            }
			g[i][i2]=res;
        }
    }
	memset(cnt,0,sizeof cnt);
}

int query(int l,int r){
    int lx=(l-1)/x+1,rx=(r-1)/x+1;
    if(rx-lx<=1){
        int res=0;
        for(int i=l;i<=r;i++) cnt[a[i]]=0;
        for(int i=l;i<=r;i++){
            cnt[a[i]]++;
            if(cnt[a[i]]>cnt[res]||(cnt[a[i]]==cnt[res]&&a[i]<res)) res=a[i];
        }
        return res;
    }
    int res=g[lx+1][rx-1];
	int sum=f[rx-1][res]-f[lx][res];
    for(int i=l;i<=k[lx].ed;i++) sum+=(a[i]==res),cnt[a[i]]=0;
    for(int i=k[rx].st;i<=r;i++) sum+=(a[i]==res),cnt[a[i]]=0;
    for(int i=l;i<=k[lx].ed;i++) cnt[a[i]]++;
    for(int i=k[rx].st;i<=r;i++) cnt[a[i]]++;
    for(int i=l;i<=k[lx].ed;i++){
        int tot=f[rx-1][a[i]]-f[lx][a[i]]+cnt[a[i]];
        if(tot>sum||(tot==sum&&a[i]<res)) sum=tot,res=a[i];
    }
    for(int i=k[rx].st;i<=r;i++){
        int tot=f[rx-1][a[i]]-f[lx][a[i]]+cnt[a[i]];
        if(tot>sum||(tot==sum&&a[i]<res)) sum=tot,res=a[i];
    }
    return res;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>b[i],a[i]=b[i];
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
    x=sqrt(1.0*n);
    m=(n+x-1)/x;
    for(int i=1;i<=m;i++) k[i].st=(i-1)*x+1,k[i].ed=min(i*x,n);
    init();
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        ans=b[query(l,r)];
        cout<<ans<<"\n";
    }
	return 0;
}

P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III

用一个数组表示每两个块之间众数的个数，一个 vector 表示每个值在原数组的下标，一个数组表示当前数在 vector 的下标。

答案先暂定为中间块的众数，然后再扫两边的散块，vector 往前或往后一个一个扫下标，直到超出左右两边的边界。

代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=5e5+5,M=720;
int n,x,m,q,ans;
int a[N],b[N];
int in[N],st[M],ed[M];
int f[M][M],pos[N],cnt[N];
vector<int> p[N];

void init(){
	x=sqrt(1.0*n),m=(n+x-1)/x;
	sort(b+1,b+1+n);
    for(int i=1;i<=n;i++){
		in[i]=(i-1)/x+1;
		a[i]=lower_bound(b+1,b+1+n,a[i])-b;
		p[a[i]].push_back(i);
		pos[i]=p[a[i]].size()-1;
	}
    for(int i=1;i<=m;i++) st[i]=(i-1)*x+1,ed[i]=min(i*x,n);
	for(int i=1;i<=m;i++){
		memset(cnt,0,sizeof cnt);
		for(int j=i;j<=m;j++){
			f[i][j]=f[i][j-1];
			for(int k=st[j];k<=ed[j];k++) f[i][j]=max(f[i][j],++cnt[a[k]]);
		}
	}
}

int query(int l,int r){
	if(l>r||l>n) return 0;
	l=max(1ll,l),r=min(n,r);
	int ans=-1;
	if(in[l]==in[r]){
		for(int i=l;i<=r;i++) cnt[a[i]]=0;
		for(int i=l;i<=r;i++) ans=max(ans,++cnt[a[i]]);
		return ans;
	}
	ans=f[in[l]+1][in[r]-1];
	for(int i=l;i<=ed[in[l]];i++) while(pos[i]+ans<p[a[i]].size()&&p[a[i]][pos[i]+ans]<=r) ans++;
	for(int i=r;i>=st[in[r]];i--) while(pos[i]-ans>=0&&p[a[i]][pos[i]-ans]>=l) ans++;
	return ans;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>b[i],a[i]=b[i];
    init();
    while(q--){
        int l,r;
        cin>>l>>r;
        l^=ans,r^=ans;
        ans=query(l,r);
        cout<<ans<<"\n";
    }
	return 0;
}