#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
const int T = 999'999'999;
struct node
{
ll pL = 0, pR = T, ansR = T, w = 0, posL = 0, sz = 0;
ll pos(ll k)
{
if (k <= pL)
return posL;
else if (k >= pR)
return posL + (pR - pL);
return posL + (k - pL);
}
ll weight(ll k)
{
if (k >= ansR)
return k - ansR + w;
return w;
}
void increase(int t)
{
posL -= t, pL -= t, pR -= t;
if(pL < 0)
posL += -pL, pL = 0;
ansR -= t;
if(ansR < 0)
w += -ansR, ansR = 0;
}
void debug()
{
// printf("[%lld, %lld]: w = %lld -%lld- (+1), pos = %lld\n", pL, pR, w, ansR, posL);
}
};
node merge(node n1, node n2)
{
node res;
n2.increase(n1.sz);
if (n1.pR < n2.pL)
res = node{n2.pL, n2.pL};
else if (n2.pR < n1.pL)
res = node{n2.pR, n2.pR};
else
res = node{max(n1.pL, n2.pL), min(n1.pR, n2.pR)};
if (n2.ansR <= n1.posL + (n1.pR - n1.pL))
{
res.ansR = min(n1.ansR, max(0LL, n2.ansR - n1.posL) + n1.pL);
// assert(n1.pos(n2.ansR - n1.posL + n1.pL) == n2.ansR);
}
else
res.ansR = n1.ansR;
res.w = n1.weight(res.ansR) + n2.weight(n1.pos(res.ansR));
res.posL = n2.pos(n1.pos(res.pL));
res.sz = n1.sz + n2.sz;
return res;
}
int N, Q, pre[300005];
struct segTree
{
node seg[1200006];
// i: [L, R)
void modify(int pos, node n, int i = 1, int L = 0, int R = N)
{
if (R - L == 1)
seg[i] = n;
else
{
int mid = (L + R) / 2;
if (pos < mid)
modify(pos, n, i << 1, L, mid);
else
modify(pos, n, i << 1 | 1, mid, R);
seg[i] = merge(seg[i << 1], seg[i << 1 | 1]);
}
}
node query(int qL, int qR, int i = 1, int L = 0, int R = N)
{
if (qL <= L && R <= qR)
return seg[i];
else if (qR <= L || R <= qL)
return node{};
else
{
int mid = (L + R) / 2;
return merge(query(qL, qR, i << 1, L, mid),
query(qL, qR, i << 1 | 1, mid, R));
}
}
} Rseg, Lseg;
signed main()
{
cin >> N >> Q;
for (int i = 1; i < N; i++)
{
int L, R;
cin >> L >> R;
Rseg.modify(i, node{L, R - 1, R - 1, 0, L, 1});
Lseg.modify(N - i, node{L, R - 1, R - 1, 0, L, 1});
}
for (int i = 1; i <= Q; i++)
{
int T, A, B, C, D;
cin >> T;
if (T == 1)
{
cin >> A >> B >> C;
Rseg.modify(A, node{B, C - 1, C - 1, 0, B, 1});
Lseg.modify(N - A, node{B, C - 1, C - 1, 0, B, 1});
}
else
{
cin >> A >> B >> C >> D;
if (A < C)
{
// Rseg.query(A, C).debug();
// merge(node{B, B, B, 0, B, 0}, Rseg.query(A, C)).debug();
// merge(merge(node{B, B, B, 0, B, 0}, Rseg.query(A, C)), node{D, D, D, 0, D, 0}).debug();
cout << merge(merge(node{B, B, B, 0, B, 0}, Rseg.query(A, C)), node{D, D, D, 0, D, 0}).w << '\n';
}
else if (C < A)
cout << merge(merge(node{B, B, B, 0, B, 0}, Lseg.query(N - A + 1, N - C + 1)), node{D, D, D, 0, D, 0}).w << '\n';
else
cout << max(0, B - D) << '\n';
}
}
}
Compilation message
Compilation timeout while compiling timeleap
