Submission #1199383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199383		hashdfdfh	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	1 ms	320 KiB

apple

#include <iostream>
#include <vector>
using namespace std;
#define int long long

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需要需要更新的数值
	void apply(node* cur, int len, int add) {
		// 如果add是1的话，才需要去操作（也只需要把cur的value和lazy直接改，不用累加）
		if (add == 1) {
			cur->value = len * add;
			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);
	}
};

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);
}

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

	SumSegmentTree sst(MAX);

	// 保存上一轮查询的结果
	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:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         freopen((s + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         freopen((s + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100