http://cogs.pro:8080/cogs/problem/problem.php?pid=1763

二分答案x

把区间内>=x的数设为1，<x的数设为-1

左端点在[a,b]之间,右端点在[c,d]之间的子序列中，若中位数>=x，

那么 [b+1,c-1]的区间和+[a,b]的最大右子段和+[c,d]的最大左子段和>=0

查询可以用线段树

多组询问，不能每一次二分都重设1和-1

所以用主席树

其中第i棵线段树表示<=i的都被设成了-1

因为主席树是线段树的前缀和，所以一次修改只需要改第i棵线段树，就可以得到<=i的都被设成-1的线段树

#include<cstdio>

#include<iostream>

#include<algorithm>

#define N 20001

using namespace std;

int n;

pair<int,int>a[N];

int cnt;

int root[N],lc[N*],rc[N*];

int q[];

struct node

{

    int sum,lmax,rmax;

    node operator + (node p)

    {

        node c;

        c.sum=sum+p.sum;

        c.lmax=max(lmax,sum+p.lmax);

        c.rmax=max(p.rmax,rmax+p.sum);

        return c;

    }

}e[N*],zero;

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

void build(int &k,int l,int r)

{

    k=++cnt;

    if(l==r)

    {

        e[k].sum=e[k].lmax=e[k].rmax=;

        return;

    }

    int mid=l+r>>;

    build(lc[k],l,mid);

    build(rc[k],mid+,r);

    e[k]=e[lc[k]]+e[rc[k]];

}

void change(int pre,int &k,int l,int r,int pos)

{

    k=++cnt;

    if(l==r)

    {

        e[k].sum=e[k].lmax=e[k].rmax=-;

        return;

    }

    int mid=l+r>>;

    if(pos<=mid)

    {

        rc[k]=rc[pre];

        change(lc[pre],lc[k],l,mid,pos);

    }

    else

    {

        lc[k]=lc[pre];

        change(rc[pre],rc[k],mid+,r,pos);

    }

    e[k]=e[lc[k]]+e[rc[k]];

}

node query(int k,int l,int r,int opl,int opr)

{

    if(opl>opr) return zero;

    if(l>=opl && r<=opr) return e[k];

    int mid=l+r>>;

    if(opr<=mid) return query(lc[k],l,mid,opl,opr);

    if(opl>mid) return query(rc[k],mid+,r,opl,opr);

    return query(lc[k],l,mid,opl,opr)+query(rc[k],mid+,r,opl,opr);

}

bool check(int pos)

{

    if(query(root[pos],,n,q[],q[]).rmax+query(root[pos],,n,q[]+,q[]-).sum+query(root[pos],,n,q[],q[]).lmax>=) return true;

    return false;

}

int main()

{

    freopen("nt2012_middle.in","r",stdin);

    freopen("nt2012_middle.out","w",stdout);

    read(n);

    for(int i=;i<=n;++i)

    {

        read(a[i].first);

        a[i].second=i;

    }

    sort(a+,a+n+);

    build(root[],,n);

    for(int i=;i<=n;++i) change(root[i-],root[i],,n,a[i].second);

    int m;

    read(m);

    int ans=;

    int l,r,mid;

    while(m--)

    {

        for(int i=;i<;++i)

        {

            read(q[i]);

            q[i]+=ans;

            q[i]%=n;

            q[i]++;

        }

        sort(q,q+);

        l=,r=n;

        while(l<=r)

        {

            mid=l+r>>;

            if(check(mid-)) ans=mid,l=mid+;

            else r=mid-;

        }

        ans=a[ans].first;

        cout<<ans<<'\n';

    }

}

1763. [国家集训队2012]middle

★★★☆ 输入文件：nt2012_middle.in 输出文件：nt2012_middle.out 简单对比
时间限制：3 s 内存限制：1024 MB

middle(陈立杰)

时间限制：3.0s 内存限制：1.0GB

【大意】

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

【输入格式】

第一行序列长度n。
接下来n行按顺序给出a中的数。
接下来一行Q。
然后Q行每行a,b,c,d，我们令上个询问的答案是x(如果这是第一个询问则x=0)。
令数组q={(a+x)%n,(b+x)%n,(c+x)%n,(d+x)%n}。
将q从小到大排序之后，令真正的要询问的a=q[0],b=q[1],c=q[2],d=q[3]。
输入保证满足条件。

【输出格式】

Q行依次给出询问的答案。

【数据规模和约定】

0:n,Q<=100
1,...,5:n<=2000
0,...,19:n<=20000,Q<=25000

【样例输入】

5
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0

【样例输出】

271451044
271451044
969056313