P2471 [SCOI2007]降雨量

Description

我们常常会说这样的话：“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年，且对于任意Y<Z<X，Z年的降雨量严格小于X年。例如2002，2003，2004和2005年的降雨量分别为4920，5901，2832和3890，则可以说“2005年是自2003年以来最多的”，但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未知，有的说法是可能正确也可以不正确的。

Solution

抱歉在下实在是读不懂题目.

降雨量:

-3951 1990

-3941 2156

查询

-3951 -3941

应该输出啥?

maybe或者是false?????

Code

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

// #define int long long

struct Node {

	int mx, isfull; Node *ls, *rs;

	Node(int _ = 0, int __ = 0, Node *_ls = nullptr, Node *_rs = nullptr) :

		mx(_), isfull(__), ls(_ls), rs(_rs) { }

	void PushUp() {

		mx = std:: max(ls ? ls->mx : 0, rs ? rs->mx : 0);

		isfull = (ls ? ls->isfull : 0) bitand (rs ? rs->isfull : 0);

	}

	void init(int p) {

		mx = p, isfull = true;

	}

	void merge(Node o) {

		mx = std:: max(mx, o.mx), isfull = isfull bitand o.isfull;

	}

};

class Tree {

	int n, lim;

	Node *root;

#define LS l, mid, node->ls

#define RS mid + 1, r, node->rs

	void insert(int l, int r, Node* node, const int& p, const int& k) {

		if (l == r) {

			return node->init(k);

		}

		int mid = ((long long)l + r) >> 1ll;

		if (p <= mid) {

			if (not node->ls) node->ls = new Node();

			insert(LS, p, k);

		}

		if (p >  mid) {

			if (not node->rs) node->rs = new Node();

			insert(RS, p, k);

		}

		node->PushUp();

	}

	Node query(int l, int r, Node* node, const int& L, const int& R) {

		if (l >= L and r <= R) return *node;

		int mid = ((long long)l + r) >> 1ll;

		Node res = Node(0, 1);

		if (L <= mid) res.merge(node->ls ? query(LS, L, R) : Node(0, 0));

		if (R >  mid) res.merge(node->rs ? query(RS, L, R) : Node(0, 0));

		return res;

	}

	int query(int l, int r, Node* node, const int& p) {

		if (l == r) return node->mx;

		int mid = ((long long)l + r) >> 1ll;

		if (p <= mid) return node->ls ? query(LS, p) : -1;

		if (p >  mid) return node->rs ? query(RS, p) : -1;

	}

#undef LS

#undef RS

  public:

	Tree(int _n) : n(_n), root(new Node()), lim(0) {}

	void insert(int p, int k) {

		// printf("insert: %d %d\n", p, k);

		lim = std:: max(lim, p);

		return insert(1, n, root, p, k);

	}

	inline Node query(int l, int r) {

		if (l > r) return false;

		// printf("query: %d %d\n", l, r);

		return query(1, n, root, l, r);

	}

	int solution(int k, int p) {

		int val = query(1, n, root, p);

		// printf("val : %d %d\n", p, val);

		if (val == -1) return -1;

		Node res = query(k + 1, p - 1);

		return val < res.mx ? false : (res.isfull ? true : -1);

	}

};

const int Delta = 1e8 + 1;

void test();

signed main () {

	// test();

	int n;

	scanf("%lld", &n);

	Tree* T = new Tree(1e9 + 1);

	for (int i = 0, y, r; i < n; i += 1) {

		scanf("%lld%lld", &y, &r);

		T->insert(y + Delta, r);

	}

	int m;

	scanf("%lld", &m);

	for (int i = 0, y, r; i < m; i += 1) {

		scanf("%lld%lld", &y, &r);

		int res = T->solution(y + Delta, r + Delta);

		printf("%s\n", ~res ? (res ? "true" : "false") : "maybe");

	}

	return 0;

}

void test() {

	freopen("1.in", "r", stdin);

	freopen("1.out", "w", stdout);

}