BruceJay's Blog

BZOJ2653 middle

| Comments

To start with

主席树%%%%%%

Problem

Solution

这题Bruce看了题解。
对每一个权值x建一棵权值线段树,权值线段树上有n个位置,若a[i]>x,则这个位置上的权值为1,否则为-1。举个例子,对于这个样例,权值206452321各个位置上的权值分别为-1,1,-1,1,-1。
这些权值线段树可以用主席树维护。将a排好序,后一个只需对前一个修改一个位置就行了(也就是修改一条链)。
对于询问,可以二分。对于权值x,区间[l1,r1],[l2,r2],如果权值线段树上区间[l,r](l1<=l<=r1,l2<=r<=r2)的和的最大值大于等于0,则说明最大中位数>=x。至于维护权值线段树上和最大的那一段,可以结合区间[l,r]的和、最大前缀和以及最大后缀和。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 20100;
const int Size = 300100;
int a[N]; int num[N]; int root[N];
bool cmp(int x,int y){return a[x]<a[y];}
int tr[Size][2]; int sum[Size];
int lx[Size]; int rx[Size];
int q[4]; int n,m,cnt=0,ans=0;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Pushup(int &t)
{
    int l=tr[t][0],r=tr[t][1];
    sum[t]=sum[l]+sum[r];
    lx[t]=max(lx[l],sum[l]+lx[r]);
    rx[t]=max(rx[r],sum[r]+rx[l]);
}

void Build(int &t,int l,int r)
{
    t=++cnt;
    if(l==r){
        lx[t]=rx[t]=sum[t]=1;
        return;
    }
    int mid=(l+r)>>1;
    Build(tr[t][0],l,mid);
    Build(tr[t][1],mid+1,r);
    Pushup(t); 
}

void Update(int &t,int p,int l,int r,int pos,int v)
{
    t=++cnt;
    tr[t][0]=tr[p][0]; tr[t][1]=tr[p][1];
    if(l==r){
        lx[t]=rx[t]=sum[t]=v;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) Update(tr[t][0],tr[p][0],l,mid,pos,v);
    else Update(tr[t][1],tr[p][1],mid+1,r,pos,v);
    Pushup(t);
}

int Query_all(int t,int L,int R,int l,int r)
{
    if(L==l && R==r) return sum[t];
    int mid=(L+R)>>1;
    if(r<=mid) return Query_all(tr[t][0],L,mid,l,r);
    else if(l>mid) return Query_all(tr[t][1],mid+1,R,l,r);
    else return Query_all(tr[t][0],L,mid,l,mid)+Query_all(tr[t][1],mid+1,R,mid+1,r);
}

int Query_left(int t,int L,int R,int l,int r)
{
    if(L==l && R==r) return lx[t];
    int mid=(L+R)>>1;
    if(r<=mid) return Query_left(tr[t][0],L,mid,l,r);
    else if(l>mid) return Query_left(tr[t][1],mid+1,R,l,r);
    else return max(Query_left(tr[t][0],L,mid,l,mid),Query_all(tr[t][0],L,mid,l,mid)+Query_left(tr[t][1],mid+1,R,mid+1,r));
}

int Query_right(int t,int L,int R,int l,int r)
{
    if(L==l && R==r) return rx[t];
    int mid=(L+R)>>1;
    if(r<=mid) return Query_right(tr[t][0],L,mid,l,r);
    else if(l>mid) return Query_right(tr[t][1],mid+1,R,l,r);
    else return max(Query_right(tr[t][1],mid+1,R,mid+1,r),Query_right(tr[t][0],L,mid,l,mid)+Query_all(tr[t][1],mid+1,R,mid+1,r));
}

bool Check(int k,int l1,int r1,int l2,int r2)
{
    int res=0;
    if(r1+1<l2) res+=Query_all(root[k],0,n-1,r1+1,l2-1);
    res+=Query_right(root[k],0,n-1,l1,r1);
    res+=Query_left(root[k],0,n-1,l2,r2);
    return res>=0;
}

int main()
{
    freopen("2653.in","r",stdin);
    freopen("2653.out","w",stdout);
    n=read();
    for(int i=0;i<n;i++) a[i]=read();
    for(int i=0;i<n;i++) num[i]=i;
    sort(num,num+n,cmp);
    sort(a,a+n);
    Build(root[0],0,n-1);
    for(int i=1;i<n;i++)
        Update(root[i],root[i-1],0,n-1,num[i-1],-1);
    m=read();
    while(m--){
        for(int i=0;i<4;i++) q[i]=read();
        for(int i=0;i<4;i++) q[i]=(q[i]+ans)%n;
        sort(q,q+4);
        int l=0,r=n-1,res=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(Check(mid,q[0],q[1],q[2],q[3])){
                l=mid+1; res=mid;
            }
            else r=mid-1;
        }
        ans=a[res];
        printf("%d\n",ans);
    }
    return 0;
}

Last but not least

这题真心想不出啊。

Comments

comments powered by Disqus