bzoj_2653 middle

题目:

   一个长度为n的序列a,设其排过序之后为b,其中位数定义为b[n/2],其中a,b从0开始标号,除法取下整。给你一个长度为n的序列s。回答Q个这样的询问:s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中,最大的中位数。其中a< b < c < d。位置也从0开始标号。我会使用一些方式强制你在线。
   第一行所谓“排过序”指的是从小到大排序!

思路:

   题目描述的很迷啊,其实第一句话的意思就是的中位数是.....
   常见的思路,看到中位数可以考虑二分中位数的值,把小于二分值的设为,大于等于的设为。如果一个区间的和大于等于,说明当前二分值大于等于实际中位数。
   但是如果这样每次二分都要重建一棵线段树,那么每次查询的复杂度就是的。如果先预处理出这些线段树,就会有棵线段树,考虑到两棵线段树之间只有一个数字不同,所以可以考虑用主席树(或函数式线段树?其实我分不清这两个东西qwq)优化。
   那么问题就变成了判断能否找到一个区间。那么只要找到这个区间的最大值就行了,这个问题在GSS系列题中遇到过,大致就是中间必取,两端取一个从左(右)开始的最长连续和。

代码:

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
template<class T> inline bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T> inline bool tomin(T &a,T b){return a>b?a=b,1:0;}
using std::max;using std::min;
const int N=20005;

struct Node{
    int sum,lmax,rmax;
    Node operator + (const Node _) const {
        return (Node){
            sum+_.sum,
            max(sum+_.lmax,lmax),
            max(rmax+_.sum,_.rmax)
        };
    }
    void set(int x){
        sum=x;lmax=rmax=0;
        if(x>0)lmax=rmax=x;
    }
}node[N*40];
int ls[N*40],rs[N*40],tot;
#define mid (L+R>>1)
#define lson ls[o],L,mid
#define rson rs[o],mid+1,R
void copyNode(int &o){
    node[++tot]=node[o];
    ls[tot]=ls[o];rs[tot]=rs[o];
    o=tot;
}
void build(int &o,int L,int R){
    copyNode(o);
    if(L==R)return node[o].set(1);
    build(lson);build(rson);
    node[o]=node[ls[o]]+node[rs[o]];
}
void upd(int x,int v,int &o,int L,int R){
    copyNode(o);
    if(L==R)return node[o].set(v);
    if(x<=mid)upd(x,v,lson);
    else upd(x,v,rson);
    node[o]=node[ls[o]]+node[rs[o]];
}
Node qry(int l,int r,int o,int L,int R){
    if(l==L&&r==R)return node[o];
    if(r<=mid)return qry(l,r,lson);
    else if(l>mid)return qry(l,r,rson);
    else return qry(l,mid,lson)+qry(mid+1,r,rson);
}

int a[N],num[N],rt[N],n,cnt,kth[N];
struct Data{
    int pos,val;
    bool operator < (const Data _) const {
        return val<_.val;
    }
}d[N];

void init(){
    build(rt[0],1,n);
    std::sort(d+1,d+1+n);
    rep(i,1,n){
        rt[i]=rt[i-1];
        kth[d[i].pos]=i;
        num[i]=a[d[i].pos];
        if(i!=1)upd(d[i-1].pos,-1,rt[i],1,n);
    }
}

bool check(int a,int b,int c,int d,int k){
    int o=rt[k];
    Node nod1=qry(a,b-1,o,1,n),nod2=qry(c+1,d,o,1,n);
    int sum=qry(b,c,o,1,n).sum;
    return nod1.rmax+sum+nod2.lmax>=0;
}
int solve(int a,int b,int c,int d){
    int L=1,R=n,ans;
    while(L<=R){
        int k=check(a,b,c,d,mid);
        if(check(a,b,c,d,mid))
            ans=num[mid],L=mid+1;
        else    
            R=mid-1;
    }
    return ans;
}

int main(){
    scanf("%d",&n);
    rep(i,1,n){
        scanf("%d",a+i);
        d[i]=(Data){i,a[i]};
    }
    init();
    int q,lastans=0;
    scanf("%d",&q);
    rep(i,1,q){
        int p[4];
        rep(j,0,3){
            scanf("%d",p+j);
            p[j]=(p[j]+lastans)%n+1;
        }
        std::sort(p,p+4);
        printf("%d\n",lastans=solve(p[0],p[1],p[2],p[3]));
    }
    return 0;
}