这题在线做法貌似很麻烦呢……
后来看题解发现了一种奇怪的做法：二分答案 + 线段树。
但是这里线段树可以用珂朵莉树替换，于是我写了珂朵莉树。
二分结果的值为 \(mid\)，然后把整个序列每个 \(a_i\)，若 \(a_i \le mid\)，使 \(a_i \leftarrow 1\)，否则使 \(a_i = 0\)。
那么 \(0/1\) 序列的升序和降序用线段树就可以 \(\log{n}\) 搞，计算区间内 \(1\) 的个数然后乱搞一下就好，
需要用到线段树区间覆盖，区间求和。
但是这一点我用了珂朵莉树。
判定的时候跑一遍所有的修改操作，最后检查 \(a_{q}\) 是否还是 \(1\)。
代码： 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
using namespace std;
const int N = 1e5;
const int M = 1e5;
int n,m,q;
int a[N + 10];
int l,r,mid,ans;
struct node
{
int l,r;
mutable int val;
inline bool operator<(const node &a) const
{
return l < a.l;
}
};
set<node> tree;
typedef set<node>::iterator IT;
inline IT split(int x)
{
IT it = tree.lower_bound((node){x,0,0});
if(it != tree.end() && it->l == x)
return it;
--it;
int l = it->l,r = it->r;
int v = it->val;
tree.erase(it);
tree.insert((node){l,x - 1,v});
return tree.insert((node){x,r,v}).first;
}
inline void assign(int l,int r,int val)
{
IT itr = split(r + 1),itl = split(l);
tree.erase(itl,itr);
tree.insert((node){l,r,val});
}
inline int query(int l,int r)
{
IT itr = split(r + 1),itl = split(l);
int ret = 0;
for(;itl != itr;++itl)
ret += itl->val * (itl->r - itl->l + 1);
return ret;
}
struct s_change
{
int l,r,op;
} chg[M + 10];
bool check()
{
tree.clear();
int last = a[1] >= mid,cnt = 1;
for(register int i = 2;i <= n;++i)
if((a[i] >= mid) == last)
++cnt;
else
{
tree.insert((node){i - cnt,i - 1,last});
last = a[i] >= mid;
cnt = 1;
}
tree.insert((node){n - cnt + 1,n,last});
for(register int i = 1;i <= m;++i)
{
int sum = query(chg[i].l,chg[i].r);
if(sum == chg[i].r - chg[i].l + 1)
assign(chg[i].l,chg[i].r,1);
else if(!chg[i].op)
assign(chg[i].l,chg[i].r - sum,0),assign(chg[i].r - sum + 1,chg[i].r,1);
else
assign(chg[i].l,chg[i].l + sum - 1,1),assign(chg[i].l + sum,chg[i].r,0);
}
return split(q)->val;
}
int main()
{
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
for(register int i = 1;i <= m;++i)
scanf("%d%d%d",&chg[i].op,&chg[i].l,&chg[i].r);
scanf("%d",&q);
l = 1,r = n;
while(l <= r)
{
mid = l + r >> 1;
if(check())
ans = mid,l = mid + 1;
else
r = mid - 1;
}
printf("%d\n",ans);
}