クエリの定義 基本的なテクニック 値の変更なし ver オフラインクエリ rank kth_min オンラインクエリ rank kth_min まとめ 値の変更あり ver X[p] の値を v に変更 rank kth_min その他 値の変更/挿入あり ver クエリの定義 長さ N の整数列 X に対して, 以…

前提 配列（または bitset） Fenwick Tree 平方分割 Trie（動的 Segment Tree） 平衡二分木 おまけ 前提 集合に対して N 個の 追加・削除・k番目に小さい値の取得 のクエリがくるとします. 集合の要素は順序が付けられるものだけ考えます. 要素が非負整数の…

問題文 http://codeforces.com/contest/785/problem/E 問題概要 1, 2, ... , n の列が最初にあって l_i, r_i が Q 個与えられるので毎回 l_i 番目の値と r_i 番目の値をスワップしてから全体の反転数を求めよ AC までの思考過程 Editorial 曰く, 想定解は平…

問題文 https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp18Day3/problems/E 問題概要 日本語なので省略 解法 Euler Tour をとってやると, あとは必要な操作は「区間和」と「区間のブール値反転操作」だけになります.想定解は遅延評価セグメントツ…