#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX = 1e9;
struct node {
node *left, *right;
ll val, lazy;
node() {
val = 0;
lazy = 0;
left = nullptr;
right = nullptr;
}
};
void updateLazy(node* now, ll l, ll r) {
if(now->lazy) {
now->val = r-l+1;
if(l != r) {
if(!(now->left)) {now->left = new node();}
if(!(now->right)) {now->right = new node();}
now->left->lazy = 1;
now->right->lazy = 1;
}
}
}
void update(node* now, ll l, ll r, ll a, ll b) {
// Update Lazy
updateLazy(now, l, r);
if (l > b || r < a) {
return ;
}
if(a <= l && r <= b) {
now->val = (r-l+1);
// Propagate Lazy
if(l != r) {
if(!(now->left)) {now->left = new node();}
if(!(now->right)) {now->right = new node();}
now->left->lazy = 1;
now->right->lazy = 1;
}
return ;
}
if (!(now->left)) {
now->left = new node();
}
if(!(now->right)) {
now->right = new node();
}
ll mid = (l+r)/2;
update(now->left, l, mid, a, b);
update(now->right, mid+1, r, a, b);
now->val = now->left->val + now->right->val;
return ;
}
ll query(node* now, ll l, ll r, ll a, ll b) {
// Update Lazy
if (!now || l > b || r < a) {
return 0;
}
if(a <= l && r <= b) {
return now->val;
}
ll mid = (l+r)/2;
ll out = 0;
if (now->left) {
out += query(now->left, l, mid, a, b);
}
if(now->right) {
out += query(now->right, mid+1, r, a, b);
}
return out;
}
ll q;
node root;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> q;
while(q--) {
ll type, ql, qr;
cin >> type >> ql >> qr;
if (type == 1) {
cout << query(&root, 1, MAX, ql, qr) << "\n";
} else {
update(&root, 1, MAX, ql, qr);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
