web analytics

JZOJ 4848 永恒的契约 解题报告

Description
宅邸迅速的燃烧着,必须带贝蒂走出禁书库!凭着感觉,又一次直接找到禁书库的门。
“你,是那个人嘛?”400年了,当初圣域建立结界时没有进入圣域,被伤了心的人工精灵贝蒂,与强欲魔女签订契约,守护宅邸的禁书库,直至“那个人”的到来,那个人会解开贝蒂的心结。
“我不是那个什么人,但我会成为你唯一的人。我会给你幸福!”
精灵与人签订契约,从此相依为命。这便是,永恒的契约。

宅邸里,罗兹瓦尔的房间图书柜后,有一条链接宅邸和圣域的秘密通道,其中有一个神奇的大回环,由n块石头组成。
第i块石头有一个高度ai,两块不同的石头i,j能够互相看到,则它们在环上的两条路径中有至少一条路径上除了两个端点(即i,j)路径上石头高度都不大于min(ai,aj)。
被罗兹瓦尔雇佣的猎肠者躲在这秘密的通道中,为了能够更好的观察通道中的情况,她想知道有多少对石头能够互相看到。

Input
第一行一个正整数T,表示数据组数。
接下来T组数据,每组数据第一行读入正整数n,接下来一行按顺时针顺序读入序列a表示石块的高度。

Output
T行表示每组数据的答案。

Sample Input
1
5
1 2 4 5 3

Sample Output
7

Data Constraint
40%,n<=200
60%,n<=2000
70%,n<=100000
80%,n<=1000000,1<=ai<=1000000
100%,n<=1000000,T<=5,1<=ai<=1000000000

分析:

这道题其实很迷。其实就是,这里有一个环。而在这个环上。只要满足两个数中间没有比他们还大的数,我们就可以认为他们两个数是可以看到的。由于这是个环,所以两个数可以在顺时针方向或者是逆时针方向看到。所以这里不是普通的找前驱和后继的问题。
前驱---这个数前面第一个比它大的数。
后继---当前数后面第一个比它大的数。

于是:
我们想另外一种情况,如果这道题是一个链而不是一个环。我们会怎么做呢?
如果只是一条链。首先我们有一个数组 left[] 这里代表,当前数的前驱,所以我们从前往后枚举当前数的时候,如果往前找的时候,首先是往前找也就是left[i-1]。如果当i-1要小于i。那么我们要找到的就是left[i-1]这个数。因为从left[i-1]到i-1期间的数都比i-1小,所以我们要找到的是i-1的前驱,直到找到该数的前驱。
而找到后继呢?也是这样的方式,从后往前找,每次都找到该数的后继。
当然。如果只找前驱和后继,我们会漏掉如果相等的情况。。。如果两数相等他们互相还是会看到。所以我们还要把相等的情况加上。这个处理我们可以加在找后继的时候,sum[]数组表示当前数到它的后继有多少数与该数相同。每次往后找的时候如果找到相同那么就sum[i]=sum[j]+1 这里的sum[j]指找后继的时候找到的数,我们这里不用担心如果找后继的时候 还会发现另一个与该数相等的数,因为后继一定比该数大,所以我们找到的第一个与该数相等的数一定就是 该数到其前驱里最靠近该数的那个相当的数,如果在该区间里还有其他相等的数其计数也就在sum[j]---最靠近原数的那个相等的数的sum里。。。
最后:
我们在统计对数的时候,就是寻找。如果该数有前驱 ans++ 如果该数有后继 ans++ 最后还要记录ans+=sum[i] 将相等的数量也加上。由于前驱与后及满足单调性,所以我们加上前驱与后继,对于下一个数来说是不会重复记录的。是不会记重的!!!就是这样。

所以接下来的问题就变成了,如何将一个环转化成一个链呢?
这个问题其实我们可以想想在这个环里有什么值会对全局性造成影响。
最大值其实会对整个环造成印象,如果我们在一个环里有一个最大值,那么这个最大值将是一个屏障,挡住了所有的数找前驱与后继,那么我们其实就可以从这个最大值开始将整个环拆开,拆成一条链。为了不印象其他的值,我们最好先将这个最大值删去。最后再处理这个最大值对这个链的其他的数的影响的值。

恩。这就结束了。

接下来是代码:

 

Post a Comment

You must be logged in to post a comment.