数据结构统计
P4602 [CTSC2018] 混合果汁
观察出可以使用二分答案，随后应用主席树维护前缀信息，使check函数优化到log级
#include<bits/stdc++.h>
#define N 100005
#define int long long
using namespace std;
struct Ty{int u,v,w;bool operator <(const Ty &a)const{return v<a.v;}
}x[N];
int num[N],root[N],cnt;
bool cmp(int a,int b){return a>b;}
struct Ig{int summ,val,l,r;}y[N*20];
void pushup(int u){y[u].val=y[y[u].l].val+y[y[u].r].val;y[u].summ=y[y[u].l].summ+y[y[u].r].summ;return;
}
void update(int &u,int v,int l,int r,int id,int val){u=++cnt;if(l==r){y[u].summ=y[v].summ+val;y[u].val=y[u].summ*l;return;}int mid=(l+r)/2;if(id<=mid){update(y[u].l,y[v].l,l,mid,id,val);y[u].r=y[v].r;}else{y[u].l=y[v].l;update(y[u].r,y[v].r,mid+1,r,id,val);}pushup(u);return;
}
int query(int u,int l,int r,int val){if(!u)return 2e18;if(val>y[u].summ)return 2e18;if(l==r)return val*l;int mid=(l+r)/2;if(val<=y[y[u].l].summ)return query(y[u].l,l,mid,val);else return y[y[u].l].val+query(y[u].r,mid+1,r,val-y[y[u].l].summ);return 0;
}
signed main(){int n,m;scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++){scanf("%lld%lld%lld",&x[i].v,&x[i].w,&x[i].u);num[i]=x[i].v;}sort(num+1,num+n+1,cmp);int L=unique(num+1,num+n+1)-num-1;for(int i=1;i<=n;i++){int l=1,r=L;while(l<r){int mid=(l+r)/2;if(num[mid]>x[i].v)l=mid+1;else r=mid;}x[i].v=l;}sort(x+1,x+n+1);x[0].v=0;for(int i=1;i<=n;i++){update(root[x[i].v],root[x[i-1].v],1,1e5,x[i].w,x[i].u);}for(int i=1;i<=m;i++){int u,val;scanf("%lld%lld",&val,&u);if(query(root[L],1,1e5,u)>val){printf("-1\n");continue;}int l=1,r=L;while(l<r){int mid=(l+r)/2;if(query(root[mid],1,1e5,u)<=val)r=mid;else l=mid+1;}printf("%lld\n",num[l]);}return 0;
}
分块维护区间众数
通过处理出大块的众数和每个数的出现位置，枚举可能成为众数的数，使用二分找出符合询问的区间从而计算个数
#include<bits/stdc++.h>
#define N 40005
#define M 4005
using namespace std;
int x[N],num[N],z[N],L[M],R[M],cnt[N],top=0,f[M][M];
vector<int>y[N];
inline int solve(int u,int fl,int fr){int l=0,r=y[u].size()-1,now=0;while(l<r){int mid=(l+r+1)/2;if(y[u][mid]<=fr)l=mid;else r=mid-1;}now=l;l=0;r=y[u].size()-1;while(l<r){int mid=(l+r+1)/2;if(y[u][mid]<fl)l=mid;else r=mid-1;}now-=l;return now;
}
signed main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&x[i]);z[i]=x[i];}sort(z+1,z+n+1);top=unique(z+1,z+n+1)-z-1;for(int i=1;i<=n;i++)x[i]=lower_bound(z+1,z+top+1,x[i])-z;int blockl=25,gron=(n-1)/blockl+1;for(int i=1;i<=gron;i++){L[i]=R[i-1]+1;R[i]=L[i]+blockl-1;}R[gron]=n;for(int i=1;i<=gron;i++){for(int j=L[i];j<=R[i];j++)num[j]=i;int maxn=0;for(int j=1;j<=top;j++)cnt[j]=0;for(int j=i;j<=gron;j++){for(int k=L[j];k<=R[j];k++){cnt[x[k]]++;if(cnt[x[k]]>cnt[maxn]||cnt[x[k]]==cnt[maxn]&&x[k]<maxn)maxn=x[k];}f[i][j]=maxn;}}for(int i=1;i<=top;i++)y[i].push_back(0);for(int i=1;i<=n;i++)y[x[i]].push_back(i);int last=0,v;for(int i=1;i<=m;i++){int l,r;scanf("%d%d",&l,&r);l=(l+last-1)%n+1;r=(r+last-1)%n+1;if(l>r)swap(l,r);int maxn=f[num[l]+1][num[r]-1],maxx=solve(maxn,l,r);for(int j=l;j<=R[num[l]];j++){v=solve(x[j],l,r);if(v>maxx||v==maxx&&x[j]<maxn){maxx=v;maxn=x[j];}}for(int j=L[num[r]];j<=r;j++){v=solve(x[j],l,r);if(v>maxx||v==maxx&&x[j]<maxn){maxx=v;maxn=x[j];}}last=z[maxn];printf("%d\n",z[maxn]);}return 0;
}