START202——Min-Max Deque · znzryb
## 思路讲解
首先，做这道题目，需要有简单版的基础，简单版就是一个简单的贪心。以下是简单版的代码。
```cpp
FOR(i,2,N){
if(i&1){
if(q.back()>=q.front()){
q.EF(A[i]);
}else{
q.EB(A[i]);
tr.update(i,i);
}
}else{
if(q.back()<=q.front()){
q.EF(A[i]);
}else{
q.EB(A[i]);
tr.update(i,i);
}
}
}
ll ans=min(q.back(),q.front());
```
那复杂版就是多了一个在线修改+询问，一个询问就是把 $A[p]:=x$，然后 naive 的想法就是再跑一遍简单版的程序，当然，不难发现，时间复杂度肯定有问题。
经过简单尝试，我们发现这个**贪心算法不是很好优化**，因此我们可以想办法改进一下我们的这个贪心做法。
我们发现比较难优化，是因为我们想通过一种方法**直接**在 $O(\log n)$ 的时间复杂度内**得到答案**，这无疑有一定的难度。
那么，我们能不能在 $O(\log n)$ 的时间复杂度内判断一个答案可不可行那？
这肯定是比之前的问题简单多了，但也没有那么简单。
假设答案为 $X$，将原数组 $A$ 表示为 $0101...$ ，$0$ 代表 $<X$，$1$ 代表 $≥X$。
我们不难发现（在题设保证 N 为奇数的情况下）：
1. 越后出现越重要。
1. $10101$ 为相持阶段，得到的 $B$ 是 $11$ 类型，或**维持原类型**（即不能抵消 00）。
1. 出现 $11$ 即使得 $B$ 变为 $11$ 类型（抵消一个 00）。
1. 同理，出现 $00$ 即使得 $B$ 变为 $00$ 类型（抵消一个 11）。
那么通过上面发现的性质，那么我们其实就是要找到 $11$ & $00$ 的最靠右出现位置，这个可以使用二分答案+线段树二分 or 二分答案+二分+线段树解决。
具体来说是这样：
```cpp
auto check=[&](int mid){
int pos00=tr.closer00(N,mid);
int pos11=tr.closer11(N,mid); // 使用线段树上二分实现
// pos00==-1 && pos11==-1 说明为1010结构，合法
return pos11>=pos00;
};
auto cal=[&](){
int l=1,r=N;
while (l<r) {
int mid=l+r+1>>1;
if(check(mid)){
l=mid;
}else{
r=mid-1;
}
}
return l;
};
```
代码：
[https://www.codechef.com/viewsolution/1188151973](https://www.codechef.com/viewsolution/1188151973)
时间复杂度$O(n\log^2n)$。
## AC代码
[https://www.codechef.com/viewsolution/1188151973](https://www.codechef.com/viewsolution/1188151973)
::: 源代码
```cpp
// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T>> v){cerr<<"{\n";for (auto i : v) _print(i), cerr << "\n";cerr<<" }";}
#endif
using ll = long long;using ull = unsigned long long;
using ld=double;using LD=long double;
using i128 = __int128;
using pdd = pair<ld,ld>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<ld>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)2e5+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;
inline void __();
ll A[MAXN];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--)
__();
return 0;
}
/*
*/
struct SEG{
int n;vll tro,tre;
SEG(int n):n(n),tro(n*4+5,INF),tre(4*n+5,-INF) {}
void pushup(int o){
tro[o]=min(tro[lson(o)],tro[rson(o)]);
tre[o]=max(tre[lson(o)],tre[rson(o)]);
}
void update(int o,int p,ll x,int l,int r){
if(l==r && r==p){
if(l&1) tro[o]=x;
else tre[o]=x;
return;
}
int mid=l+r>>1;
if(p<=mid && p>=l){
update(lson(o), p, x, l, mid);
pushup(o);
}else{
update(rson(o), p, x, mid+1, r);
pushup(o);
}
}
void update(int p,ll x){
update(1,p,x,1,n);
}
// odd=0
int closer00(int o,int R,int X,int l,int r){
if(l==r){
if(tro[o]<X){
return l;
}
return -1;
}
int pos=-1;
int mid=l+r>>1;
if(R>=mid+1 && tro[rson(o)]<X){
pos=closer00(rson(o),R,X,mid+1,r);
}
if(pos!=-1) return pos;
if(R>=l && tro[lson(o)]<X){
pos=closer00(lson(o),R,X,l,mid);
}
return pos;
}
int closer00(int R,ll X){
return closer00(1,R,X,1,n);
}
int closer11(int o,int R,int X,int l,int r){
if(l==r){
if(tre[o]>=X){
return l;
}
return -1;
}
int pos=-1;
int mid=l+r>>1;
if(R>=mid+1 && tre[rson(o)]>=X){
pos=closer11(rson(o),R,X,mid+1,r);
}
if(pos!=-1) return pos;
if(R>=l && tre[lson(o)]>=X){
pos=closer11(lson(o),R,X,l,mid);
}
return pos;
}
int closer11(int R,ll X){
return closer11(1,R,X,1,n);
}
};
inline void __(){
cin>>N>>Q;
SEG tr(N);
// #ifdef LOCAL
// cerr<<"OK\n";
// #endif
FOR(i,1,N){
cin>>A[i];
tr.update(i,A[i]);
}
// #ifdef LOCAL
// cerr<<"OK2\n";
// #endif
auto check=[&](int mid){
int pos00=tr.closer00(N,mid);
int pos11=tr.closer11(N,mid);
#ifdef LOCAL
debug(pos00);
debug(pos11);
#endif
return pos11>=pos00;
};
auto cal=[&](){
int l=1,r=N;
while (l<r) {
int mid=l+r+1>>1;
if(check(mid)){
l=mid;
}else{
r=mid-1;
}
// #ifdef LOCAL
// debug(l);
// #endif
}
return l;
};
cout<<cal()<<" ";
// #ifdef LOCAL
// cerr<<"OK3\n";
// #endif
FOR(i,1,Q){
ll p,x;cin>>p>>x;
tr.update(p,x);
cout<<cal()<<" ";
}
cout<<"\n";
}
/*
AC
https://www.codechef.com/viewsolution/1188151973
*/
```
:::
## 心路历程（WA，TLE，MLE……）