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

HPXXZYY · 2025-06-20 21:27:33 · 题解

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

1. 给定 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} 中出现的整数。
2. 给定 k,x，修改 a_{k}=x。

其实 \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。

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

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

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