时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒 空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M 64bit IO Format: %lld
题目描述
X 爷爷是牛牛国的一个商人,他选择在国内经商。由于牛牛国处于峡谷之中,所以牛牛国的城市排成了一列,这导致了牛牛国的两端相距太远而且交通不十分便利。 X 爷爷只会在某个范围内进行经商,每次经商,他会选择一件物品,并找到他的活动范围内该物品市面价格差最大的两个城市,从低价的城市买并卖到高价的城市。当然,如果他的活动范围内该物品的价格都一样,不存在额差,那么X爷爷就只能 0 利润空手而归了。
牛牛国女皇牛妹调查了 X 爷爷最近次的经商活动,得到了 X 爷爷的每一次经商活动中物品的单件利润以及所经商的物品当时在所有城市的市面价值,他想知道 X 爷爷有多少种满足的活动范围。