Sparse Table Advanced Skills

Store a tuple of (value of maximum, index of maximum, value of the second maximum). To merge two segments, we compare if the indices of the maximums are the same. They can possibly be the same because we often query intersecting segments in the sparse table. If they are, the second maximum is the largest of the respective second maximums. If they aren't, let the first node has a large or equal value of maximum. Then the second maximum is the larger of the second maximum of the first node and the maximum of the second node.

url:https://codeforces.com/blog/entry/120773

st表的高级操作：存储最大值，合并时可能会把重复区间的最大值计算两次，把最大值下标记录，特判即可。

//first 最大值 second 次大值
PII merge(PII A,PII B){
	int L1=A.first,L2=A.second,R1=B.first,R2=B.second;
	PII c={-1,-1};
	if(L2==-1)c.second=R2;
	else if(R2==-1)c.second=L2;
	else if(a[L2].h>a[R2].h)c.second=L2;
	else c.second=R2;
	
	if(L1==R1){
		c.first=L1;
	}
	else{
		if(a[L1].h>a[R1].h){
			c.first=L1;
			if(c.second==-1||a[c.second].h<a[R1].h)
				c.second=R1;
		}
		else{
			c.first=R1;
			if(c.second==-1||a[c.second].h<a[L1].h)
				c.second=L1;
		}
	}
	return c;
}