題目鏈接

BZOJ

洛谷

解析

3.20 正解是線段樹，但是今天沒時間寫了，先挖個坑qwq，暫時就寫個\(ODT\)

upd 3.21 （沒有咕的）線段樹解法

操作0：區間賦值

操作1：查詢區間和，區間賦值

先查詢區間\([l0, r0]\)的和\(sum\)，得到可用的腦組織數并將\([l0, r0]\)賦\(0\)，然后在\([l1, r1]\)上二分找到位置\(p\)，滿足\([l1, p]\)的中\(0\)的個數等于\(sum\)（如果沒有，說明可用腦組織多了，直接把\(p\)設為\(r1\)就行）然后把\([l1, p]\)賦\(1\)

操作2：查詢最長連續子段

復雜度\(O(n \log^2 n)\)

ODT解法

這個題珂朵莉樹能過……BZOJ上還跑得飛快……

上面是線段樹，下面是珂朵莉樹……

操作0：直接\(assign\)

操作1：查出\([l0, r0]\)中\(1\)的個數，然后\(assign\)，對\([l1, r1]\)暴力跑，找夠了就\(assign\)，但是注意不要經常\(split\)，這里的\(assign\)能用之前的迭代器就不要再\(split\)去找了，不然珂朵莉也救不了你qwq（$TLE$10發的教訓qwq）

操作2：暴力跑一遍區間內節點就好了，要有信仰

另外通過此題發現的\(ODT\)注意事項：每次重新\(split\)了右端點之后一定要再\(split\)左端點一次，不然左邊的迭代器可能被刪除（下面的82行，也就是倒數第6行，好像markdown不顯示行號……），這就是luogu上有篇題解會\(RE\)的原因

代碼

線段樹

#include <iostream> #include <cstdio> #include <cstring> #define MAXN 200005typedef long long LL; struct SegmentTree {struct Node {int maxlen, llen, rlen, cov, sum;} node[MAXN << 2];void build(int, int, int);void push_up(int, int, int);void push_down(int, int, int);void cover(int, int, int, int, int, int);int query1(int, int, int, int, int);int query(int, int, int, int, int);void fix(int, int, int, int);Node & operator [](int x) { return node[x]; } };int N, M; SegmentTree tr;int main() {scanf("%d%d", &N, &M);tr.build(1, 1, N);while (M--) {int tp, l0, r0;scanf("%d%d%d", &tp, &l0, &r0);if (tp == 0) tr.cover(1, 1, N, l0, r0, 0);else if (tp == 1) {int l1, r1; scanf("%d%d", &l1, &r1);tr.fix(l0, r0, l1, r1);} else printf("%d\n", tr.query(1, 1, N, l0, r0));}return 0; } void SegmentTree::push_up(int id, int L, int R) {int ls = id << 1, rs = id << 1 | 1, mid = (L + R) >> 1;if (node[ls].maxlen == mid + 1 - L) node[id].llen = mid + 1 - L + node[rs].llen;else node[id].llen = node[ls].llen;if (node[rs].maxlen == R - mid) node[id].rlen = R - mid + node[ls].rlen;else node[id].rlen = node[rs].rlen;node[id].maxlen = std::max(std::max(node[ls].maxlen, node[rs].maxlen), node[ls].rlen + node[rs].llen);node[id].sum = node[ls].sum + node[rs].sum; } void SegmentTree::push_down(int id, int L, int R) {int ls = id << 1, rs = id << 1 | 1, mid = (L + R) >> 1;if (~node[id].cov) {node[ls].cov = node[rs].cov = node[id].cov;node[ls].sum = node[id].cov * (mid + 1 - L);node[ls].llen = node[ls].rlen = node[ls].maxlen = mid + 1 - L - node[ls].sum;node[rs].sum = node[id].cov * (R - mid);node[rs].llen = node[rs].rlen = node[rs].maxlen = R - mid - node[rs].sum;node[id].cov = -1;} } void SegmentTree::build(int id, int L, int R) {node[id].cov = -1;node[id].llen = node[id].rlen = node[id].maxlen = 0;node[id].sum = R - L + 1;if (L == R) return;int mid = (L + R) >> 1;build(id << 1, L, mid);build(id << 1 | 1, mid + 1, R); } void SegmentTree::cover(int id, int L, int R, int l, int r, int v) {if (L >= l && R <= r) {node[id].cov = v;node[id].sum = v * (R - L + 1);node[id].maxlen = node[id].llen = node[id].rlen = R - L + 1 - node[id].sum;} else {push_down(id, L, R);int mid = (L + R) >> 1;if (l <= mid) cover(id << 1, L, mid, l, r, v);if (r > mid) cover(id << 1 | 1, mid + 1, R, l, r, v);push_up(id, L, R);} } int SegmentTree::query1(int id, int L, int R, int l, int r) {if (L >= l && R <= r) return node[id].sum;push_down(id, L, R);int mid = (L + R) >> 1, res = 0;if (l <= mid) res += query1(id << 1, L, mid, l, r);if (r > mid) res += query1(id << 1 | 1, mid + 1, R, l, r);return res; } int SegmentTree::query(int id, int L, int R, int l, int r) {if (L >= l && R <= r) return node[id].maxlen;push_down(id, L, R);int mid = (L + R) >> 1;if (r <= mid) return query(id << 1, L, mid, l, r);else if (l > mid) return query(id << 1 | 1, mid + 1, R, l, r);else {int res = std::max(query(id << 1, L, mid, l, mid), query(id << 1 | 1, mid + 1, R, mid + 1, r));res = std::max(res, std::min(node[id << 1].rlen, mid - l + 1) + std::min(node[id << 1 | 1].llen, r - mid));return res;} } void SegmentTree::fix(int l0, int r0, int l1, int r1) {int tot = query1(1, 1, N, l0, r0);if (!tot) return;cover(1, 1, N, l0, r0, 0);int l = l1, r = r1;while (l < r) {int mid = (l + r) >> 1;if (mid - l1 + 1 - query1(1, 1, N, l1, mid) < tot) l = mid + 1;else r = mid;}cover(1, 1, N, l1, l, 1); } //Rhein_E

ODT

#include <cstdio> #include <iostream> #include <cstdio> #include <set> #include <algorithm>typedef long long LL; struct ODT_Node {int l, r; char val;ODT_Node (int _l, int _r, char _v):l(_l), r(_r), val(_v) {}ODT_Node (int p = 0):l(p), r(p), val(0) {}bool operator <(const ODT_Node &n) const { return l < n.l; } }; typedef std::set<ODT_Node>::iterator iter; struct ODT {std::set<ODT_Node> data;void init(int n = 0) { data.clear(); data.insert(ODT_Node(1, n, 1)); }iter split(int);void assign(int, int, char);int query(int, int); }; void fix(int, int, int, int);ODT odt; int N, M;int main() {scanf("%d%d", &N, &M);odt.init(N);while (M--) {int tp, l0, r0;scanf("%d%d%d", &tp, &l0, &r0);if (tp == 0) odt.assign(l0, r0, 0);else if (tp == 1) {int l1, r1;scanf("%d%d", &l1, &r1);fix(l0, r0, l1, r1);} else printf("%d\n", odt.query(l0, r0));}return 0; }inline iter ODT::split(int pos) {iter it = data.lower_bound(ODT_Node(pos));if (it->l == pos) return it;--it;int l = it->l, r = it->r; char v = it->val;data.erase(it);data.insert(ODT_Node(l, pos - 1, v));return data.insert(ODT_Node(pos, r, v)).first; } inline void ODT::assign(int l, int r, char v) {iter right = split(r + 1), left = split(l);data.erase(left, right);data.insert(ODT_Node(l, r, v)); } inline int ODT::query(int l, int r) {int res = 0, tmp = 0;iter right = split(r + 1), left = split(l);for (iter i = left; i != right; ++i)if (i->val) res = std::max(res, tmp), tmp = 0;else tmp += i->r - i->l + 1;return std::max(res, tmp); } void fix(int l0, int r0, int l1, int r1) {int tot = 0, blank = 0;iter right = odt.split(r0 + 1), left = odt.split(l0), it;for (it = left; it != right; ++it)if (it->val) tot += it->r - it->l + 1;odt.data.erase(left, right);odt.data.insert(ODT_Node(l0, r0, 0));if (!tot) return;right = odt.split(r1 + 1), left = odt.split(l1);for (it = left; it != right && blank < tot; ++it)if (!it->val) blank += it->r - it->l + 1;if (blank < tot) {odt.data.erase(left, right);odt.data.insert(ODT_Node(l1, r1, 1));} else {int rr = (--it)->r - blank + tot;right = odt.split(rr + 1), left = odt.split(l1);odt.data.erase(left, right);odt.data.insert(ODT_Node(l1, rr, 1));} } //Rhein_E

轉載于:https://www.cnblogs.com/Rhein-E/p/10568079.html

總結

以上是生活随笔為你收集整理的bzoj4592[SHOI2015]脑洞治疗仪的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。