(luogu2839)middle

发表于 分类于 ， ，

原题链接

十分巧妙的主席树题

思路:

类似于 P1168, 有一个使用二分求区间中位数的方法:

对于数 x, 将 >=x 的值标为 1, <x 的值标为 - 1.

然后将询问区间的标号加起来，若和 >=0 表示中位数可能比 x 更大， 否则中位数一定比 x 更小.

对于这题来说，虽然区间是不固定的，但也可以借鉴上述思想:

对于数 x, 首先区间 (b, c) 是固定的，求出这段区间的标号和.

然后对于区间 [a,b], 求出这段区间的最大后缀标号和 , 同样对于 [c,d] 求出其最大前缀标号和.

若这三个值的和 >=0 则说明可能存在符合条件的比 x 更大的中位数， 否则说明最大的中位数比 x 更小.

同时注意到如果从小到大对数 x 建立线段树维护标号 , 则每个位置的值只会改变一次， 于是可以使用主席树将这些线段树结合起来.

所以不同于以往在区间上建立值域线段树， 这次是在值域上建立区间的线段树.

注意 (b, c) 区间有可能不存在.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int Mn(20050);

template<typename T> void qrd(T& x) {
    x = 0;
    char c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c - '0';
        c = getchar();
    }
}

int n,q;
int ld; //数字个数
int a[Mn],da[Mn];   //原数组, 离散化数组
vector<int> vp[Mn]; //每个值的位置
struct td { //线段树节点
    int lsm,rsm,sum;
    td *ls,*rs;
}*rts[Mn],mem[Mn*40],* const nil = mem;
td* new_td(td x = *nil) {
    static int mc = 0;
    mem[++mc] = x;
    return mem+mc;
}
void upd(td* rt) {
    rt->sum = rt->ls->sum + rt->rs->sum;
    rt->lsm = max(rt->ls->lsm, rt->ls->sum+rt->rs->lsm);
    rt->rsm = max(rt->rs->rsm, rt->rs->sum+rt->ls->rsm);
}
void ibud(td*& rt,int l,int r) {    //建立初始线段树
    if(rt==nil) {
        rt = new_td();
    }
    if(l==r) {
        rt->lsm = rt->rsm = rt->sum = 1;
        return;
    }
    int mid((l+r)/2);
    ibud(rt->ls,l,mid);
    ibud(rt->rs,mid+1,r);
    upd(rt);
}
void imdf(td*& rt,int l,int r,int mp) { //主席树修改
    rt = new_td(*rt);
    if(l==r) {
        rt->lsm = rt->rsm = 0;
        rt->sum = -1;
        return;
    }
    int mid((l+r)/2);
    if(mp<=mid) {
        imdf(rt->ls,l,mid,mp);
    } else {
        imdf(rt->rs,mid+1,r,mp);
    }
    upd(rt);
}
void init() {   //初始化
    *nil = {0,0,0,nil,nil};
    memcpy(da+1,a+1,sizeof(int)*n);
    /*离散化*/
    sort(da+1,da+n+1);
    ld = unique(da+1,da+n+1) - da - 1;
    for(int i(1);i<=n;++i) {
        int p = lower_bound(da+1,da+ld+1,a[i]) - da;
        vp[p].push_back(i);
    }
    /*建立主席树*/
    rts[1] = nil;
    ibud(rts[1],1,n);
    for(int i(2);i<=ld;++i) {
        rts[i] = rts[i-1];
        for(int aj: vp[i-1]) {
            imdf(rts[i],1,n,aj);
        }
    }
}
td qry(td* rt,int l,int r,int ql,int qr) {  //查询
    if(ql>r || qr<l || ql>qr) {
        return *nil;
    }
    if(l>=ql && r<=qr) {
        return *rt;
    }
    int mid((l+r)/2);
    td ret = *nil, lqd = *nil, rqd = *nil;
    if(ql<=mid) {
        lqd = qry(rt->ls,l,mid,ql,qr);
    }
    if(qr>mid) {
        rqd = qry(rt->rs,mid+1,r,ql,qr);
    }
    ret.sum = lqd.sum + rqd.sum;
    ret.lsm = max(lqd.lsm,lqd.sum + rqd.lsm);
    ret.rsm = max(rqd.rsm,rqd.sum + lqd.rsm);
    return ret;
}

int main() {
    qrd(n);
    for(int i(1);i<=n;++i) {
        qrd(a[i]);
    }
    init();
    qrd(q);
    int qx(0);  //上次询问答案
    while(q--) {
        int x,y,z,w;
        qrd(x), qrd(y), qrd(z), qrd(w);
        int pr[4] = {(x+qx)%n+1,(y+qx)%n+1,(z+qx)%n+1,(w+qx)%n+1};  //询问解密
        sort(pr,pr+4);
        int l(1), r(ld);
        while(l<r) {    //二分
            int mid((l+r+1)/2);
            int tmp = qry(rts[mid],1,n,pr[1],pr[2]).sum + qry(rts[mid],1,n,pr[0],pr[1]-1).rsm + qry(rts[mid],1,n,pr[2]+1,pr[3]).lsm;
            if(tmp>=0) {
                l = mid;
            } else {
                r = mid-1;
            }
        }
        printf("%d\n",qx = da[l]);
    }
    return 0;
}