自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 22:49:25，当前版本为作者最后更新于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;
}