|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
#define int long long
|
|
|
#define N 1000100
|
|
|
|
|
|
// 柯朵莉树
|
|
|
// O2优化后，也过不去最后的两个测试点TLE
|
|
|
int n, m;
|
|
|
struct Node {
|
|
|
int l, r;
|
|
|
mutable int v;
|
|
|
Node(int L, int R = 0, int V = 0) :
|
|
|
l(L), r(R), v(V) {
|
|
|
}
|
|
|
bool operator<(const Node &t) const {
|
|
|
return l < t.l;
|
|
|
}
|
|
|
};
|
|
|
set<Node> s;
|
|
|
|
|
|
set<Node>::iterator split(int p) {
|
|
|
auto it = s.lower_bound(Node(p));
|
|
|
if (it != s.end() && it->l == p) return it;
|
|
|
it--;
|
|
|
int l = it->l, r = it->r, v = it->v;
|
|
|
s.erase(it);
|
|
|
s.insert(Node(l, p - 1, v));
|
|
|
return s.insert(Node(p, r, v)).first;
|
|
|
}
|
|
|
|
|
|
void assign(int l, int r, int v) {
|
|
|
auto R = split(r + 1), L = split(l);
|
|
|
s.erase(L, R);
|
|
|
s.insert(Node(l, r, v));
|
|
|
}
|
|
|
|
|
|
// 本题逻辑，区间修改[l1,r1]--->[l2,r2]
|
|
|
void change(int l1, int r1, int l2, int r2) {
|
|
|
int res = 0;
|
|
|
auto R = split(r1 + 1), L = split(l1), it = L;
|
|
|
for (; L != R; L++)
|
|
|
if (L->v == 1) res += (L->r - L->l + 1); // 记录正常脑组织的个数
|
|
|
|
|
|
s.erase(it, R); // 删除旧区间
|
|
|
s.insert(Node(l1, r1, 0)); // 旧区间清零
|
|
|
|
|
|
if (!res) return; // 如果这里面没有正常脑组织，那还修什么修
|
|
|
|
|
|
R = split(r2 + 1), L = split(l2), it = L;
|
|
|
|
|
|
// 个人理解属于优化，事实也是如此，但优化后效果是一样的，还是挂了两个测试点TLE
|
|
|
// if (res >= r2 - l2 + 1) { // 如果正常脑组织的个数，超过预修补区间的长度，那么多余的扔掉
|
|
|
// s.erase(L, R);
|
|
|
// s.insert(Node(l2, r2, 1));
|
|
|
// return;
|
|
|
// }
|
|
|
|
|
|
// 小于等于目标区间长度
|
|
|
for (; L != R; L++) {
|
|
|
if (L->v == 0) {
|
|
|
res -= L->r - L->l + 1; // 利用正常的脑组织进行修补
|
|
|
if (res < 0) { // 如果正常脑组织放在这个区间不够
|
|
|
assign(L->l, L->r + res, 1); // 能修多少算多少
|
|
|
break; // 剩余的使没了，不用再往下查看了
|
|
|
} else
|
|
|
L->v = 1; // 暴力修改此区域的值v=1
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int query(int l, int r) {
|
|
|
auto R = split(r + 1), L = split(l);
|
|
|
int res = 0, sum = 0;
|
|
|
for (; L != R; L++) {
|
|
|
if (L->v == 0) // 如果区间值为0,累加计算本轮可以获取到的最长连续0长度，准备参加PK大赛
|
|
|
sum += L->r - L->l + 1;
|
|
|
else
|
|
|
// 如果区间不为0，则以上一轮的最长的、区间内都是0的长度是多少
|
|
|
// 不断进行PK大赛，选举出最长的区间最大的连续脑洞区域
|
|
|
res = max(res, sum), sum = 0;
|
|
|
}
|
|
|
// 这里有技巧！一般我们直接返回res,但是这里不行，因为如果最后一块是连续的0,那么else的代码将无法执行，造成结果错误，需要最后补一下检查
|
|
|
return max(res, sum);
|
|
|
}
|
|
|
|
|
|
signed main() {
|
|
|
// 加快读入
|
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
|
cin >> n >> m;
|
|
|
|
|
|
// 柯朵莉初始化
|
|
|
// 最初是没有脑洞的，全部是正常的大脑，都是1
|
|
|
s.insert(Node(1, n, 1));
|
|
|
|
|
|
while (m--) {
|
|
|
int op, l, r;
|
|
|
cin >> op >> l >> r;
|
|
|
if (op == 0) assign(l, r, 0); //[l,r]之间挖出脑洞
|
|
|
if (op == 1) { // 进行了一次脑洞治疗，从[l1,r1]--->[l2,r2]进行修补
|
|
|
int l2, r2;
|
|
|
cin >> l2 >> r2;
|
|
|
change(l, r, l2, r2);
|
|
|
}
|
|
|
// 询问 [l, r] 区间内最大的脑洞有多大.也就是有多少个0
|
|
|
if (op == 2) cout << query(l, r) << endl;
|
|
|
}
|
|
|
return 0;
|
|
|
} |
