本文共 1539 字，大约阅读时间需要 5 分钟。
【题目分析】
查找区间内出现次数大于一半的数字。
直接用主席树，线段树上维护区间大小，由于要求出现次数大于一半，每到一个节点可以分治下去。
时间复杂度(N+Q)logN
【代码】
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define maxn 500005#define mlog 30#define inf (0x3f3f3f3f) int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;} int rt[maxn],ls[maxn*mlog],rs[maxn*mlog],siz[maxn*mlog],idx=0; int n,m,x,a[maxn]; int ins(int o,int l,int r,int x){ int k=++idx; siz[k]=siz[o]+1; int mid=(l+r)/2; if (l==r) return k; if (x<=mid) rs[k]=rs[o],ls[k]=ins(ls[o],l,mid,x); else ls[k]=ls[o],rs[k]=ins(rs[o],mid+1,r,x); return k;} int query(int o1,int o2,int l,int r,int tim){// printf("%d %d\n",l,r); if (l==r) { if (siz[o2]-siz[o1]>tim) return l; else return 0; } if (siz[ls[o2]]-siz[ls[o1]]>siz[rs[o2]]-siz[rs[o1]]) return query(ls[o1],ls[o2],l,(l+r)/2,tim); else return query(rs[o1],rs[o2],(l+r)/2+1,r,tim);} int main(){ n=read();m=read(); for (int i=1;i<=n;++i) a[i]=x=read(),rt[i]=ins(rt[i-1],1,n,x);// for (int i=1;i<=n;++i) printf("%d ",a[i]); printf("\n"); for (int i=1;i<=m;++i) { int l=read(),r=read();// printf("ask for %d to %d\n",l,r); if (l==r) {// printf("l == r\n"); printf("%d\n",a[r]); } else printf("%d\n",query(rt[l-1],rt[r],1,n,(r-l+1)/2)); }}
转载于:https://www.cnblogs.com/SfailSth/p/6195085.html