Submission #76047452

---

Source Code Expand

#include <iostream>
#include <map>
using namespace std;
const int MAX_N = 3e5 + 10;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    // cnt[x]: 第x个细胞的实际块数 = 存储值 + base
    long long cnt[MAX_N] = {0};
    // base: 全局偏移量，用于模拟批量减1操作
    long long base = 0;
    // freq: 存储当前不同块数的细胞数量（使用存储值作为键）
    map<long long, int> freq;
    
    // 初始状态：所有细胞的存储值都是0，共N个
    freq[0] = N;
    
    while (Q--) {
        int type;
        cin >> type;
        
        if (type == 1) {
            int x;
            cin >> x;
            
            // 1. 更新频率哈希表：移除旧值的计数
            long long old_val = cnt[x];
            freq[old_val]--;
            if (freq[old_val] == 0) {
                freq.erase(old_val);
            }
            
            // 2. 增加目标细胞的块数
            cnt[x]++;
            
            // 3. 更新频率哈希表：添加新值的计数
            long long new_val = cnt[x];
            freq[new_val]++;
            
            // 4. 检查是否所有细胞都至少有1个块（实际值 = 存储值 + base >= 1）
            // 最小的实际值 = 最小存储值 + base >= 1
            if (!freq.empty() && freq.begin()->first + base >= 1) {
                // 执行全局减1操作：通过增加base来模拟
                base--;
                
                // 注意：此时所有细胞的实际值都减少了1，相当于存储值都增加了1
                // 但我们不需要修改cnt数组，只需要维护base即可
            }
        } else {
            int y;
            cin >> y;
            
            // 查询实际值 >= y的细胞数量，即存储值 >= y - base的细胞数量
            long long threshold = y - base;
            int ans = 0;
            
            // 使用upper_bound找到第一个大于等于threshold的键
            auto it = freq.lower_bound(threshold);
            while (it != freq.end()) {
                ans += it->second;
                ++it;
            }
            
            cout << ans << '\n';
        }
    }
    
    return 0;
}

Submission Info

Judge Result