START202——Min-Max Deque

思路讲解

首先，做这道题目，需要有简单版的基础，简单版就是一个简单的贪心。以下是简单版的代码。

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. 越后出现越重要。

2. $10101$ 为相持阶段，得到的 $B$ 是 $11$ 类型，或维持原类型（即不能抵消 00）。

3. 出现 $11$ 即使得 $B$ 变为 $11$ 类型（抵消一个 00）。

4. 同理，出现 $00$ 即使得 $B$ 变为 $00$ 类型（抵消一个 11）。

那么通过上面发现的性质，那么我们其实就是要找到 $11$ & $00$ 的最靠右出现位置，这个可以使用二分答案+线段树二分 or 二分答案+二分+线段树解决。

具体来说是这样：

  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

时间复杂度$O(n\log^2n)$。

AC代码

https://www.codechef.com/viewsolution/1188151973

源代码

// 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……）