[二分][主席树] Luogu P2839 Middle

题目描述

一个长度为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行依次给出询问的答案。

输入输出样例

输入样例#1：

输出样例#1：

271451044
271451044
969056313

说明

0:n,Q<=100

1,...,5:n<=2000

0,...,19:n<=20000,Q<=25000

题解

考虑二分答案，那么当前mid是合法的情况就是存在一个序列，比它大的个数等于比它小的个数
那么我们就可以把比它大的数看作是1，比它小的就是-1，一个合法序列的和>=0
那么就是相当于求在左端点在[a,b]中右端点在[c,d]中的最大子段和
这个东西可以拆分成[a~b]的最大后缀和，[b+1~c-1]的和，和[c~d]最大前缀和
怎么维护这个东东呢，用线段树的话空间会爆炸，那我们就可以打主席树动态开点

代码

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define N 20010
 6 using namespace std;
 7 struct note{int v,d;}a[N];
 8 struct node{int s,ls,rs,l,r;}t[N*30];
 9 int ans,tot,n,m,root[N],q[4];
10 bool cmp(note a,note b) { return a.v<b.v; }
11 node merge(node y,node z) 
12 {
13     node x;
14     x.s=y.s+z.s,x.ls=max(y.ls,y.s+z.ls),x.rs=max(z.rs,z.s+y.rs);
15     return x;
16 }
17 void pushup(int d)
18 {
19     int l=t[d].l,r=t[d].r;
20     t[d].s=t[l].s+t[r].s,t[d].ls=max(t[l].ls,t[l].s+t[r].ls),t[d].rs=max(t[r].rs,t[l].rs+t[r].s);
21 }
22 void build(int &d,int l,int r)
23 {
24     d=++tot;
25     if (l==r) { t[d].s=t[d].ls=t[d].rs=1; return; }
26     int mid=l+r>>1;
27     build(t[d].l,l,mid),build(t[d].r,mid+1,r),pushup(d);
28 }
29 void change(int &d,int l,int r,int x)
30 {
31     t[++tot]=t[d],d=tot;
32     if (l==r) { t[d].s=t[d].ls=t[d].rs=-1; return; }
33     int mid=l+r>>1;
34     if (x<=mid) change(t[d].l,l,mid,x); else change(t[d].r,mid+1,r,x); pushup(d);
35 }
36 node find(int d,int l,int r,int x,int y)
37 {
38     if (x>y) return t[0];
39     if (l==x&&r==y) return t[d];
40     int mid=l+r>>1;
41     if (y<=mid) return find(t[d].l,l,mid,x,y);
42     else if (x>mid) return find(t[d].r,mid+1,r,x,y);
43     else return merge(find(t[d].l,l,mid,x,mid),find(t[d].r,mid+1,r,mid+1,y));
44 }
45 bool check(int x) { return find(root[x],1,n,q[0],q[1]).rs+find(root[x],1,n,q[1]+1,q[2]-1).s+find(root[x],1,n,q[2],q[3]).ls>=0; }
46 int main()
47 {
48     scanf("%d",&n);
49     for (int i=1;i<=n;i++) scanf("%d",&a[i].v),a[i].d=i;
50     sort(a+1,a+n+1,cmp),build(root[1],1,n);
51     for (int i=2;i<=n;i++) root[i]=root[i-1],change(root[i],1,n,a[i-1].d);
52     for (scanf("%d",&m);m;m--)
53     {
54         for (int i=0,x;i<4;i++) scanf("%d",&x),q[i]=(x+ans)%n+1;
55         sort(q,q+4); int l=1,r=n+1,mid;
56         while (l<r)
57         {
58             int mid=l+r>>1;
59             if (check(mid)) l=mid+1; else r=mid; 
60         }
61         printf("%d
",ans=a[l-1].v);
62     }
63 }