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

$\text{[Problem]}$

给定一个长度为 $n$ 的数组 $a_{1\dots n}$，进行 $m$ 次一下操作：

1. 给定 $l,r$，求出 ∑ l ≤ i < j ≤ r mex { a i , a j } \sum\limits_{l \leq i < j\leq r}\text{mex}\{a_{i},a_{j}\} l≤i<j≤r∑​mex{ai​,aj​}。其中 mex { x 1 , x 2 , … , x n } \text{mex}\{ x_{1},x_{2},\dots,x_{n} \} mex{x1​,x2​,…,xn​} 表示大于等于 $1$ 的最小的未在 $x_{1\dots n}$ 中出现的整数。
2. 给定 $k,x$，修改 $a_k=x$。

$1\le n,m\le 1\times 10^5,1\le l<r\le n,1\le k\le n,1\le a_i,x\le 1\times 10^9$。

$\text{[Analysis]}$

其实 mex { x , y } ( x < y ) \text{mex}\{x,y\}(x<y) mex{x,y}(x<y) 的取值无非就是 $1,2,3$。

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

这题到这里也就做完了。

开一个树状数组分别统计区间内 $1,2$ 出现的次数就可以了。

记得开 long long。

$\text{Code}$

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$ 时等于没改，如果数据纯随机的话，大部分修改都是没用的。

	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);}}

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