购买大楼

线段树 树状数组 序列最大值查询

题目描述

一共有 $n$ 套好渴鹅的楼盘，价值从高到低，因此 $1$ 号大楼是最珍贵的。现在有 $m$ 家公司，一共有 $q$ 次购买交易。这些公司的实力是以升序排列的，这代表这第 $m$ 家公司的实力最为强盛。由于实力不同，因此当厉害的公司购买的大楼价值不如没那么厉害的公司购买的大楼时，他就会想办法把它灭掉。

对于任意一次购买交易，设当前编号为 $i$，那么你需要输入 $a_i$ 和 $p_i$，表示当前这笔交易的公司与需要交易的大楼的编号。由于 $m$ 家公司正在竞争这 $n$ 栋大楼，因此他们需要一些其他公司购买的信息。具体如下：

• 如果这栋大楼已经被买过了，那么这个公司就无法购买这栋大楼。购买失败，输出 can't buy!；
• 否则，按照以下的顺序进行模拟：
  • 首先让这个公司买下这栋大楼；
  • 然后告诉这个公司，比这栋大楼价值要高的大楼，有多少栋被买了；
  • 最后告诉这个公司，比这栋大楼价值要低的大楼，所有购买的公司的编号最大值。

按照题意模拟即可。

输入格式

• 第一行，输入 $n,m,q$，表示的数在题目中已经告诉了；
• 接下来 $q$ 行，第 $i$ 行输入 $a_i,p_i$，表示一笔交易；
• 模拟即可。

输出格式

很简单。

提示说明

普通数据

测试点百分比	$n$	$m$	$q$
$10\%$	$\le 10$	$\le 10$	$\le 100$
另 $20\%$	$\le 100$	$\le 100$	$\le 50$
另 $10\%$	$\le 100$	$\le 100$	$\le 100$
另 $30\%$	$\le 10^5$	$\le 10^5$	$\le 100$
所有的数据	$\le 10^5$	$\le 10^5$	$\le 10^5$

加强数据

$1\le n,q\le 10^7$，$1\le a_i\le m$，$1\le p_i\le n$，$1\le q\le 10^6$