Submission #1203738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203738		hashdfdfh	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	315 ms	137304 KiB

apple

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 1e9 + 5;
const int DEFAULT = 0;

struct node {
	// 节点保存的数值本身
	int value = DEFAULT;

	// lazy标记
	int lazy = 0;

	// 左侧节点
	node* left = nullptr;

	// 右侧节点
	node* right = nullptr;
};

class SumSegmentTree {
private:
	int len;

	// 保存线段树的根
	node* root = new node;

	// 合并两个结果
	int combine(int x, int y) {
		return x + y;
	}

	// 把lazy的结果，应用到at上
	// len代表需要更新的区间大小，add表示整个区间都要加上add
	void apply(node* cur, int len, int add) {
		// 这里只需要处理add是1的情况
		if (add == 1) {
			cur->value = len;
			cur->lazy = add;
		}
	}

	// 把lazy的数值，pushdown到at的children
	void pushdown(node* cur, int at_left, int at_right) {
		// 找到mid
		int mid = (at_left + at_right) / 2;

		// 左侧
		// 首先确定，左侧是否存在
		if (cur->left == nullptr) {
			cur->left = new node;
		}
		apply(cur->left, mid - at_left + 1, cur->lazy);

		// 右侧
		// 首先确定，右侧是否存在
		if (cur->right == nullptr) {
			cur->right = new node;
		}
		apply(cur->right, at_right - mid, cur->lazy);

		// at的lazy重置为0，表示已经pushdown完成
		cur->lazy = 0;
	}

	// 更新操作
	void update(int start, int end, int val, node* cur, int at_left, int at_right) {
		// 终止条件
		// 1、完全在[start,end]范围内
		if (start <= at_left && at_right <= end) {
			apply(cur, at_right - at_left + 1, val);
			return;
		}

		// 2、完全不在[start,end]范围内，不需要更新
		if (at_right < start || end < at_left) {
			return;
		}

		// 先pushdown，再继续
		pushdown(cur, at_left, at_right);

		// 找到mid
		int mid = (at_left + at_right) / 2;

		// 左侧
		update(start, end, val, cur->left, at_left, mid);

		// 右侧
		update(start, end, val, cur->right, mid + 1, at_right);

		// 更新本身
		cur->value = combine(cur->left->value, cur->right->value);
	}

	// 查询操作
	int query(int start, int end, node* cur, int at_left, int at_right) {
		// 终止条件
		// 1、完全在[start,end]范围内
		if (start <= at_left && at_right <= end) {
			return cur->value;
		}

		// 2、完全不在[start,end]范围内
		if (at_right < start || end < at_left) {
			return DEFAULT;
		}

		// 先pushdown，再继续
		pushdown(cur, at_left, at_right);

		int mid = (at_left + at_right) / 2;

		// 计算左边
		int resl = query(start, end, cur->left, at_left, mid);

		// 计算右边
		int resr = query(start, end, cur->right, mid + 1, at_right);

		// 返回总和
		return combine(resl, resr);
	}

public:
	SumSegmentTree(int len) : len(len) {

	}

	// 更新操作
	void update(int start, int end, int val) {
		update(start, end, val, root, 0, len - 1);
	}

	// 查询操作
	int query(int start, int end) {
		return query(start, end, root, 0, len - 1);
	}
};

int main() {
	int m;
	cin >> m;

	SumSegmentTree sst(MAX);

	// 读取m次查询
	int type;
	int a, b, c = 0;
	for (int i = 0; i < m; ++i) {
		cin >> type >> a >> b;
		a--;
		a += c;
		b--;
		b += c;

		// 如果是更新
		if (type == 2) {
			// 传入的是变化量
			sst.update(a, b, 1);
		}
		// 如果是查询
		else {
			c = sst.query(a, b);
			cout << c << endl;
		}
	}
}

• Subtask 1: 100 / 100