题解：P9546 [湖北省选模拟 2023] 山路长环 / ring

#include<bits/stdc++.h>
#define TIME chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()
#define rep(i,l,r) for(int qwp=(r),i=(l);i<=qwp;i++)
#define per(i,r,l) for(int qwp=(l),i=(r);i>=qwp;i--)
using namespace std;
constexpr int MB=1<<20;
struct FastIO{
	char ib[MB+100],*p,*q;char ob[MB+100],*r,stk[128];int tp;
	FastIO(){p=q=ib,r=ob,tp=0;}~FastIO(){fwrite(ob,1,r-ob,stdout);}
	char read_char(){if(p==q){p=ib,q=ib+fread(ib,1,MB,stdin);if(p==q)return 0;}return *p++;}
	template<typename T>void read_int(T& x){char c=read_char(),l=0;for(x=0;!isdigit(c);c=read_char())l=c;for(;isdigit(c);c=read_char())x=x*10-'0'+c;if(l=='-')x=-x;}
    void write_char(char c){if(r-ob==MB)r=ob,fwrite(ob,1,MB,stdout);*r++=c;}
	template<typename T>void write_int(T x){if(x<0)write_char('-'),x=-x;do stk[++tp]=x%10+'0';while(x/=10);while(tp)write_char(stk[tp--]);}
}IO;
namespace ax_by_c{
constexpr int N=3e5+5;
struct node{int mn,p,q,ans;};
inline int cal(int len){return len>>(len&1);}
inline node operator + (const node &x,const node &y){return ((x.mn==y.mn)?((node){x.mn,x.p,y.q,x.ans+y.ans+cal(y.p-x.q)}):((x.mn<y.mn)?(x):(y)));}
int n,m,a[N];
struct DS1{
    node tr[N*4];
    inline void pu(int u){tr[u]=(tr[u<<1]+tr[u<<1|1]);}
    void bld(int u,int l,int r){
        if(l==r)return (void)(tr[u]={a[l],l,l,0});
        int mid=l+((r-l)>>1);bld(u<<1,l,mid),bld(u<<1|1,mid+1,r),pu(u);
    }
    void upd(int u,int l,int r,int p,int z){
        if(l==r)return (void)(tr[u]={z,l,l,0});
        int mid=l+((r-l)>>1);if(p<=mid)upd(u<<1,l,mid,p,z);else upd(u<<1|1,mid+1,r,p,z);pu(u);
    }
    node Q(int u,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr)return tr[u];
        int mid=l+((r-l)>>1);
        if(qr<=mid)return Q(u<<1,l,mid,ql,qr);if(mid+1<=ql)return Q(u<<1|1,mid+1,r,ql,qr);
        return Q(u<<1,l,mid,ql,qr)+Q(u<<1|1,mid+1,r,ql,qr);
    }
}tr;
void main(){
    IO.read_int(n),IO.read_int(m);rep(i,1,n)IO.read_int(a[i]);tr.bld(1,1,n);
    rep(_,1,m){
        int o;IO.read_int(o);
        if(o==1){int x,y;IO.read_int(x),IO.read_int(y),a[x]=y,tr.upd(1,1,n,x,y);}
        if(o==2){
            int l,r;IO.read_int(l),IO.read_int(r);node z=tr.Q(1,1,n,l,r);
            if(l==r)IO.write_int(((a[l])?(1):(0)));
            else if(z.mn&&((r-l+1)&1))IO.write_int(r-l+1);
            else IO.write_int(z.ans+cal(z.p-l+1+r-z.q));
            IO.write_char('\n');
        }
    }
}
}
int main(){
    auto _Tbe=TIME;
    // freopen("game.in","r",stdin);
    // freopen("game.out","w",stdout);
    ax_by_c::main();
    auto _Ted=TIME;
    cerr<<"\nTIME:"<<_Ted-_Tbe<<'\n';
    return 0;
}
/*
ulimit -s 524288
g++ -O2 -std=c++14 -static game.cpp -o game.exe
g++ -O2 -std=c++14 -fsanitize=address,leak,undefined game.cpp -o game.exe
./game.exe
*/