当前位置:网站首页>Bzoj5178: [jsoi2011] lollipop (Chairman tree)

Bzoj5178: [jsoi2011] lollipop (Chairman tree)

2020-12-07 15:04:50 osc_ p4wgjz7p

Subject portal
.

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 ; 
    if(p<=mid)Link(t[u].lc,l,mid,p);
    else Link(t[u].rc,mid+1,r,p);
}
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<=n;i++) {Link(rt[i],1,n,a[i]);Merge(rt[i],rt[i-1]);}
    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;
}

版权声明
本文为[osc_ p4wgjz7p]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201207150436888r.html