C. Inversion Graph

link

Law 1： Monotonic stack

#include<iostream>
using namespace std;
const int N=2e5+100;
int stk[N],tt,x,top;

int main()
{
    
	int t;
	cin>>t;
	while(t--)
	{
    
		tt=0;
		
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
    
			cin>>x;
			if(tt==0||x>stk[tt]) 
			{
    
				stk[++tt]=x;
			}
			else
			{
    
				int top=stk[tt--];
				while(tt&&stk[tt]>x) tt--;
				stk[++tt]=top;
			}
		}		
		cout<<tt<<endl;
	}	
	return 0;
}

Law 2:

When traversal to $a[i]$, If $max[1,i]<min[i+1,n],ans++$
（ Like a separator , Because the front part and the back part will not be merged ）

#include<iostream>
using namespace std;
const int N=2e5+100;
int a[N],lmax[N],rmin[N];

int main()
{
    
	int t;
	cin>>t;
	while(t--)
	{
    
		int n; cin>>n;
		int maxn=0,minn=0x3f3f3f3f;
		for(int i=1;i<=n;i++) 
		{
    
			cin>>a[i];
			if(a[i]>maxn) maxn=a[i];			
			lmax[i]=maxn;
		}
		
		for(int i=n;i>=1;i--)
		{
    
			rmin[i]=minn;
			if(a[i]<minn) minn=a[i];			
		}
	
		int ans=0;
		for(int i=1;i<=n;i++)
		if(lmax[i]<rmin[i]) ans++;
		cout<<ans<<endl;
	}
	
	return 0;
}