Submission #1203739

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

apple

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

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

// Index实现

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

	// lazy标记
	int lazy = 0;

	// 左侧节点索引
	int left = -1;

	// 左侧节点索引
	int right = -1;
};

class SumSegmentTree {
private:
	int len;

	// 保存整个线段树
	vector<node> tree;

	// 保存tree当前的idx
	int cidx = 0;

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

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

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

		// 左侧
		// 首先确定，左侧是否存在
		if (tree[cur].left == -1) {
			tree[cur].left = cidx;
			tree.push_back(node());
			cidx++;
		}
		apply(tree[cur].left, mid - at_left + 1, tree[cur].lazy);

		// 右侧
		// 首先确定，右侧是否存在
		if (tree[cur].right == -1) {
			tree[cur].right = cidx;
			tree.push_back(node());
			cidx++;
		}
		apply(tree[cur].right, at_right - mid, tree[cur].lazy);

		// at的lazy重置为0，表示已经pushdown完成
		tree[cur].lazy = 0;
	}

	// 更新操作
	void update(int start, int end, int val, int 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, tree[cur].left, at_left, mid);

		// 右侧
		update(start, end, val, tree[cur].right, mid + 1, at_right);

		// 更新本身
		tree[cur].value = combine(tree[tree[cur].left].value, tree[tree[cur].right].value);
	}

	// 查询操作
	int query(int start, int end, int cur, int at_left, int at_right) {
		// 终止条件
		// 1、完全在[start,end]范围内
		if (start <= at_left && at_right <= end) {
			return tree[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, tree[cur].left, at_left, mid);

		// 计算右边
		int resr = query(start, end, tree[cur].right, mid + 1, at_right);

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

public:
	SumSegmentTree(int len) : len(len) {
		// 开始放入一个node，作为root
		tree.push_back(node());
		cidx++;
	}

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

	// 查询操作
	int query(int start, int end) {
		return query(start, end, 0, 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