BZOJ 3524 [Poi2014]Couriers 主席树

给一个长度为n的序列a。1≤a[i]≤n。
m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。

第一行两个数n，m。
第二行n个数，a[i]。
接下来m行，每行两个数l,r，表示询问[l,r]这个区间。

m行，每行对应一个答案。

【数据范围】

n,m≤500000

2016.7.9重设空间，但未重测！

传送门

AC 100 纪念！（蒟蒻）

撒花撒花~~~~~

其实主席树好像就是可持久化线段树？？（唔）

主席树(Chair Tree)是把n棵线段树，从O(N^2)的空间优化到了O（NlogN）

因为这n棵函数式线段树（权值线段树）的结构都是一致的，

以及一些特点，我们就可以优化了。

记得有个有图的教程似乎不错看看图就可以懂了的吧……

这题：

其实题意就是找m个区间的众数。

那么一个众数出现次数就是在区间长度一半以上；

通过构建一棵主席树，我们可以用前缀和的思想搞出区间内一段连续数字的总出现次数。

事实上，我们只要沿着出现次数比一半大的方向不停往下找，就可以找到了；

当然如果不存在，那么就是下面的两个儿子的值都比区间一半小。

所以可以称是主席树的入门题目了吧……

双倍经验BZOJ 2223

#include<bits/stdc++.h>
using namespace std;
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;
}
const int N=500005,logN=25;
int n,m,Tcnt;
int root[N];
struct ChairTree{int l,r,num;
}ct[N*logN];
void insert(int L,int R,int &x,int val){ct[Tcnt++]=ct[x];x=Tcnt-1;ct[x].num++;if (L==R) return;int mid=(L+R)>>1;if (val<=mid) insert(L,mid,ct[x].l,val);else insert(mid+1,R,ct[x].r,val);
}
int query(int L,int R,int ll,int rr,int g){if (L==R) return L;int mid=(L+R)>>1,t1=ct[ct[rr].l].num-ct[ct[ll].l].num,t2=ct[ct[rr].r].num-ct[ct[ll].r].num;if (t1>g) return query(L,mid,ct[ll].l,ct[rr].l,g); elseif (t2>g) return query(mid+1,R,ct[ll].r,ct[rr].r,g);else return 0;
}
int main(){n=read(),m=read();root[0]=0,Tcnt=1;for (int i=1;i<=n;i++)root[i]=root[i-1],insert(1,n,root[i],read());int x,y;while (m--){x=read(),y=read();printf("%d\n",query(1,n,root[x-1],root[y],(y-x+1)>>1));}return 0;
}