[C++知识库]C. Inversion Graph

C. Inversion Graph

链接

法1：单调栈

#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;
}

法2:

当遍历到$a[i]$,如果$max[1,i]<min[i+1,n]，ans++$
（就像是分隔符，因为前面的部分和后面的部分不会有存在合并）

#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;
}