L2461. 「2018 集训队互测 Day 1」完美的队列 题解

题目大意

有 $n$ 个队列，每个队列有一个容量限制 $a_i$。进行 $m$ 次操作，每次操作将值 $x$ 加入到区间 $[l,r]$ 的所有队列中。如果某个队列的大小超过了其容量 $a_i$，则会自动弹出元素直到大小不超过 $a_i$。

需要在每次操作后输出当前所有队列中不同权值的数量。

解题思路

问题分析

这是一个复杂的数据结构问题，需要维护多个队列的操作和查询。直接模拟每次操作的时间复杂度太高，需要寻找更高效的算法。

关键观察

1. 操作的影响：每次操作会影响一个区间内的队列，但每个队列有容量限制，较早的操作可能会被弹出。

2. 权值存活时间：一个权值在队列中存在的时间取决于它被加入的时间和后续操作导致它被弹出的时间。

3. 分块思想：将队列分成若干块，分别处理块内和块间的操作。

算法设计

1. 分块处理

• 将 $n$ 个队列分成 $\sqrt{n}$ 块
• 对于每个操作，如果它完全包含一个块，则进行整体处理；否则处理零散部分

2. 两种计算方式

• 小块操作：操作只影响块的一部分，直接维护每个队列的插入和删除操作
• 大块操作：操作覆盖整个块，使用双指针技巧计算权值的存活时间

3. 核心技巧：双指针扫描

对于每个块，使用双指针 $i, j$ 扫描操作序列：

• $i$ 表示当前考虑的操作
• $j$ 表示使得块中所有队列都不超容量的最早操作
• 通过维护块的容量状态，确定每个权值何时被弹出

4. 权值统计

• 维护每个权值的出现次数
• 当权值出现次数从 0 到 1 时，答案加 1
• 当权值出现次数从 1 到 0 时，答案减 1

时间复杂度

• 分块处理：$O(\sqrt{n})$ 每块
• 双指针扫描：$O(m)$ 每块
• 总复杂度：$O((n+m)\sqrt{n})$，在数据范围内可行

代码实现

#include <bits/stdc++.h>
using namespace std;

constexpr int M = 101000, E = 400;

int n, m, a[M], mxA;
int l[M], r[M], x[M], ans[M];
int L[E], R[E], P[M], B, S, rk[M];
vector<pair<int, bool>> q;
vector<int> p, d, g;
vector<int> ins[M], rmv[M];

int buc[M << 1], val[M], tag, num;

// 处理小块操作
inline void calcSmall(int b, int x) {
    int cnt = p.size();
    
    for (int i = 0, j = 0; i < cnt; i++) {
        // 双指针找到满足容量限制的最大范围
        while (j < cnt && j - i + p[j] - p[i] <= a[x])
            j++;
        
        int e = j - 1 - i + p[j - 1] - p[i], result = INT_MAX;
        
        if (e == a[x])
            result = d[j - 1];
        else if (p[j - 1] + a[x] - e - 1 < int(g.size()))
            result = g[p[j - 1] + a[x] - e - 1];
        
        ans[d[i]] = max(ans[d[i]], result);
    }
}

// 增加队列中的值
inline void _Inc(int x) {
    int p = val[x];
    if (p == tag) num++;
    buc[p]--, buc[p + 1]++, val[x]++;
}

// 减少队列中的值  
inline void _Dec(int x) {
    int p = val[x];
    if (p == tag + 1) num--;
    buc[p]--, buc[p - 1]++, val[x]--;
}

// 增加标签（整体移动）
inline void _IncTag() {
    num -= buc[++tag];
}

// 减少标签（整体移动）
inline void _DecTag() {
    num += buc[tag--];
}

// 处理大块操作
inline void calcBig(int b) {
    // 收集影响当前块的所有操作
    for (int i = 1; i <= m; i++) {
        if (r[i] < L[b] || l[i] > R[b]) continue;
        
        if (l[i] <= L[b] && r[i] >= R[b])
            q.push_back({i, true}), g.push_back(i);  // 完整覆盖块的操作
        else
            rk[i] = g.size(), q.push_back({i, false});  // 部分覆盖的操作
    }

    // 初始化桶和值
    memset(buc, 0, sizeof(buc));
    tag = m, num = R[b] - L[b] + 1;
    
    for (int i = L[b]; i <= R[b]; i++)
        buc[a[i] + m]++, val[i] = a[i] + m;

    // 双指针扫描操作序列
    int cnt = q.size();
    for (int i = 0, j = 0; i < cnt; i++) {
        auto [id, full] = q[i];
        
        if (full) {
            // 完整覆盖操作：减少标签，寻找最早的不超容量位置
            _DecTag();
            while (j <= i || (j < cnt && num)) {
                auto [id, full] = q[j];
                if (full)
                    _IncTag();
                else {
                    // 部分覆盖操作：减少受影响队列的值
                    int _l = max(L[b], l[id]), _r = min(R[b], r[id]);
                    for (int i = _l; i <= _r; i++)
                        _Dec(i);
                }
                j++;
            }
            
            int result = num ? INT_MAX : q[j - 1].first;
            ans[id] = max(ans[id], result);
        } else {
            // 部分覆盖操作：增加受影响队列的值
            int _l = max(L[b], l[id]), _r = min(R[b], r[id]);
            for (int i = _l; i <= _r; i++)
                _Inc(i);
        }
    }

    // 处理小块内的插入删除
    set<int> s;
    for (int i = L[b]; i <= R[b]; i++) {
        for (int j : ins[i]) s.insert(j);
        
        for (int j : s)
            p.push_back(rk[j]), d.push_back(j);
        
        calcSmall(b, i);
        p.clear(), d.clear();
        
        for (int j : rmv[i]) s.erase(j);
    }

    q.clear(), g.clear();
}

int nume[M], answer = 0;
vector<int> del[M];

// 插入小块操作
inline void insertSmall(int id, int l, int r) {
    ins[l].push_back(id), rmv[r].push_back(id);
}

int main() {
    scanf("%d%d", &n, &m);
    S = sqrt(n), B = ceil(1.0 * n / S);
    
    // 读入容量限制
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        mxA = max(mxA, a[i]);
    }
    
    // 分块初始化
    for (int i = 1; i <= B; i++) {
        L[i] = (i - 1) * S + 1;
        R[i] = i == B ? n : i * S;
        for (int j = L[i]; j <= R[i]; j++)
            P[j] = i;
    }
    
    // 读入操作并分类
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", l + i, r + i, x + i);
        int bl = P[l[i]], br = P[r[i]];
        
        if (bl == br)
            insertSmall(i, l[i], r[i]);  // 小块操作
        else {
            // 跨块操作，拆分成小块
            if (l[i] != L[bl])
                insertSmall(i, l[i], R[bl]);
            if (r[i] != R[br])
                insertSmall(i, L[br], r[i]);
        }
    }
    
    // 处理每个块
    for (int i = 1; i <= B; i++)
        calcBig(i);
    
    // 统计答案
    for (int i = 1; i <= m; i++)
        if (ans[i] <= m)
            del[ans[i]].push_back(x[i]);
    
    for (int i = 1; i <= m; i++) {
        if (!nume[x[i]]) answer++;
        nume[x[i]]++;
        
        for (int j : del[i]) {
            if (nume[j] == 1) answer--;
            nume[j]--;
        }
        
        printf("%d\n", answer);
    }
    
    return 0;
}

算法流程详解

1. 初始化分块

• 将队列分成 $\sqrt{n}$ 个块
• 记录每个块的左右边界

2. 操作分类

• 小块操作：操作完全在一个块内
• 跨块操作：拆分成多个小块操作处理

3. 块处理

对于每个块：

• 收集所有影响该块的操作
• 使用双指针确定每个权值的存活时间
• 处理完整覆盖和部分覆盖的情况

4. 答案统计

• 维护每个权值的计数器
• 根据权值的插入和删除时间更新答案

样例分析

对于样例：

n=3, m=3
a=[1,2,3]
操作1: [1,2] 加入1
操作2: [2,3] 加入2  
操作3: [1,3] 加入3

算法会正确计算每个权值的存活时间，最终输出：

1
2
2

总结

本题通过巧妙的分块设计和双指针技巧，高效地解决了多队列操作的问题。主要技巧包括：

1. 分块处理：将问题分解为块内和块间操作
2. 双指针扫描：确定权值的存活时间
3. 延迟统计：批量处理权值的插入和删除

这种结合分块和双指针的思路，在处理区间操作问题时非常有效，值得深入学习掌握。