BZOJ 4592 [Shoi2015]脑洞治疗仪

题目链接：​​传送门​​​

Description

曾经发明了自动刷题机的发明家SHTSC又公开了他的新发明：脑洞治疗仪–一种可以治疗他因为发明而日益增大的脑洞的神秘装置。
为了简单起见，我们将大脑视作一个01序列。1代表这个位置的脑组织正常工作，0代表这是一块脑洞。
1 0 1 0 0 0 1 1 1 0
脑洞治疗仪修补某一块脑洞的基本工作原理就是将另一块连续区域挖出，将其中正常工作的脑组织填补在这块脑洞中。（所以脑洞治疗仪是脑洞的治疗仪？）
例如，用上面第8号位置到第10号位置去修补第1号位置到第4号位置的脑洞。我们就会得到：
1 1 1 1 0 0 1 0 0 0
如果再用第1号位置到第4号位置去修补第8号位置到第10号位置：
0 0 0 0 0 0 1 1 1 1
这是因为脑洞治疗仪会把多余出来的脑组织直接扔掉。
如果再用第7号位置到第10号位置去填补第1号位置到第6号位置：
1 1 1 1 0 0 0 0 0 0
这是因为如果新脑洞挖出来的脑组织不够多，脑洞治疗仪仅会尽量填补位置比较靠前的脑洞。
假定初始时SHTSC并没有脑洞，给出一些挖脑洞和脑洞治疗的操作序列，你需要即时回答SHTSC的问题：
在大脑某个区间中最大的连续脑洞区域有多大。

Input

第一行两个整数n，m。表示SHTSC的大脑可分为从1到n编号的n个连续区域。有m个操作。
以下m行每行是下列三种格式之一。
0 l r ：SHTSC挖了一个从l到r的脑洞。
1 l0 r0 l1 r2 ：SHTSC进行了一次脑洞治疗，用从l0到r0的脑组织修补l1到r1的脑洞。
2 l r ：SHTSC询问l到r这段区间最大的脑洞有多大。
n,m <=200000，1<=l<=r<=n

Output

对于每个询问，输出一行一个整数，表示询问区间内最大连续脑洞区域有多大。

Sample Input

10 10
0 2 2
0 4 6
0 10 10
2 1 10
1 8 10 1 4
2 1 10
1 1 4 8 10
2 1 10
1 7 10 1 6
2 1 10

Sample Output

3
3
6
6

暴力艹正解系列

ヽ(￣▽￣)ﾉ

这是对于01序列的区间操作

不要想别的了

珂朵莉就好了

第二种操作具体怎么实现在代码里说

珂朵莉树的空间复杂度是十分优秀的

因为

不需要开数组啊ヾ(๑╹◡╹)ﾉ"

BZOJ：

虽然时间排名没有那么高但是空间大小是很明显的

空间差距太大了

这是最优解第一页（不懂rank1写的啥子）

当然还有洛谷的：

这是开了O2加了读优之后的

开O2会比之前快三四倍

再加上读优还会快500ms左右

可见珂朵莉树在理论情况下有多优秀

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define
#define

using namespace std;
struct node {
  int l, r;
  mutable int v;
  node (int L, int R = -1, int V = 0) : l(L), r(R), v(V) {}
  bool operator < (const node &a) const{
    return l < a.l;
  }
};
set<node> s;
int calc(iter it) {return it->r - it->l + 1;}
iter split(int pos) {
  iter it = s.lower_bound(node(pos));
  if (it != s.end() and it->l == pos) return it;
  it--;
  int lcc = it->l, rcc = it->r, val = it->v;
  s.erase(it);
  s.insert(node(lcc, pos - 1, val));
  return s.insert(node(pos, rcc, val)).first;
}
void assign(int l, int r, int val) {
  iter rcc = split(r + 1), lcc = split(l);
  s.erase(lcc, rcc);
  s.insert(node(l, r, val));
}
int askmax(int l, int r) { //这是区间询问最长的脑洞
  iter rcc = split(r + 1), lcc = split(l);
  int ans = 0, now = 0;
  for (; lcc != rcc; lcc++)
    if (lcc->v == 0)
      now += calc(lcc);
    else ans = max(ans, now), now = 0;
  return max(ans, now);
}
void rec(int l,int r,int sum) {
  iter rcc = split(r + 1), lcc = split(l);
  for(; lcc != rcc; lcc++)
    if (lcc->v == 0) { //有脑洞要补
      if (sum <= calc(lcc)) { //组织用不完了
        if (sum == calc(lcc)) lcc->v = 1; //正好用完
        else {
          int ql = lcc->l, qr = lcc->r; //否则就从头补组织，补不完的就不管了
          s.erase(lcc);
          s.insert(node(ql, ql + sum - 1, 1)); //能补完这些
          s.insert(node(ql + sum, qr, 0)); //这些补不完了
        }
        return;
      }
      else lcc->v = 1, sum -= calc(lcc); //能用完就用
    }
}
void recover(int l, int r, int ll, int rr) {
  iter rcc = split(r + 1), lcc = split(l);
  int ans = 0;
  for(iter it = lcc; it != rcc; it++)
    if (it->v != 0)
      ans += calc(it);
  s.erase(lcc, rcc);
  s.insert(node(l, r, 0));
  if (ans) rec(ll, rr, ans); //这里先计算出要拿的区间有多少组织可以拿
}
int n, m, opt, x, y, xx, yy;
inline char GETCHAR() {
  static char buf[B], *p1 = buf, *p2 = buf;
  return p1 == p2 and (p2 = (p1 = buf) + fread(buf, 1, B, stdin), p1 == p2) ? EOF : *p1++;
}
template<class T> void read(T &x) {
  x = 0; int flag = 0; char ch = GETCHAR();
  while (!isdigit(ch)) flag |= ch == '-', ch = GETCHAR();
  while (isdigit(ch)) x = (x * 10) + (ch ^ 48), ch = GETCHAR();
  x = flag ? -x : x;
}
inline void write(int x) {
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}

int main() {
  read(n); read(m);
  s.insert(node(1, n, 1));
  while (m--) {
    read(opt);
    switch(opt) {
      case 0 : read(x); read(y); assign(x, y, 0); break;
      case 1 : read(x); read(y); read(xx); read(yy); recover(x, y, xx, yy); break;
      case 2 : read(x); read(y); write(askmax(x, y)); puts(""); break;
      default : break;
    }
  }
  return 0;
}