Codeforces Round 873 (Div. 2)

ABC都很简单，但是D1写起来有些麻烦，就没写，D2应该是一个分治的思路，后面想不出来了。

D1的思路非常好出，n只有5e3的范围，意味着\((n^2)\)可过，可以直接枚举所有的子区间，也就是题目所说的子数组，然后尝试统计答案。
考虑一个子区间的答案是什么样的，发现只有逆序的数字才需要排序，我们直接找到逆序数字中最小和最大的位置，然后二分找到他们对于这个区间的剩余的位置应该处于哪个位置，这样就能够直接得到这个区间所需的最小的时间。用st表统计最大最小值，总体\(O(n^2logn)\)（其实很危险，而且写起来有点麻烦，就没写）

看完题解了。。D1的\(O(n^2)\)做法就是正解，只需要简简单单的数据结构暴力优化就过了D2。。
难怪D1赛时没几个人过。。这么简单的三题出来了就是rank1000+。
做法不是分治，信息明显无法合并。而是另一个思路，考虑对于每个位置的数字计算答案，也就是这个点会在几次子数组排序中被波及到。那么，我们需要计算的就是对于这个点\(i\)来说，有多少个二元组\((l,r)\)满足选择这个区间后会使得\(i\)的位置处于被排序的区间内。

分析思路好混乱。。难受

其实这段话是最关键的
With these observations, we can conclude that the answer for a subarray a[l..r] equals the r−l minus the number of positions k such that l≤k<r and max(a[l..k])<min(a[k+1..r]) (∗). Let us analyze how to calculate the sum of this value over all possible l and r.

意识到这种位置的含义其实就是无需排序的位置，其实就是这个题目的关键。对于这个区间，我们需要的排序的代价其实就是这个区间的长度减去满足这个条件的位置的数量。
注意到这个，就可以把要求公式化了。看上去没有什么用，但是其实非常关键，

啊啊啊啊啊从头开始，思路全乱了。不应该分两天写的。。。

我看到这题的第一个思路是分治，通过合并两个区间的信息以一个归并的形式来得到答案，但是思考过后就会发现这个思路不可行，左右两边的信息合并非常困难，完全没有规律。
而正解的思路也是很典型，就是对于每一个\(i\in [1,n]\)统计答案，统计对于每个\(i\)，有多少个子区间的选择需要给这个位置的点排序。这个子区间的数量就是这个节点对于答案的贡献。我们把每个点的贡献加起来就是最终的答案。并不是很难想的思路。
然后我们现在需要解决的问题就是怎么统计每个节点的答案。我们考虑什么情况下一个节点会被排序。发现先固定节点不好考虑，尝试固定子区间，即先考虑在子区间固定的情况下，拥有哪些特点的节点会被排序并统计答案。
这个是我认为这题最难的地方。。因为这个的思路不常规吧。。大概吧
需要一些观察（ ？)
观察发现，对于\(k\)个位置，\(l< i_1 <i_2< i_3 ... <i_k <r\)，我们可以分别对区间\(a[l...i_1],a[i_1+1...i_2]...a[i_k+1...r]\)进行排序的条件是，\(max(a[l...i_x])<min(i_x+1...r)\)(\(*\))全部成立。也就是前面一段的最大值一定要小于后面一段的最小值。很容易可以发现这样的话每一段的排序是没有相互影响的。
很明显，这样的分段对于我们答案来说是非常重要的。因为每一个这样的分段就意味着一个位置不产生贡献。这个子数组\(a[l..r]\)所产生的贡献就是就是\(r-l-k\)
然后把这个结论给转化为以点作为主体，对于一个位置\(i\)，我们计算有多少个三元组\((l,k,r)\)，满足\(min(a[k+1..r])==a[i]\)以及\(max(a[l..k])<min(a[k+1...r])\)，这个三元组是对于每一个\(i\)进行计算的，其实就能够很容易发现，这里面的\(k\)就是距离\(i\)左侧最近的且\(a[k]<a[i]\)的点。
我们再对于这个三元组统计一个\(x\),表示\(k\)左侧的第一个满足\(a[x]>a[i]\)的位置，\(y\)，表示\(i\)右侧第一个\(a[y]<a[i]\)的位置。
要是上面的部分全部都理解了的话，这个时候再看一眼我们所需的东西，其实就能够恍然大悟了。我们所需的就是\(x<l\leq k\)，\(i\leq r <y\)的三元组。
所以对于\(i\)这个点的贡献就是为全部的答案减去上\((k-x)*(y-i)\) ，直接枚举\(O(n^2)\)，st表+二分或者倍增优化\(O(n\ log\ n)\)。
这题就没了。

在理解这题前，我是真的感觉这题的答案统计非常的难以想到，但是在我刚刚写的时候我突然发现其实启发点就是对于每个点，答案的统计标准会变的这么简单，而且理解起来非常的合理和顺利，这个应该在开始的时候就能够找到一些端倪的才对。
其实最终要的还是尝试以点为主题的统计答案，一旦想到了这个，其实这个特殊性发现起来就很方便了。当前前提是观察得到了(\(*\))式，而没有后面的思路，我要怎么样才能知道我需要观察得到(\(*\))式呢？正向尝试一下，然后反向尝试一下？而事实上正向的尝试也不一定会得到这个式子，完全可能是其他的式子。
可能是可以直接感觉到对于单点的答案统计不会复杂？然后再向这个方向思考。那么这个又是从哪里感觉到的呢...不过是不是这类题目就这些思路了？不太有其他方向的可能，或者说这个思路是我最后的办法，他只能有用吧。。感觉是这个了，先确定对于单点计算贡献的思路，然后再去尝试分析每个点会做出怎么样的贡献。这样才能够比较顺理成章的得到上面的思路吧。。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
	int a=0,b=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
	for(;c>='0'&&c<='9';c=getchar())a=a*10+c-'0';
	return a*b;
}
int a[300002],n,b[300002];
int l[300002],r[300002];
int sta[300002][2],top;
bool mycmp(int x,int y)
{
	return a[x]>a[y];
}
int main()
{
	int T=read();
	while(T--)
	{
		n=read();
		ll ans=0;
		for(ll i=1;i<=n;i++)
			b[i]=i,a[i]=read(),ans+=i*(i-1)/2;
		sort(b+1,b+1+n,mycmp);
		top=0;
		for(int i=1;i<=n;i++)
			r[i]=n+1,l[i]=0;
		for(int i=1;i<=n;i++)
		{
			while(top!=0&&sta[top][0]>a[i])r[sta[top][1]]=i,top--;
			if(top!=0)l[i]=sta[top][1];
			sta[++top][0]=a[i],sta[top][1]=i;
		}
		set<int> s;
		s.insert(0);
		for(int i=1;i<=n;i++)
		{
			int p=b[i];
			int k=l[p],y=r[p];
			int x;
			if(k==0)x=0;
			else 
			x=*--s.lower_bound(k);
			s.insert(p);
			ans-=1LL*(k-x)*(y-p);
		}
		cout<<ans<<endl;
	}
	return 0;
}

这份代码和上面的代码的思路区别其实有些大，没用用st表求，其实这个求数字左右两边的第一个小/大的数字的位置是经典的单调栈模型，所以直接用单调栈就搞定了，然后另一个需求是另一个数字的左侧的第一个比k大的位置，其实是一个二位偏序，但是因为答案只能是最靠近的一个而不是所有，所以树状数组不太能做，而是用set结合插入的顺序完成。