3 条题解

  • 0
    @ 2026-8-5 20:35:42 
    #include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,M=400;
int s[M][N],p[M][M],a[N],b[N],c[N],n,B,len,blen;
void init()
{
	for(int i=1;i<=len;i++)
	{
		for(int j=1;j<=blen;j++)c[j]=0;
		int mx=-1e9,id=1e9;
		for(int j=i;j<=len;j++)
		{
			for(int k=(j-1)*B+1;k<=min(j*B,n);k++)
			{
				c[a[k]]++;
				if(c[a[k]]>mx)
					mx=c[a[k]],id=a[k];
				else if(c[a[k]]==mx)id=min(id,a[k]);
			}
			p[i][j]=id;
		}
	}
	for(int i=1;i<=len;i++)
	{
		for(int j=1;j<=blen;j++)s[i][j]=s[i-1][j];
		for(int j=(i-1)*B+1;j<=min(i*B,n);j++)s[i][a[j]]++;
	}
}
int query(int l,int r)
{
	int bl=(l-1)/B+1,br=(r-1)/B+1;
	if(br-bl<=1)
	{
		for(int i=l;i<=r;i++)c[a[i]]=0;
		int mx=-1e9,id=1e9;
		for(int i=l;i<=r;i++)
		{
			c[a[i]]++;
			if(c[a[i]]>mx)mx=c[a[i]],id=a[i];
			else if(c[a[i]]==mx)id=min(id,a[i]);
		}
		return b[id];
	}
	else 
	{
		for(int i=l;i<=bl*B;i++)c[a[i]]=s[br-1][a[i]]-s[bl][a[i]];
		for(int i=(br-1)*B+1;i<=r;i++)c[a[i]]=s[br-1][a[i]]-s[bl][a[i]];
		int id=p[bl+1][br-1],mx=s[br-1][id]-s[bl][id];c[id]=mx;
		for(int i=l;i<=bl*B;i++)
		{
			c[a[i]]++;
			if(c[a[i]]>mx)mx=c[a[i]],id=a[i];
			else if(c[a[i]]==mx)id=min(id,a[i]);
		}
		for(int i=(br-1)*B+1;i<=r;i++)
		{
			c[a[i]]++;
			if(c[a[i]]>mx)mx=c[a[i]],id=a[i];
			else if(c[a[i]]==mx)id=min(id,a[i]);
		}
		return b[id];
	}
}
signed main()
{
	cin>>n;B=sqrt(n);len=(n-1)/B+1;
	for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);blen=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+blen+1,a[i])-b;
	init();
	for(int i=1;i<=n;i++)
	{
		int l,r;cin>>l>>r;
		cout<<query(l,r)<<'\n';
	}
	return 0;
}
    • 0
      @ 2026-7-27 21:04:38 
      #include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10, sqrtN = 350;
// 区间查询众数
// a[i]记录离散化后的值，b[i]记录每个点i所在块;
// f[i][j]记录从第i块到第j块的众数
// pos[i]记录离散化后值为i的所有位置，用于二分查询出现次数
// 每个块i的左端点L[i]、右端点R[i]
int n, a[N], b[N], L[sqrtN], R[sqrtN], f[sqrtN][sqrtN];
vector<int> vals, pos[N];
int tmp_cnt[N], vis[N], timer = 0;
int vis2[N], timer2 = 0;

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        vals.push_back(a[i]);
    }
    // 离散化
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1;
        pos[a[i]].push_back(i);
    }
    
    int B = sqrt(n), cnt = (n + B - 1) / B; // B为每块的长度，cnt为总块数
    for (int i = 1; i <= n; i++) {
        b[i] = (i - 1) / B + 1;
    }
    for (int i = 1; i <= cnt; i++) {
        L[i] = (i - 1) * B + 1;
        R[i] = min(i * B, n);
    }
    
    // 预处理块到块的众数
    for (int i = 1; i <= cnt; i++) {
        timer++;
        int max_cnt = 0, mode = 0;
        for (int j = i; j <= cnt; j++) {
            for (int k = L[j]; k <= R[j]; k++) {
                int v = a[k];
                if (vis[v] != timer) {
                    vis[v] = timer;
                    tmp_cnt[v] = 0;
                }
                tmp_cnt[v]++;
                if (tmp_cnt[v] > max_cnt || (tmp_cnt[v] == max_cnt && (mode == 0 || vals[v - 1] < vals[mode - 1]))) {
                    max_cnt = tmp_cnt[v];
                    mode = v;
                }
            }
            f[i][j] = mode;
        }
    }
    
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        int ans = 0, max_cnt = 0;
        timer2++;
        
        // 获取值v在[l, r]内的出现次数
        auto get_cnt = [&](int v, int l, int r) {
            return upper_bound(pos[v].begin(), pos[v].end(), r) - lower_bound(pos[v].begin(), pos[v].end(), l);
        };
        
        // 更新众数
        auto update = [&](int v) {
            if (vis2[v] == timer2) return; // 避免重复统计
            vis2[v] = timer2;
            int c = get_cnt(v, l, r);
            if (ans == 0 || c > max_cnt || (c == max_cnt && vals[v - 1] < vals[ans - 1])) {
                max_cnt = c;
                ans = v;
            }
        };
        
        if (b[l] == b[r]) { // 如果l和r在同一块内
            for (int j = l; j <= r; j++)
                update(a[j]);
        } else {
            if (b[l] + 1 <= b[r] - 1) {
                ans = f[b[l] + 1][b[r] - 1];
                max_cnt = get_cnt(ans, l, r);
                vis2[ans] = timer2; // 标记已统计，防止零散块重复统计
            }
            for (int j = l; j <= R[b[l]]; j++)
                update(a[j]);
            for (int j = L[b[r]]; j <= r; j++)
                update(a[j]);
        }
        cout << vals[ans - 1] << '\n';
    }
    return 0;
}
      • 0
        @ 2026-5-29 7:58:57

        回滚莫队（离线）：

        #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,B,a[300010],ans[300010],lsh[300010],tsp;
struct Q{
	int l,r,id;
}qq[300010];
bool cmp(Q a,Q b){
	if(a.l/B!=b.l/B)return a.l<b.l;
	return a.r<b.r;
}
int cnt[300010],cntc[300010],cntl[300010],mx,s,vis[300010];
int calc(int l,int r){
	int mx=0,res=0;
	for(int i=l;i<=r;i++){
		cntc[a[i]]++;
		if(cntc[a[i]]>mx||(cntc[a[i]]==mx&&a[i]<res)){
			mx=cntc[a[i]];
			res=a[i];
		}
	}
	for(int i=l;i<=r;i++)cntc[a[i]]=0;
	return lsh[res];
}
void add(int v){
	cnt[v]++;
	if(cnt[v]>mx||(cnt[v]==mx&&v<s)){
		mx=cnt[v];s=v;
	}
}
void addl(int v){
	if(vis[v]<tsp){
		vis[v]=tsp;
		cntl[v]=cnt[v];
	}
	cntl[v]++;
	if(cntl[v]>mx||(cntl[v]==mx&&v<s)){
		mx=cntl[v];
		s=v;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	B=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		lsh[i]=a[i];
	}
	sort(lsh+1,lsh+1+n);
	int ln=unique(lsh+1,lsh+1+n)-lsh-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(lsh+1,lsh+1+ln,a[i])-lsh;
		cin>>qq[i].l>>qq[i].r;qq[i].id=i;
	}
	sort(qq+1,qq+1+n,cmp);
	for(int i=0,j=1;i<=n/B;i++){
		int R=min(n,(i+1)*B-1);
		memset(cnt,0,sizeof(cnt));
		mx=s=0;
		tsp++;
		int l=R+1,r=R;
		for(;j<=n&&qq[j].l/B==i;j++){
			if(qq[j].r/B==qq[j].l/B){
				ans[qq[j].id]=calc(qq[j].l,qq[j].r);
				continue;
			}
			while(r<qq[j].r)add(a[++r]);
			int nmx=mx,ns=s;
			tsp++;
			while(l>qq[j].l)addl(a[--l]);
			ans[qq[j].id]=lsh[s];
			mx=nmx;s=ns;
			l=R+1;
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}

        分块（在线）：

        #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn=3e5+10,mxl=550;
int n,a[mxn],L[mxl],R[mxl],s[mxl][mxn],z[mxl][mxl],p[mxn],tt[mxn],cnt,B,ln,lsh[mxn];
void init(){
	for(int i=1;;i++){
		L[i]=(i-1)*B+1;R[i]=min(n,i*B);
		if(R[i]==n){
			cnt=i;
			break;
		}
	}
	for(int i=1;i<=n;i++)p[i]=(i+B-1)/B;
	for(int i=1;i<=cnt;i++){
		for(int j=L[i];j<=R[i];j++){
			tt[a[j]]++;
		}
		for(int j=1;j<=ln;j++)s[i][j]=tt[j];
	}
	for(int i=1;i<=cnt;i++){
		memset(tt,0,sizeof(tt));
		int mx=ln;
		for(int j=i;j<=cnt;j++){
			for(int k=L[j];k<=R[j];k++){
				tt[a[k]]++;
				if(tt[a[k]]>tt[mx]||(tt[a[k]]==tt[mx]&&a[k]<mx))mx=a[k];
			}
			z[i][j]=mx;
		}
	}
}
int find(int l,int r){
	if(p[l]==p[r]){
		for(int i=l;i<=r;i++)tt[a[i]]=0;
		int mx=ln;
		tt[ln]=0;
		for(int i=l;i<=r;i++){
			tt[a[i]]++;
			if(tt[a[i]]>tt[mx]||(tt[a[i]]==tt[mx]&&a[i]<mx))mx=a[i];
		}
		return lsh[mx];
	}
	int mx=(p[l]+1<=p[r]-1?z[p[l]+1][p[r]-1]:ln);
	tt[mx]=s[p[r]-1][mx]-s[p[l]][mx];
	for(int i=l;i<=R[p[l]];i++)tt[a[i]]=s[p[r]-1][a[i]]-s[p[l]][a[i]];
	for(int i=L[p[r]];i<=r;i++)tt[a[i]]=s[p[r]-1][a[i]]-s[p[l]][a[i]];
	for(int i=l;i<=R[p[l]];i++){
		tt[a[i]]++;
		if(tt[a[i]]>tt[mx]||(tt[a[i]]==tt[mx]&&a[i]<mx))mx=a[i];
	}
	for(int i=L[p[r]];i<=r;i++){
		tt[a[i]]++;
		if(tt[a[i]]>tt[mx]||(tt[a[i]]==tt[mx]&&a[i]<mx))mx=a[i];
	}
	return lsh[mx];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	B=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		lsh[i]=a[i];
	}
	sort(lsh+1,lsh+1+n);
	ln=unique(lsh+1,lsh+1+n)-lsh-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(lsh+1,lsh+1+ln,a[i])-lsh;
	}
	init();
	for(int i=1;i<=n;i++){
		int l,r;
		cin>>l>>r;
		cout<<find(l,r)<<'\n';
	}
	return 0;
}
        • 1

        数列分块入门 9

        信息

        ID
        477
        时间
        1500ms
        内存
        1024MiB
        难度
        8
        标签
        递交数
        38
        已通过
        6
        上传者
        1. Language
        2. 兼容模式
        3. 主题
        3. Worker 0, 17ms
        4. Powered by Hydro v5.0.1 Community