https://beta.atcoder.jp/contests/agc026/tasks/agc026_b BとDの最大公約数が肝になることがわかればほとんど解けたようなもんですが、他の自明な条件も忘れないように。
https://beta.atcoder.jp/contests/agc026/tasks/agc026_c 文字列の前N字について割り当てを決めてしまえば後はDP。
https://codeforces.com/contest/1007/problem/B 雑にやると辛いやつですね。包除しましょう。
https://codeforces.com/contest/1009/problem/F 普通にマージテクするだけと思ったけど制約が厳しすぎる…
https://codeforces.com/contest/1004/problem/B え?ってなるけど…上界をよく考えましょう。
https://codeforces.com/contest/1004/problem/D 端の値で大体決まります。
https://codeforces.com/contest/1004/problem/E 木の葉の方からいらないやつを削除していきます。K=1がコーナーケース。
https://codeforces.com/contest/1004/problem/F えーセグ木すごいですね。一見できなさそうなんですが…結合性さえあればセグ木にできるんだなぁ。実装はテンプレートがあるのでそれを使いましょう。
int N, M, X; struct T { ll v; vector<pi> dpl, dpr; T(ll x = 0) { v = (x >= X); dpl.clear(); dpr.clear(); dpl.pb(pi(0, x)); dpr.pb(pi(0, x)); } friend ostream& operator<<(ostream& out, const T& t) { out << t.v << t.dpl << t.dpr; return out; } }; T operator+(const T& tl, const T& tr) { if(sz(tl.dpl) == 1) return tr; if(sz(tr.dpr) == 1) return tl; T res; res.v = tl.v + tr.v; int at = sz(tl.dpr) - 2; rep(i, 0, sz(tr.dpl) - 1) { while(at > 0 && (tl.dpr[at - 1].sec | tr.dpl[i].sec) >= X) { at--; } if((tl.dpr[at].sec | tr.dpl[i].sec) >= X) { res.v += (tl.dpr.back().fst - tl.dpr[at].fst) * (tr.dpl[i + 1].fst - tr.dpl[i].fst); } } res.dpl = tl.dpl; res.dpl.erase(--res.dpl.end()); int tb = tl.dpl.back().sec; int len = tl.dpl.back().fst; rep(i, 0, sz(tr.dpl) - 1) { if(tb != (tb | tr.dpl[i].sec)) { tb |= tr.dpl[i].sec; res.dpl.pb(pi(tr.dpl[i].fst + len, tb)); } } res.dpl.pb(pi(tr.dpl.back().fst + len, tb)); res.dpr = tr.dpr; res.dpr.erase(--res.dpr.end()); tb = tr.dpr.back().sec; len = tr.dpr.back().fst; rep(i, 0, sz(tl.dpr) - 1) { if(tb != (tb | tl.dpr[i].sec)) { tb |= tl.dpr[i].sec; res.dpr.pb(pi(tl.dpr[i].fst + len, tb)); } } res.dpr.pb(pi(tl.dpr.back().fst + len, tb)); return res; } struct segtree{ int n; vector<T> seg; void init(int mx) { n = 1; while(n < mx) n *= 2; seg = vector<T>(n * 2); } segtree(int mx = 0) { init(mx); } void update(int i, T x) { i += n - 1; seg[i] = x; while(i > 0) { i = (i - 1) / 2; seg[i] = seg[i * 2 + 1] + seg[i * 2 + 2]; } } T ga(int a, int b, int k, int l, int r) { if(b <= l || r <= a) return T(); if(a <= l && r <= b) return seg[k]; else { T lv = ga(a, b, k * 2 + 1, l, (l + r) / 2); T rv = ga(a, b, k * 2 + 2, (l + r) / 2, r); return lv + rv; } } void show() { vector<T> tmp; rep(i, 0, n) tmp.push_back(get(i, i + 1)); debug(tmp); } //edit from here T get(int a, int b) { return ga(a, b, 0, 0, n); } //[a, b) };