loj 6285

给定一个长度为n的序列a，之后有n次询问，每次询问[l,r]区间中的最小众数，蒟蒻的方法被卡了，求优化/更有解法

我的做法是普通莫队+权值线段树

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
 
int n,block,a[maxn],b[maxn],A[maxn],mp[maxn],ans[maxn];
struct Query{int l,r,id;}q[maxn];
inline int read(){
    register int x=0,f=1;register char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
struct Segment_Tree{
    struct Tree{int l,r,maxx,id;}t[maxn<<2];
    inline void push_up(int u){
        if(t[u<<1].maxx>t[u<<1|1].maxx) t[u].maxx=t[u<<1].maxx,t[u].id=t[u<<1].id;
        else if(t[u<<1].maxx<t[u<<1|1].maxx) t[u].maxx=t[u<<1|1].maxx,t[u].id=t[u<<1|1].id;
        else t[u].maxx=t[u<<1].maxx,t[u].id=min(t[u<<1].id,t[u<<1|1].id);
    }
    inline void build(int u,int l,int r){
        t[u].l=l,t[u].r=r,t[u].id=-2e9;
        if(l==r){t[u].id=l;return;}
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        push_up(u);
    }
    inline void modify(int u,int pos,int x){
//      cout<<u<<" "<<t[u].l<<" "<<t[u].r<<endl;
        if(t[u].l==t[u].r){t[u].maxx+=x;return;}
        int mid=t[u].l+t[u].r>>1;
        if(pos<=mid) modify(u<<1,pos,x);
        if(pos>mid) modify(u<<1|1,pos,x);
        push_up(u);
    }
    inline pair<int,int> query(int u,int l,int r){
        if(l<=t[u].l&&t[u].r<=r) return {t[u].id,t[u].maxx};
        int mid=t[u].l+t[u].r>>1;
        pair<int,int> ans={-1,0};
        if(r<=mid) ans=query(u<<1,l,r);
        else if(l>mid) ans=query(u<<1|1,l,r);
        else if(l<=mid&&r>mid){
            pair<int,int> ans1=query(u<<1,l,r),ans2=query(u<<1|1,l,r);
            if(ans1.second<ans2.second) ans=ans2;
            else if(ans1.second>ans2.second) ans=ans1;
            else ans={min(ans1.first,ans2.first),ans1.second};
        }
        return ans;
    }
    void dfs(int u){
        if(t[u].l==t[u].r){
            cout<<t[u].id<<" "<<t[u].maxx<<endl;
            return; 
        }
        dfs(u<<1),dfs(u<<1|1);
    }
}tr;
 
inline bool cmp(Query x,Query y){
    if(x.l/block==y.l/block) return x.r<y.r;
    return x.l/block<y.l/block;
}
inline void add(int x){tr.modify(1,A[x],1);}
inline void del(int x){tr.modify(1,A[x],-1);}
int main(){
    n=read(),block=sqrt(n);
    for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];
    sort(b+1,b+n+1);
    int m=unique(b+1,b+n+1)-b-1;
    for(register int i=1;i<=n;i++) A[i]=lower_bound(b+1,b+m+1,a[i])-b,mp[A[i]]=a[i];//离散化后数组A[i] 
    for(register int i=1;i<=n;i++) q[i].l=read(),q[i].r=read(),q[i].id=i; 
    sort(q+1,q+n+1,cmp);
    tr.build(1,1,n);
    int l=1,r=0;
    for(register int i=1;i<=n;i++){
        while(l<q[i].l) del(l++);
        while(l>q[i].l) add(--l);
        while(r<q[i].r) add(++r);
        while(r>q[i].r) del(r--);
//      cout<<"dfs "<<i<<": "<<endl; 
//      tr.dfs(1);
//      puts("");
        ans[q[i].id]=mp[tr.query(1,1,n).first];
    }
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
    return 0;
}