题意：
有的疯狂的二次元爱好者，家里会有很多手办，这不就有一个，他家里有3e5个手办，他的手办按作品出现的先后次序给编了号，同一作品的手办使用了相同数字，然后他取出n个随便放成一排，现在他就来考你了，让你求出从编号l到编号r之间，哪个作品的手办出现次数，超过 (r-l+1)/k次，当然可能有不止一部作品满足，要找出最早的一部作品的编号（即最小编号）
题解：
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+100; int n,m,q; int a[maxn];//原始数组 int t[maxn];//离散化数组 int T[maxn];//第i棵线段树的根节点编号 int lson[maxn*30];//每个节点的左儿子编号 int rson[maxn*30];//每个节点的右儿子编号 int c[maxn*30];//节点的权值 int tot;//动态开点 void init_hash () { //事先离散化 for (int i=1;i<=n;i++) t[i]=a[i]; sort(t+1,t+n+1); m=unique(t+1,t+n+1)-t-1; } int Hash (int x) { return lower_bound(t+1,t+m+1,x)-t; } int build (int l,int r) { //开一颗新的线段树 int root=tot++; c[root]=0; if (l!=r) { int mid=(l+r)>>1; lson[root]=build(l,mid); rson[root]=build(mid+1,r); } return root; } int up (int root,int p,int v) { int newRoot=tot++; int tmp=newRoot; int l=1,r=n; c[newRoot]=c[root]+v; while (l<r) { int mid=(l+r)>>1; if (p<=mid) { lson[newRoot]=tot++; rson[newRoot]=rson[root]; newRoot=lson[newRoot]; root=lson[root]; r=mid; } else { rson[newRoot]=tot++; lson[newRoot]=lson[root]; newRoot=rson[newRoot]; root=rson[root]; l=mid+1; } c[newRoot]=c[root]+v; } return tmp; } int query (int left_root,int right_root,int l,int r,int k) { if (c[left_root]-c[right_root]<=k) return -1; if (l==r) return l; int mid=(l+r)>>1; int ans=query(lson[left_root],lson[right_root],l,mid,k); if (ans==-1) ans=query(rson[left_root],rson[right_root],mid+1,r,k); return ans; } int main () { tot=0; scanf("%d%d",&n,&q); for (int i=1;i<=n;i++) scanf("%d",a+i); T[n+1]=build(1,n); for (int i=n;i;i--) { int p=a[i]; T[i]=up(T[i+1],p,1); } //printf("%d ",c[T[1]]); while (q--){ int l,r,k; scanf("%d%d%d",&l,&r,&k); printf("%d ",query(T[l],T[r+1],1,n,(r-l+1)/k)); } }