题解 100% AC

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int vec[N],n;
int main(){
    int t;
    cin>>t;
    for(int ca=1;ca<=t;ca++){
        if(ca==1){
            cin>>n;
            for(int i=1;i<=n;i++) cin>>vec[i];
        }
        else{
            int k;
            cin>>k;
            while(k--){
                int x,y;
                cin>>x>>y;
                vec[x]=y;
            }
        }
        deque<pair<int,int>> dq1,dq2;
        for(int j=1;j<=n;j++) dq1.push_back(make_pair(vec[j],j));
        int ans;
        while(true){
            if(dq1.size()+dq2.size()==2){
                ans=1;
                break;
            }
            int small=dq1.front().first;
            dq1.pop_front();
            int big, id;
            if(dq2.empty() || (!dq1.empty() && dq1.back() > dq2.back())){
                big=dq1.back().first;
                id=dq1.back().second;
                dq1.pop_back();
            }
            else{
                big=dq2.back().first;
                id=dq2.back().second;
                dq2.pop_back();
            }
            pair<int,int> cur={big-small,id};
            if(dq1.empty() || cur < dq1.front()){
                ans=dq1.size()+dq2.size()+2;
                int cnt=0;
                while(true){
                    cnt++;
                    if(dq1.size()+dq2.size()+1==2){
                        if(cnt%2==0) ans--;
                        break;
                    }
                    int new_big, new_id;
                    if(dq2.empty() || (!dq1.empty() && dq1.back() > dq2.back())){
                        new_big=dq1.back().first;
                        new_id=dq1.back().second;
                        dq1.pop_back();
                    }
                    else{
                        new_big=dq2.back().first;
                        new_id=dq2.back().second;
                        dq2.pop_back();
                    }
                    cur={new_big-cur.first,new_id};
                    if((dq1.empty() || cur < dq1.front()) && (dq2.empty() || cur < dq2.front())){
                        continue;
                    }
                    else{
                        if(cnt%2==0) ans--;
                        break;
                    }
                }
                break;
            }
            else{
                dq2.push_front(cur);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}