結果

問題 No.2901 Logical Sum of Substring
コンテスト
ユーザー hahho
提出日時 2025-02-10 21:42:21
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 242 ms / 3,000 ms
コード長 4,936 bytes
コンパイル時間 3,682 ms
コンパイル使用メモリ 116,704 KB
実行使用メモリ 88,424 KB
最終ジャッジ日時 2025-02-10 21:42:33
合計ジャッジ時間 10,141 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

// ChatGPT o3-mini-highのコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
const int INF = 1e9;
 
// セグメント木の各ノードが保持する情報
struct Node {
    int total;            // 区間全体の論理和
    int best;             // この区間内で条件を満たす最短連続部分列の長さ（存在しなければ INF）
    int len;              // 区間の長さ
    // left: 区間先頭からの連続部分列の累積ORとその長さ（ORが変化したときのみ記録）
    vector<pair<int,int>> left;
    // right: 区間末尾からの連続部分列の累積ORとその長さ（ORが変化したときのみ記録）
    vector<pair<int,int>> right;
};
 
int N, K, Q, target;
vector<int> arr;
vector<Node> segtree;
 
// 2つのノードを結合する
Node combine(const Node &L, const Node &R) {
    Node res;
    res.len = L.len + R.len;
    res.total = L.total | R.total;
    res.best = min(L.best, R.best);
    
    // L の suffix と R の prefix の組み合わせで条件 (OR == target) を満たすかチェック
    for(auto &lp : L.right) {
        for(auto &rp : R.left) {
            int cur = lp.first | rp.first;
            if(cur == target)
                res.best = min(res.best, lp.second + rp.second);
        }
    }
    
    // 左側リストの作成: L.left の情報に R.left を付加
    res.left = L.left;
    int cur = L.total;
    int base_len = L.len;
    for(auto &p : R.left) {
        int newOr = cur | p.first;
        int newLen = base_len + p.second;
        // 直前の値と異なる場合のみ追加
        if(res.left.empty() || res.left.back().first != newOr)
            res.left.push_back({newOr, newLen});
        cur = newOr;
    }
    
    // 右側リストの作成: R.right の情報に L.right の情報を付加
    res.right = R.right;
    int cur_r = R.total;
    int base_len_r = R.len;
    vector<pair<int,int>> right_ext;
    for(auto &p : L.right) {
        int newOr = p.first | cur_r;
        int newLen = p.second + base_len_r;
        if(right_ext.empty() || right_ext.back().first != newOr)
            right_ext.push_back({newOr, newLen});
        cur_r = newOr;
    }
    // 右側リストは R.right と右拡張分を連結
    for(auto &p : right_ext) {
        if(!res.right.empty() && res.right.back().first == p.first)
            res.right.back().second = min(res.right.back().second, p.second);
        else
            res.right.push_back(p);
    }
    
    return res;
}
 
// 1要素からノードを生成
Node make_node(int x) {
    Node node;
    node.len = 1;
    node.total = x;
    node.best = (x == target ? 1 : INF);
    node.left.push_back({x, 1});
    node.right.push_back({x, 1});
    return node;
}
 
// セグメント木の構築 (区間 [l, r] を idx 番目のノードに対応)
void build(int idx, int l, int r) {
    if(l == r) {
        segtree[idx] = make_node(arr[l]);
        return;
    }
    int mid = (l + r) / 2;
    build(idx*2, l, mid);
    build(idx*2+1, mid+1, r);
    segtree[idx] = combine(segtree[idx*2], segtree[idx*2+1]);
}
 
// 点更新: pos 番目の値を val に更新
void update(int idx, int l, int r, int pos, int val) {
    if(l == r) {
        segtree[idx] = make_node(val);
        return;
    }
    int mid = (l + r) / 2;
    if(pos <= mid)
        update(idx*2, l, mid, pos, val);
    else
        update(idx*2+1, mid+1, r, pos, val);
    segtree[idx] = combine(segtree[idx*2], segtree[idx*2+1]);
}
 
// 区間クエリ: [ql, qr] の情報を取得
Node query(int idx, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr)
        return segtree[idx];
    int mid = (l + r) / 2;
    if(qr <= mid)
        return query(idx*2, l, mid, ql, qr);
    else if(ql > mid)
        return query(idx*2+1, mid+1, r, ql, qr);
    else {
        Node leftNode = query(idx*2, l, mid, ql, qr);
        Node rightNode = query(idx*2+1, mid+1, r, ql, qr);
        return combine(leftNode, rightNode);
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 入力形式: 
    // 1行目: N K
    // 2行目: A_1 A_2 ... A_N
    // 3行目: Q
    // 以降 Q 行: 各 query
    cin >> N >> K;
    target = (1 << K) - 1;
    arr.resize(N + 1);
    for (int i = 1; i <= N; i++){
        cin >> arr[i];
    }
    cin >> Q;
    
    segtree.resize(4 * (N + 1));
    build(1, 1, N);
    
    while(Q--){
        int type;
        cin >> type;
        if(type == 1) { // 更新クエリ: 1 i v
            int pos, val;
            cin >> pos >> val;
            update(1, 1, N, pos, val);
        } else if(type == 2) { // 区間クエリ: 2 l r
            int l, r;
            cin >> l >> r;
            Node ans = query(1, 1, N, l, r);
            if(ans.best >= INF)
                cout << -1 << "\n";
            else
                cout << ans.best << "\n";
        }
    }
    return 0;
}
0