提出 #73651307

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>

using namespace std;

// 定义查询结构体，保存左右端点、查询索引
struct Query {
    int l, r, idx;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, Q;
    cin >> N >> Q;
    
    vector<int> P(N + 1);  // 花卉品种，下标从1开始（匹配题目中的花床编号）
    for (int i = 1; i <= N; ++i) {
        cin >> P[i];
    }
    
    // 读取所有查询
    vector<Query> queries(Q);
    for (int i = 0; i < Q; ++i) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].idx = i;
    }
    
    // 分块大小：取√N（经验值，优化常数）
    int block_size = sqrt(N) + 1;
    
    // 排序规则：按左端点所在块排序，同块内右端点奇偶性优化（减少指针移动）
    sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) {
        if (a.l / block_size != b.l / block_size) {
            return a.l / block_size < b.l / block_size;
        }
        // 奇数块右端点升序，偶数块降序（奇偶排序优化）
        return (a.l / block_size % 2) ? (a.r > b.r) : (a.r < b.r);
    });
    
    // 初始化双指针和统计变量
    int cur_l = 1, cur_r = 0;
    int distinct_count = 0;
    vector<int> freq(N + 2, 0);  // 记录每个品种的出现次数（P_i≤N）
    vector<int> ans(Q);          // 保存每个查询的答案
    
    // 处理每个查询
    for (const auto& q : queries) {
        int l = q.l, r = q.r, idx = q.idx;
        
        // 扩展右指针到r
        while (cur_r < r) {
            cur_r++;
            if (freq[P[cur_r]] == 0) {
                distinct_count++;
            }
            freq[P[cur_r]]++;
        }
        
        // 收缩右指针到r
        while (cur_r > r) {
            freq[P[cur_r]]--;
            if (freq[P[cur_r]] == 0) {
                distinct_count--;
            }
            cur_r--;
        }
        
        // 扩展左指针到l
        while (cur_l > l) {
            cur_l--;
            if (freq[P[cur_l]] == 0) {
                distinct_count++;
            }
            freq[P[cur_l]]++;
        }
        
        // 收缩左指针到l
        while (cur_l < l) {
            freq[P[cur_l]]--;
            if (freq[P[cur_l]] == 0) {
                distinct_count--;
            }
            cur_l++;
        }
        
        // 记录当前查询的答案
        ans[idx] = distinct_count;
    }
    
    // 按原始顺序输出答案
    for (int x : ans) {
        cout << x << '\n';
    }
    
    return 0;
}

提出情報

ジャッジ結果