#P4563. [JXOI2018] 守卫

[JXOI2018] 守卫

题目背景

九条可怜是一个热爱运动的女孩子。

题目描述

这一天她去爬山,她的父亲为了她的安全,雇了一些保镖,让他们固定地呆在在山的某些位置,来实时监视九条可怜,从而保护她。

具体来说,一座山可以描述为一条折线,折线的下方是岩石。这条折线有 nn 个折点,每个折点上有一个亭子,第 ii 个折点的坐标是 (i,hi)(i,h_i) 。九条可怜只可能会在亭子处玩耍,那些保镖也只会在亭子处监视可怜。

由于技术方面的原因,一个保镖只能监视所有他能看得到的,横坐标不超过他所在位置的亭子。我们称一个保镖能看到一个亭子 pp ,当且仅当他所在的亭子 qqpp 的连线不经过任何一块岩石。特别地,如果这条连线恰好经过了除了 p,qp,q 以外的亭子,那么我们认为保镖看不到可怜。

雇佣保镖是一件很费钱的事情,可怜的父亲希望保镖越少越好。

可怜的父亲还希望得到详尽的雇佣保镖的方案,他知道有些亭子可能正在维修,他想对所有的 1lrn1\leq l\leq r\leq n 计算:如果事先已知了只有区间 [l,r][l,r] 的亭子可以用来玩耍(和监视),那么最少需要多少个保镖,才能让 [l,r][l,r] 中的每一个亭子都被监视到。

可怜的父亲已经得到了一个结果,他希望和你核实他的结果是否正确。

输入格式

第一行输入一个整数 nn 表示亭子的数目。

接下来一行 nn 个整数,第 ii 个整数 hih_i 表示第 ii 个亭子的坐标是 (i,hi)(i,h_i)

输出格式

对所有的 1lrn1\leq l\leq r\leq n 计算:如果事先已知了可怜只会在 [l,r][l,r] 这个区间的亭子里面玩耍,那么最少需要多少个保镖,才能让 [l,r][l,r] 中的每一个亭子都被监视到。由于输出量太大,可怜的父亲只要你输出所有 [l,r][l,r] 的答案的异或即可。

3
2 3 1
3

提示

样例解释

如果 rl+12r-l+1\leq 2,那么答案显然是 11

如果 l=1l=1r=nr=n,那么答案是 22,需要安排两个保镖在 (2,3),(3,1)(2,3),(3,1) 两个位置监视可怜。

数据范围与提示

对于 30%30\% 的数据,n20n\leq 20
对于 70%70\% 的数据,n500n\leq 500
对于 100%100\% 的数据,n5000n\leq 50001hi1091\leq h_i\leq 10^9