Codeforces Round ＃804 C The Third Problem

https://codeforces.com/contest/1699/problem/C

label

Array operation

The question

Given 0 To n-1 Permutation a.

Definition MEX( a[l -> r] ) Why not a[l -> r] The smallest nonnegative integer that appears in .

If to any 1 <= l <= r <=n, MEX( a[l -> r] ) = MEX( b[l -> r] ) Hang up , said a And b be similar .

Find out how many different permutations there are b And a be similar . The answer is right 1e9 + 7 modulus .

Ideas

Reference resources

First 0 The position cannot be changed , Because of this position mex by 1. Then consider 1 The location of , be in 1 Those numbers in the middle have certain freedom , and 1 It's fixed .

We reached enumeration from childhood to maintain an interval [l,r], If a number is not in the interval , It means that the position of this number cannot be changed , We extend the interval to the position of this number as the boundary . If a number is in an interval , It shows that it can be placed at any free position in the interval . Let's record how many free positions there are in the interval , Each time you encounter such a number, multiply the answer by the number of free positions .

Code

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
#define ll long long

const int N = 1e5+7;
const ll p = 1e9+7;

int f[N],g[N];//g  yes  f  The inverse function of 

signed main(){
    
	cin.tie(0)->sync_with_stdio(0);
	int T;cin>>T;
	while(T--){
    
		int n;cin>>n;
		FOR(i,0,n-1) {
    cin>>f[i];g[f[i]]=i;}
		ll l,r,ans=1;
		l=r=g[0];
		FOR(i,0,n-1){
    
			if(g[i]<l) l=g[i];
			if(r<g[i]) r=g[i];
			if(l<g[i] and g[i]<r) ans=ans*(r-l+1-i)%p;
			cout<<l<<" "<<r<<endl;
		}
		cout<<ans<<endl;
	}
	return 0;
}