题解：P12894 [蓝桥杯 2025 国 Java B] 智能交通信号灯

\color{blue}{\texttt{[Problem]}}

给定一个长度为

n

的数组

a_{1\dots n}

，进行

m

次一下操作：

给定 $l,r$ ，求出 $\sum\limits_{l \leq i < j\leq r}\text{mex}\{a_{i},a_{j}\}$ 。其中 $\text{mex}\{ x_{1},x_{2},\dots,x_{n} \}$ 表示大于等于 $1$ 的最小的未在 $x_{1 \dots n}$ 中出现的整数。
给定 $k,x$ ，修改 $a_{k}=x$ 。

1 \leq n,m \leq 1\times 10^{5}, 1 \leq l < r \leq n, 1 \leq k \leq n, 1\leq a_{i},x \leq 1 \times 10^{9}

。

\color{blue}{\texttt{[Analysis]}}

其实

\text{mex}\{x,y\}(x<y)

的取值无非就是

1,2,3

。

当 $x=1,y=2$ 时， $\text{mex}=3$ 。
当 $x=1,y \not = 2$ 时， $\text{mex}=2$ 。
否则 $\text{mex}=1$ 。

这题到这里也就做完了。

开一个树状数组分别统计区间内

1,2

出现的次数就可以了。

记得开 long long。

\color{blue}{\text{Code}}

CPP

const int N=1e5+100;

class Fenwick_Tree{
	public:
		void set_size(int n){
			this->n=n;
			for(int i=1;i<=n;i++)
				c[i]=0;
		}
		void modify(int x,int val){
			for(int i=x;i<=n;i+=lowbit(i))
				c[i]+=val;
		}
		int query(int x){
			int ans=0;
			for(int i=x;i;i-=lowbit(i))
				ans+=c[i];
			
			return ans;
		}
	private:
		int c[N],n;
		int lowbit(int x){
			return x&(-x);
		}
}cnt[2];

int query(int num,int l,int r){
	if (num<1||num>2) return -1;
	
	--num;
	return cnt[num].query(r)-cnt[num].query(l-1);
}

typedef long long ll;
#define sum(n) (1ll*(n)*((n)-1)/2)
ll query(int l,int r){
	int n=r-l+1;
	int x=query(1,l,r),y=query(2,l,r),z=n-x-y;
	
	return 3ll*x*y+2ll*sum(x)+2ll*x*z+1ll*(sum(n)-1ll*x*y-sum(x)-1ll*x*z);
}

int n,m,a[N];

int main(){
	n=read();m=read();
	
	cnt[0].set_size(n);
	cnt[1].set_size(n);
	
	for(int i=1;i<=n;i++){
		a[i]=read();
		if (a[i]<=2)
			cnt[a[i]-1].modify(i,1);
	}
	
	for(int i=1;i<=m;i++){
		int opt=read(),l=read(),r=read();
		
		if (opt==1) printf("%lld\n",query(l,r));
		else{
			if (a[l]<=2)
				cnt[a[l]-1].modify(l,-1);
			
			a[l]=r;
			if (a[l]<=2)
				cnt[a[l]-1].modify(l,1);
		}
	}
	
	return 0;
}

顺便一说，这题的数据好水啊。犯了一个及其低级的错误，但是还能拿

75

分。

不过可以理解，毕竟修改操作

a_{i},x

都大于等于

3

时等于没改，如果数据纯随机的话，大部分修改都是没用的。

CPP

	for(int i=1;i<=m;i++){
		int opt=read(),l=read(),r=read();
		
		if (opt==1) printf("%lld\n",query(l,r));
		else{
			if (a[l]<=2)
				cnt[a[l]-1].modify(i,-1);
			
			a[l]=r;
			if (a[l]<=2)
				cnt[a[l]-1].modify(i,1);
		}
	}

考验一下大家，能不能找出错误在哪。

答案：modify 那里把 l 写成 i 了。

题解：P12894 [蓝桥杯 2025 国 Java B] 智能交通信号灯

文章操作

相关推荐

评论

题解：P12894 [蓝桥杯 2025 国 Java B] 智能交通信号灯