제출 #736783

#제출 시각아이디문제언어결과실행 시간메모리
736783MODDIMonkey and Apple-trees (IZhO12_apple)C++14
0 / 100
0 ms212 KiB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
struct node {
 
    ll one;
    ll lazy;
    struct node *l, *r;
};
 
struct node* getnode()
{
    struct node* temp = new struct node;
    temp->one = 0;
    temp->lazy = 0;
    temp->l = NULL;
    temp->r = NULL;
    return temp;
}
struct node* root;
void update(struct node* cur, ll l, ll r, int L, int R){
	if(cur->lazy != 0){
		cur->one = (r - l + 1);
		if(l != r){
			if(cur->l == NULL)
				cur->l = getnode();
			if(cur->r == NULL)
				cur->r = getnode();
			cur->l->lazy=1;
			cur->r->lazy=1;
		}
		cur->lazy = 0;
	}
	if(r < L || l > R)return;
	if(L <= l && r <= R){
		cur->one = (r - l + 1);
		if(l != r){
			if(cur->l == NULL)
				cur->l = getnode();
			if(cur->r == NULL)
				cur->r = getnode();
			cur->l->lazy=1;
			cur->r->lazy=1;
		}
		return;
	}
	int mid = l + (r - l) / 2;
	if(cur->l == NULL)
		cur->l = getnode();
	if(cur->r == NULL)
		cur->r = getnode();
	update(cur->l, l, mid, L, R);
	update(cur->r, mid+1, r, L, R);
	cur->one = cur->l->one + cur->r->one;
}
ll query(struct node* cur, int l, int r, int L, int R){
	if(cur->lazy != 0){
		cur->one = (r - l + 1);
		if(l !=  r){
			if(cur->l == NULL)
				cur->l = getnode();
			if(cur->r == NULL)
				cur->r = getnode();
			cur->l->lazy=1;
			cur->l->lazy=1;
		}
		cur->lazy = 0;
	}
	if(r < L || l > R)	return 0;
	if(L <= l && r <= R)	return cur->one;
	int mid = l + (r - l) / 2;
	if(cur->l == NULL)
				cur->l = getnode();
			if(cur->r == NULL)
				cur->r = getnode();
	return query(cur->l, l, mid, L, R) + query(cur->r, mid+1, r, L, R);
}
int main(){
	int n;
	cin>>n;
	root = getnode();
	ll c = 0;
	while(n--){
		int t, a, b;
		cin>>t>>a>>b;
		if(t == 2){
			update(root, 0, 1e9, a+c, b+c);
//			assert(false);
		}
		else{
			ll ans = query(root, 0, 1e9, a + c, b + c);
			c = ans;
			cout<<ans<<endl;
		}
	}

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...