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

· · 题解

首先判掉单个点。

考虑两端都是 0 的一条链，易知起点距离某一端为奇数时先手必胜，否则后手必胜。根据链长容易得出链中先手必胜位置。

考虑环，若环中有 0 是类似的。否则当环长为奇数时，先手直接把一条边删去就能进入到上面提到的情况，此时也是先手必胜。

否则考虑有 1 的情况，由于边权变为 0 相当于先手必胜，可以直接把 1 也看成 0 做类似的事情。

归纳一下，不难得出环中最小值等价于一开始的 0。于是直接用线段树维护区间最小值的最前后两个位置和区间内答案即可。

:::success[点击查看参考代码]

#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
*/

:::