about 4 years ago

又是一道主席树。可以去找丽洁姐的解题报告。觉得是非常好的一道题。
一般的主席树是按点的顺序,也就是每个点的位置对应一棵小线段树,把点的值离散后再插进去
但是这道题!!是按点值排序后(就按点值的位置啦),把每个点的位置插进去。
非常奇妙的想法!!!
然后对着正确的部分调了快1个小时我就不说什么了……
bug在于查询lmax和rmax时如果跨越mid,不能只算sum(left)+lmax(right),还要与lmax(left)作比较
这提醒我们做事要分类T_T

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define maxn 20001
#define maxm 600001
#define l(x) son[x][0]
#define r(x) son[x][1]
#define s(x) sum[x]
using namespace std;
int n,Q,tot=0;int q[4];
int num[maxn]={0},son[maxm][2],sum[maxm],lx[maxm],rx[maxm],dy[maxn];
struct node {int num,pos;} a[maxn];
int readln()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0'))c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return bj*result;
}
bool cmp(const node a,const node b)
{
    if (a.num==b.num) return a.pos<b.pos;
    return a.num<b.num;
}
void update(int now)
{
    sum[now]=sum[l(now)]+sum[r(now)];
    lx[now]=max(max(lx[l(now)],sum[l(now)]+lx[r(now)]),max(0,sum[l(now)]));
    rx[now]=max(max(rx[r(now)],sum[r(now)]+rx[l(now)]),max(0,sum[r(now)]));
}
int segment(int left,int right)
{
    if (left==right) {tot++;lx[tot]=rx[tot]=sum[tot]=1;return tot;}
    int re=++tot;int mid=(left+right)>>1;
    l(re)=segment(left,mid);
    r(re)=segment(mid+1,right);
    update(re);return re;
}
int build(int old,int left,int right,int pos)
{
    if (left==right) {tot++;lx[tot]=rx[tot]=sum[tot]=-1;return tot;}
    int re=++tot,mid=(left+right)>>1;
    if (pos<=mid) {r(re)=r(old);l(re)=build(l(old),left,mid,pos);}
    if (pos>mid) {l(re)=l(old);r(re)=build(r(old),mid+1,right,pos);}
    update(re);return re;
}
int querysum(int now,int s,int t,int left,int right)
{
    if (s<=left&&t>=right) return sum[now];
    int mid=(left+right)>>1,temp=0;
    if(s<=mid) temp+=querysum(l(now),s,t,left,mid);
    if (mid<t) temp+=querysum(r(now),s,t,mid+1,right);
    return temp; 
}
int queryright(int now,int s,int t,int left,int right)//PAY ATTENTION!!
{
    if (s<=left&&right<=t) return rx[now];
    int mid=(left+right)>>1,l=0,r=0;
    if (s<=mid)
    {
     if (t<=mid) l=queryright(l(now),s,t,left,mid);
     else l=querysum(r(now),s,t,mid+1,right)+queryright(l(now),s,t,left,mid);
    }
    if (t>mid) r=queryright(r(now),s,t,mid+1,right);
    return max(l,r); 
}
int queryleft(int now,int s,int t,int left,int right)//PAY ATTENTION!! 
{
    if (s<=left&&right<=t)return lx[now];
    int mid=(left+right)>>1,l=0,r=0;
    if (s<=mid)
    {
        l=queryleft(l(now),s,t,left,mid);
        if (t>mid) r=querysum(l(now),s,t,left,mid)+queryleft(r(now),s,t,mid+1,right);
    }
    else     r=queryleft(r(now),s,t,mid+1,right);
    return max(l,r);
}
bool judge(int num,int a,int b,int c,int d)
{
    int result=querysum(dy[num],b,c,1,n);
    int temp=0;
    if (a<=b-1) temp=queryright(dy[num],a,b-1,1,n);
    if (temp>0) result+=temp;
    temp=0;if (c+1<=d) temp=queryleft(dy[num],c+1,d,1,n);
    if (temp>0) result+=temp;
    if (result>=0) return true;return false; 
}
int main()
{
    int i,left,right,mid,x=0;
    n=readln();
    for (i=1;i<=n;i++) a[i].num=readln(),a[i].pos=i;
    sort(a+1,a+n+1,cmp);
    dy[0]=segment(1,n);
    for (i=1;i<=n;i++) dy[i]=build(dy[i-1],1,n,a[i].pos);
    Q=readln();
    for (;Q;Q--)
    {
        for (i=0;i<4;i++) q[i]=(int)((readln()+(long long)x)%n+1);
        sort(q,q+4);
        left=1;right=n;
        while (left<right)
        {
            mid=(left+right+1)>>1;      
            if (judge(mid-1,q[0],q[1],q[2],q[3])) left=mid;
            else right=mid-1;
        }
        x=a[right].num;
        printf("%d\n",x);
    }
}
← 【bzoj2588】【spoj10628】【主席树】count on a tree zkw费用流 →
 
comments powered by Disqus