Submission #1203616

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

apple

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

// Index Implementation

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

// 线段树每个节点的内容
struct node {
	// 保存数值
	int value = DEFAULT;

	// lazy标记
	int lazy = 0;

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

	// 右侧节点
	int right = -1;
};

class SumSegmentTree {
private:
	int len;

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

	// 目前用到那个idx
	int curidx = 0;

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

	// 把lazy的结果，应用到at上
	// len代表需要更新的区间大小，add需要需要更新的数值
	void apply(int cur, int len, int add) {
		// 如果add是1的话，才需要去操作（也只需要把cur的value和lazy直接改，不用累加）
		if (add == 1) {
			tree[cur].value = len * add;
			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 = curidx++;
			tree.push_back(node());
		}
		apply(tree[cur].left, mid - at_left + 1, tree[cur].lazy);

		// 右侧
		// 先确定已经存在右侧
		if (tree[cur].right == -1) {
			tree[cur].right = curidx++;
			tree.push_back(node());
		}
		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, int q) : len(len) {
		// if (q > 0) { tree.reserve(2 * q * ceil(log2(len))); }

		// 放入一个node，作为root
		tree.push_back(node());
		curidx++;
	}

	// 更新操作
	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);
	}
};

void baseIO(string s) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

int main() {
	//baseIO("f");
	int m;
	cin >> m;

	SumSegmentTree sst(MAX, m);

	// 保存上一轮查询的结果
	int pre = 0;

	// 读取m次查询
	int d, x, y;
	for (int i = 0; i < m; ++i) {
		cin >> d >> x >> y;
		// 索引从1开始
		x--;
		x += pre;
		y--;
		y += pre;

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

Compilation message (stderr)

apple.cpp: In function 'void baseIO(std::string)':
apple.cpp:157:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         freopen((s + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         freopen((s + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100