結果
問題 |
No.2901 Logical Sum of Substring
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
// 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; }