# Bzoj5178: [jsoi2011] lollipop (Chairman tree)

2020-12-07 15:04:50

solution ：
Chairman tree to find the number of times that the interval exceeds half of the length of the interval .

Code implementation ：

``````#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
struct node {

int lc,rc,c;}t[1100000];int cnt,n;
int a[51000],rt[51000];
void Link(int &u,int l,int r,int p) {
if(u==0)u=++cnt;
t[u].c++;int mid=(l+r)/2;
if(l==r)return ;
}
void Merge(int &u1,int u2) {
if(u1==0){u1=u2;return ;}
if(u2==0)return ;
t[u1].c+=t[u2].c;
Merge(t[u1].lc,t[u2].lc);Merge(t[u1].rc,t[u2].rc);
}
int find(int u1,int u2,int l,int r,int x,int y) {
int c=(y-x+1)/2;
if(l==r) {
if(t[u2].c-t[u1].c>c) return l;
else return 0;
}
int c1=t[t[u2].lc].c-t[t[u1].lc].c,c2=t[t[u2].rc].c-t[t[u1].rc].c;
if(c1<=c&&c2<=c) return 0;int mid=(l+r)/2;
if(c1>c) return find(t[u1].lc,t[u2].lc,l,mid,x,y);
else return find(t[u1].rc,t[u2].rc,mid+1,r,x,y);
}
int main() {
int m;scanf("%d%d",&n,&m);cnt=0;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++) {
int x,y,k;scanf("%d%d",&x,&y);
printf("%d\n",find(rt[x-1],rt[y],1,n,x,y));
}
return 0;
}``````

https://chowdera.com/2020/12/20201207150436888r.html