益智小分块帮帮我呗

P4168 [Violet] 蒲公英

Ruan_ji @ 2025-01-12 21:06:13

现在就是样例过了，然后0分。

实在不想再调了，您看看吧，码风很好，变量名很清晰。思路和第一篇题解一样。

悬赏5关注。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#define N 40005
#define Q 205
#define int long long
using namespace std;
int n;
int m;
int len;
int bl[N];
int s[Q][N]; //在第i个块及之前的块中出现的j的数量 
int p[Q][Q]; //i到j块的众数 
int tong[N];
int num[N];
int a[N];
int lt[Q];
int rt[Q]; 
int maxh;
vector<int> g;
int kt[N];
vector<int> clean;
signed main(){
    // freopen("P4168_1.in","r",stdin);
    // freopen("answer.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>num[i];
        g.push_back(num[i]);
    }
    sort(g.begin(),g.end());
    int t=unique(g.begin(),g.end())-g.begin();
    for(int i=1;i<=n;++i){
        a[i]=lower_bound(g.begin(),g.end(),num[i])-g.begin()+1;
        maxh=max(maxh,a[i]); 
    } 
    len=sqrt(n);
    for(int i=1;i<=len;++i){
        lt[i]=rt[i-1]+1;
        rt[i]=i*len;
    }
    rt[len]=n;
    for(int i=1;i<=len;++i){
        for(int j=lt[i];j<=rt[i];++j){
            bl[j]=i;
        }
    }
    for(int i=1;i<=len;++i){
        memset(tong,0,sizeof tong);
        int maxx=-1;
        int id=-1;
        for(int j=i;j<=len;++j){
            for(int k=lt[j];k<=rt[j];++k){
                tong[a[k]]++;
                if(tong[a[k]] > maxx){
                    maxx=tong[a[k]];
                    id=a[k];
                }
                else if(tong[a[k]] == maxx){
                    if(a[k] < id) id=a[k];
                }
            }
            p[i][j]=id; 
        }
    }
    memset(tong,0,sizeof tong);
    for(int i=1;i<=len;++i){
        for(int j=1;j<=maxh;++j){
            tong[j]=0;
        }
        for(int j=lt[i];j<=rt[i];++j){
            tong[a[j]]++;
        } 
        for(int j=1;j<=maxh;++j){
            s[i][j]=s[i-1][j]+tong[j]; 
        }
    }
    int lst=0;
    while(m--){
        int l,r; cin>>l>>r;
        l=(l+lst-1)%n+1;
        r=(r+lst-1)%n+1;
        if(l>r) swap(l,r);
        if(bl[r]-bl[l]<=1){
            int mx=-1;
            int id=-1;
            for(int i=1;i<=maxh;++i){
                tong[i]=0;
            }
            for(int i=l;i<=r;++i){
                tong[a[i]]++;
                if(tong[a[i]] > mx){
                    mx=tong[a[i]];
                    id=a[i];
                }
                else if(tong[a[i]] == mx){
                    if(a[i] < id) id=a[i];
                }
            }
            cout<<g[id-1]<<'\n';
        }
        else {
            int ll=bl[l]; int rr=bl[r];
            ll++;rr--;
            int id=p[ll][rr];
            int mx=s[ll][rr];
            kt[id]=mx;
            clean.push_back(id);
            for(int i=l;i<=rt[bl[l]];++i){
                kt[a[i]]++;
                clean.push_back(a[i]);
                if(kt[a[i]] > mx){
                    mx=kt[a[i]];
                    id=a[i];
                }
                else if(kt[a[i]] == mx){
                    if(a[i] < id){
                        id=a[i]; 
                    }
                }
            }
            for(int i=lt[bl[r]];i<=r;++i){
                kt[a[i]]++;
                clean.push_back(a[i]);
                if(kt[a[i]] > mx){
                    mx=kt[a[i]];
                    id=a[i];
                }
                else if(kt[a[i]] == mx){
                    if(a[i] < id){
                        id=a[i]; 
                    }
                }
            }
            cout<<g[id-1]<<'\n'; 
        }
    }
    return 0;
}

by coding_goat @ 2025-01-12 21:13:25

一壶茶，一包烟，一个分块调一天，加油喵！

by _int_main_ @ 2025-01-12 21:30:36

@Ruan_ji

你没在输出后更新lst
你clear记了没用
bl[r]-bl[l]>1 时你逻辑基本上全是错的

by _int_main_ @ 2025-01-12 21:31:32

改好的，具体怎么错的你自己看吧

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#define N 40005
#define Q 205
#define int long long
using namespace std;
int n;
int m;
int len;
int bl[N];
int s[Q][N]; //在第i个块及之前的块中出现的j的数量
int p[Q][Q]; //i到j块的众数
int tong[N];
int num[N];
int a[N];
int lt[Q];
int rt[Q];
int maxh;
vector<int> g;
int kt[N];
vector<int> clean;
signed main(){
    // freopen("P4168_1.in","r",stdin);
    // freopen("answer.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>num[i];
        g.push_back(num[i]);
    }
    sort(g.begin(),g.end());
    int t=unique(g.begin(),g.end())-g.begin();
    for(int i=1;i<=n;++i){
        a[i]=lower_bound(g.begin(),g.end(),num[i])-g.begin()+1;
        maxh=max(maxh,a[i]);
    }
    len=sqrt(n);
    for(int i=1;i<=len;++i){
        lt[i]=rt[i-1]+1;
        rt[i]=i*len;
    }
    rt[len]=n;
    for(int i=1;i<=len;++i){
        for(int j=lt[i];j<=rt[i];++j){
            bl[j]=i;
        }
    }
    for(int i=1;i<=len;++i){
        memset(tong,0,sizeof tong);
        int maxx=-1;
        int id=-1;
        for(int j=i;j<=len;++j){
            for(int k=lt[j];k<=rt[j];++k){
                tong[a[k]]++;
                if(tong[a[k]] > maxx){
                    maxx=tong[a[k]];
                    id=a[k];
                }
                else if(tong[a[k]] == maxx){
                    if(a[k] < id) id=a[k];
                }
            }
            p[i][j]=id;
        }
    }
    memset(tong,0,sizeof tong);
    for(int i=1;i<=len;++i){
        for(int j=1;j<=maxh;++j){
            tong[j]=0;
        }
        for(int j=lt[i];j<=rt[i];++j){
            tong[a[j]]++;
        }
        for(int j=1;j<=maxh;++j){
            s[i][j]=s[i-1][j]+tong[j];
        }
    }
    int lst=0;
    while(m--){
        int l,r; cin>>l>>r;
        l=(l+lst-1)%n+1;
        r=(r+lst-1)%n+1;
        if(l>r) swap(l,r);
        if(bl[r]-bl[l]<=1){
            int mx=-1;
            int id=-1;
            for(int i=1;i<=maxh;++i){
                tong[i]=0;
            }
            for(int i=l;i<=r;++i){
                tong[a[i]]++;
                if(tong[a[i]] > mx){
                    mx=tong[a[i]];
                    id=a[i];
                }
                else if(tong[a[i]] == mx){
                    if(a[i] < id) id=a[i];
                }
            }
            cout<<(lst=g[id-1])<<'\n';
        }
        else {
            int ll=bl[l]; int rr=bl[r];
            ll++;rr--;
            int id=p[ll][rr];
            int mx=s[rr][id]-s[ll-1][id];
            clean.clear();
            for(int i=l;i<=rt[bl[l]];++i){
                kt[a[i]]++;
                clean.push_back(a[i]);
                int cnt=kt[a[i]]+s[rr][a[i]]-s[ll-1][a[i]];
                if(cnt > mx){
                    mx=cnt;
                    id=a[i];
                }
                else if(cnt == mx){
                    if(a[i] < id){
                        id=a[i];
                    }
                }
            }
            for(int i=lt[bl[r]];i<=r;++i){
                kt[a[i]]++;
                clean.push_back(a[i]);
                int cnt=kt[a[i]]+s[rr][a[i]]-s[ll-1][a[i]];
                if(cnt > mx){
                    mx=cnt;
                    id=a[i];
                }
                else if(cnt == mx){
                    if(a[i] < id){
                        id=a[i];
                    }
                }
            }
            cout<<(lst=g[id-1])<<'\n';
            for(int v:clean)kt[v]--;
        }
    }
    return 0;
}

by chen_z @ 2025-01-12 21:49:17

吾皇万岁万岁万万岁 orz

by Ruan_ji @ 2025-01-12 22:10:05

@_intmain 我去，神仙！我一定会吸收然后再也不会犯这种错误了。谢谢您

by Ruan_ji @ 2025-01-12 22:10:29

@chen_z 受不得受不得 sto