Light

题意

有一排 $n$ 个灯。所有灯都带有颜色，用 $1$ 至 $m$ 的正整数表示。初始时所有灯都是关着的。

有 $q$ 组操作，每次反转所有某种颜色的灯的状态。在每次操作后回答所有开着的灯构成了多少个不可扩展的连续子段。

解析

设定一个常数 $k$。当我们修改某个出现次数小于等于 $k$ 的颜色时，直接暴力修改。

对于出现次数大于 $k$ 的颜色，我们只要知道有多少开着的灯与其相邻就可以间接地计算答案。这个值可以用一个数组 $\text{adj}$ 存储，在暴力修改出现次数小于等于 $k$ 的颜色时我们也同时维护这个数组。

但如何在修改出现次数大于 $k$ 的颜色时维护 $\text{adj}$ 呢？注意到这一类颜色最多有 $\dfrac{n}{k}$ 种，我们预处理出所有与当前颜色相邻且出现次数大于 $k$ 的颜色，相应地修改这至多 $\dfrac{n}{k}-1$ 个颜色的 $\text{adj}$ 数组。

总复杂度为 $O\left(nk+\dfrac{n^2}{k}\right)$，在 $k=\sqrt{n}$ 时取最优值 $O(n\sqrt{n})$。

实现

#include <bits/stdc++.h>

const int maxn = 1e5 + 19, maxb = 400;

int a, b;
int n, m, q, B;
int cnt[maxn], tmp[maxn], cor[maxn], deg[maxn][maxb], ind, adj[maxb], dec[maxn];
std::vector<int> pos[maxn];
bool vist[maxn];

int main(){
    std::scanf("%d%d%d", &n, &m, &q), B = std::sqrt(n);
    for(int i = 1; i <= n; ++i){
        std::scanf("%d", cor + i);
        ++cnt[cor[i]];
    }

    for(int i = 1; i <= n; ++i)
        if(cnt[i] > B)
            tmp[i] = ++ind;
    int B_cnt = ind;
    for(int i = 1; i <= n; ++i)
        if(cnt[i] && cnt[i] <= B)
            tmp[i] = ++ind;
    std::fill(cnt + 1, cnt + 1 + n, 0);
    for(int i = 1; i <= n; ++i){
        cor[i] = tmp[cor[i]];
        pos[cor[i]].push_back(i), ++cnt[cor[i]];
        if(cor[i - 1] == cor[i]) ++dec[cor[i]];
    }

    for(int i = 1; i <= n; ++i){
        if(cor[i] != cor[i - 1] && cnt[cor[i - 1]] > B) ++deg[cor[i]][cor[i - 1]];
        if(cor[i] != cor[i + 1] && cnt[cor[i + 1]] > B) ++deg[cor[i]][cor[i + 1]];
    }

    while(q--){
        static int v; std::scanf("%d", &v), v = tmp[v];
        if(!v){
            std::printf("%d\n", a - b);
            continue;
        }
        if(cnt[v] <= B){
            if(!vist[v]){
                assert(cnt[v] == (int)pos[v].size());
                for(int i = 0; i < cnt[v]; ++i){
                    int node = pos[v][i];
                    if(vist[cor[node - 1]] && cor[node - 1] != cor[node])
                        ++b;
                    if(vist[cor[node + 1]] && cor[node + 1] != cor[node])
                        ++b;
                    ++a;
                }
                for(int i = 1; i <= B_cnt; ++i)
                    if(i != v)
                        adj[i] += deg[v][i];
                b += dec[v];
            }
            else{
                assert(cnt[v] == (int)pos[v].size());
                for(int i = 0; i < cnt[v]; ++i){
                    int node = pos[v][i];
                    if(vist[cor[node - 1]] && cor[node - 1] != cor[node])
                        --b;
                    if(vist[cor[node + 1]] && cor[node + 1] != cor[node])
                        --b;
                    --a;
                }
                for(int i = 1; i <= B_cnt; ++i)
                    if(i != v)
                        adj[i] -= deg[v][i];
                b -= dec[v];
            }
            vist[v] ^= 1;
        }
        else{
            if(!vist[v]){
                b += dec[v] + adj[v], a += cnt[v];
                for(int i = 1; i <= B_cnt; ++i)
                    if(i != v)
                        adj[i] += deg[v][i];
            }
            else{
                b -= dec[v] + adj[v], a -= cnt[v];
                for(int i = 1; i <= B_cnt; ++i)
                    if(i != v)
                        adj[i] -= deg[v][i];
            }
            vist[v] ^= 1;
        }
        std::printf("%d\n", a - b);
    }
    return 0;
}

来源

NOI.AC #2007 light

评论