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

Rainbow_qwq · 2023-08-26 07:59:36 · 题解

首先考察环上有 0 的情况：

• 如果一个点和一个 0 边相邻，那就只能向另一个方向走，并且必须把这条边的边权走完，否则对手走回来就无法再走。
• 因此，若和一个 0 边相邻，两人接下来的走法固定，如果此时到下一个 0 边的距离为奇数，则先手胜利。
• 设一个点到两边最近 0 边的距离为 l,r，则如果 l,r 之中有任意一个为奇数，则往那个方向走并且把边权走完，即可胜利。
• 否则不难发现先手不管怎么走，后手都能胜利。

如果两个 0 之间有奇数个，那 l,r 必有一个为奇数，之间的点都是必胜点；否则之间的点有一半为必胜点。

相当于环被 0 切分成了若干条链，每条链有一个贡献（分链长奇偶不同）。

然后考察环上全部大于 0 的情况：

• 如果环长 n 为奇数，那先手可以把任意一条边走成 0，让后手陷入必败态，于是所有位置必胜。
• 如果环长 n 为偶数，那先后手都要避免把自己一条边走成 0。

把第一种情况特判掉，下面分析第二种情况。容易发现此时两边如果是 [1,1] 的话，走哪边都会出现 0，则为必败态。

如果一个人遇到一边有 1，一边为 >1 的情况，那肯定要往 >1 的方向走，而且必须把这条边走成 1，否则对手可以走回来。

于是发现上面的那套分析 0 的情况都可以套过来！也就是说，如果环上有 1，可以把所有 1 当成 0，答案不变。

进一步猜测，可以把所有环上最小值的位置当成 0，答案不变。经过打表发现确实如此。

于是只要维护区间最小值，以及区间最小值把环砍成的若干条链的贡献。

不难用线段树维护，时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
//#define int long long
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 300005
#define inf 0x3f3f3f3f

int n,Q,a[maxn];

struct node{
    int mn,l,r,len,res;
};
int F(int x){
    return x%2?x+1:x/2;
}
node operator +(node a,node b){
    if(a.mn<b.mn){
        a.len+=b.len;
        a.r+=b.len;
        return a;
    }
    if(a.mn>b.mn){
        b.len+=a.len;
        b.l+=a.len;
        return b;
    }
    node c;
    c.mn=a.mn;
    c.l=a.l;
    c.r=b.r;
    c.len=a.len+b.len;
    c.res=a.res+b.res+F(a.r+b.l);
    return c;
}

node tr[maxn<<2];
void up(int p){
    tr[p]=tr[p<<1]+tr[p<<1|1];
}
void build(int p,int l,int r){
    if(l==r)return tr[p]={a[l],0,0,1,0},void();
    int mid=l+r>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r),up(p);
}
void mdf(int p,int l,int r,int x){
    if(l==r)return tr[p]={a[l],0,0,1,0},void();
    int mid=l+r>>1;
    x<=mid?mdf(p<<1,l,mid,x):mdf(p<<1|1,mid+1,r,x); up(p);
}
node ask(int p,int l,int r,int ql,int qr){
    if(l>=ql&&r<=qr)return tr[p];
    int mid=l+r>>1;
    if(qr<=mid)return ask(p<<1,l,mid,ql,qr);
    if(ql>mid)return ask(p<<1|1,mid+1,r,ql,qr);
    return ask(p<<1,l,mid,ql,qr)+ask(p<<1|1,mid+1,r,ql,qr);
}

int chk(vi a){
    int mn=*min_element(a.begin(),a.end());
    if(mn>0 && a.size()%2)return 1;
    int p=0,q=0;
    while(a[p]!=mn)++p;
    while(a[a.size()-q-1]!=mn)++q;
    return p%2||q%2;
}

int ask(int l,int r){
    node t=ask(1,1,n,l,r);
    if(t.mn>0 && t.len%2)return t.len;
    return t.res+F(t.r+t.l);
}

signed main()
{
    n=read(),Q=read();
    For(i,1,n)a[i]=read();
    build(1,1,n);
    For(_,1,Q){
        int op=read(),x=read(),y=read();
        if(op==1)a[x]=y,mdf(1,1,n,x);
        else cout<<ask(x,y)<<"\n";
    }
    return 0;
}