#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 5e5;
struct ST {
int n;
vector<int> tree;
vector<int> lazy;
int ans;
ST(int size) {
n = size;
tree.assign(4 * n, 0);
lazy.assign(4 * n, 0);
ans = 0;
}
void push(int node, int start, int end){
if(lazy[node] != 0){
tree[node] = (end - start + 1) * lazy[node];
if(start != end){
lazy[2 * node] = lazy[node];
lazy[2 * node + 1] = lazy[node];
}
lazy[node] = 0;
}
}
void update(int node, int start, int end, int l, int r, int val){
push(node, start, end);
if(start > r || end < l) return;
if(start >= l && end <= r){
lazy[node] = val;
push(node, start, end);
return;
}
int mid = (start + end) / 2;
update(2 * node, start, mid, l, r, val);
update(2 * node + 1, mid + 1, end, l, r, val);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
int query(int node, int start, int end, int l, int r){
push(node, start, end);
if(start > r || end < l) return 0;
if(start >= l && end <= r) return tree[node];
int mid = (start + end) / 2;
int l1 = query(2 * node, start, mid, l, r);
int r1 = query(2 * node + 1, mid + 1, end, l, r);
return l1 + r1;
}
int get(int node, int start, int end, int id){
if(start == end){
return tree[node];
}
else{
int mid = (start + end) / 2;
if(mid >= id){
return get(2 * node, start, mid, id);
}
else{
return get(2 * node + 1, mid + 1, end, id);
}
}
}
};
signed main(){
int n;
cin >> n;
int k = n;
vector<array<int, 3>> T;
int mx = 0;
ST st(maxn);
while(n--){
int u;
cin >> u;
if(u == 2){
int l, r;
cin >> l >> r;
l--, r--;
st.update(1, 0, maxn, l, r, 1);
}
else{
int l, r;
cin >> l >> r;
l--, r--;
cout << st.query(1, 0, maxn, l, r) << endl;
}
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |