When I tried to solve this problem [problem:689D] using a segment tree to retrieve the max or min value in a interval, I got time limit exceeded.<br/>↵
Then I analyze the time cost, it takes n iterations to enumerate each left end of a candidate interval, and in each iteration, as the editorial says, I use binary search to find the boundaries of the right end, rmin and rmax respectively, which takes 2*logn. Then for each probe in binary search, we need to get the max and min value of interval, which takes O(logn) if use a segment tree. In a word, the total time cost is n*2logn*logn = n*(logn*logn*2).<br/>↵
This is the code I got TLE in test 7. [submission:19107380]<br/>↵
I tried to test how much time it takes then I found that it has already takes 1700ms when my program only reach the n/2th iteration. So I have to use a more efficient data structure.<br/>↵
Then I use sparse table, which will take O(nlogn) time to make the table, and only O(1) to a range query. So the total time is n*logn+n = n*(logn+1). When logn >> 1, this is better than segment tree in range query.<br/>↵
This is the code accepted.[submission:19139390]
Then I analyze the time cost, it takes n iterations to enumerate each left end of a candidate interval, and in each iteration, as the editorial says, I use binary search to find the boundaries of the right end, rmin and rmax respectively, which takes 2*logn. Then for each probe in binary search, we need to get the max and min value of interval, which takes O(logn) if use a segment tree. In a word, the total time cost is n*2logn*logn = n*(logn*logn*2).<br/>↵
This is the code I got TLE in test 7. [submission:19107380]<br/>↵
I tried to test how much time it takes then I found that it has already takes 1700ms when my program only reach the n/2th iteration. So I have to use a more efficient data structure.<br/>↵
Then I use sparse table, which will take O(nlogn) time to make the table, and only O(1) to a range query. So the total time is n*logn+n = n*(logn+1). When logn >> 1, this is better than segment tree in range query.<br/>↵
This is the code accepted.[submission:19139390]
