// I didnt use templete istg
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Range add, range sum query Dynamic ST
// Based on : https://nyaannyaan.github.io/library/segment-tree/dynamic-segment-tree.hpp
struct DynamicST
{
struct TNode;
using PNode = TNode *;
struct TNode
{
ll val, lazy;
PNode l, r;
TNode() : l(NULL), r(NULL), val(0), lazy(0) {}
};
PNode root;
ll nodecnt;
PNode newnode()
{
return new TNode();
}
void delnode(PNode p)
{
delete p;
}
// DynamicST(ll n = 0)
// {
// nodecnt = 2;
// while (nodecnt <= n)
// nodecnt *= 2;
// root = newnode();
// }
DynamicST()
{
root = newnode();
}
void downtree(PNode v, int tl, int tr)
{
if (v->lazy != -1)
{
if (v->l == NULL)
v->l = newnode();
if (v->r == NULL)
v->r = newnode();
int len = tr - tl + 1;
v->l->val = (len - len / 2) * v->lazy;
v->r->val = (len / 2) * v->lazy;
v->l->lazy = v->r->lazy = v->lazy;
v->lazy = -1;
}
}
void update(PNode v, int tl, int tr, int l, int r)
{
if (l <= tl && tr <= r)
{
v->val = tr - tl + 1;
v->lazy = 1;
}
else if (l <= tr && tl <= r)
{
downtree(v, tl, tr);
int tm = (tl + tr) >> 1;
update(v->l, tl, tm, l, r);
update(v->r, tm + 1, tr, l, r);
v->val = v->l->val + v->r->val;
}
}
ll query(PNode v, int tl, int tr, int l, int r)
{
if (l <= tl && tr <= r)
{
return v->val;
}
else if (l <= tr && tl <= r)
{
downtree(v, tl, tr);
int tm = (tl + tr) >> 1;
ll q1 = query(v->l, tl, tm, l, r);
ll q2 = query(v->r, tm + 1, tr, l, r);
return q1 + q2;
}
return 0;
}
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
// freopen("task.inp", "r", stdin);
// freopen("task.out", "w", stdout);
int q;
cin >> q;
int pre = 0;
DynamicST f;
f.delnode(f.root);
f.root = f.newnode();
while (q--)
{
int type, l, r;
cin >> type >> l >> r;
if (type == 1)
{
ll ans = f.query(f.root, INT_MIN, INT_MAX, l, r);
pre = ans;
cout << ans << '\n';
}
else
{
f.update(f.root, INT_MIN, INT_MAX, l + pre, r + pre);
}
}
}
Compilation message
apple.cpp: In constructor 'DynamicST::TNode::TNode()':
apple.cpp:15:18: warning: 'DynamicST::TNode::r' will be initialized after [-Wreorder]
15 | PNode l, r;
| ^
apple.cpp:14:12: warning: 'll DynamicST::TNode::val' [-Wreorder]
14 | ll val, lazy;
| ^~~
apple.cpp:16:9: warning: when initialized here [-Wreorder]
16 | TNode() : l(NULL), r(NULL), val(0), lazy(0) {}
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
