Dora and Rainbow Bridge

Author : shailesh_2004

Required Knowledge : Combinatorics, Ordered Sets, DSU

Time Complexity : $O(n + q \cdot logn)$

Editorialist : shailesh_2004

Approach:

Firstly, it is obvious that the answer doesn't depend on the array values because all of them are distinct.

For each rule, a new interval is introduced which should be merged with existing intervals because, let's say the values in the indices $[a, b]$ should be increasing and the values in the indices $[c, d]$ should also be increasing and these both intervals are overlapping, then the values in the merged indices $[min(a, c), max(b, d)]$ should also be increasing.

We need to find the non-overlapping merged intervals after each rule appears, let's say there are $3$ non-overlapping intervals of sizes as $3, 4, 5$ and there are $n$ elements.

First, let us try to fill the intervals here as follows:

select $3$ elements from $n$ elements and put them in ascending order in the interval of size $3$

$= {}^nC_3$ ways

then, select $4$ elements from the remaining $(n-3)$ elements and put them in ascending order in the interval of size $4$

$= {}^nC_3 \cdot {}^{n-3}C_4$ ways

then, select $5$ elements from the remaining $(n-7)$ elements and put them in ascending order in the interval of size $5$

$= {}^nC_3 \cdot {}^{n-3}C_4 \cdot {}^{n-7}C_5$ ways

then, we can arrange the remaining $(n-12)$ elements in $(n-12)!$ ways as the order doesn't matter for these remaining elements, thus this results in the following total number of ways:

$= {}^nC_3 \cdot {}^{n-3}C_4 \cdot {}^{n-7}C_5 \cdot (n-12)!$

$= \frac{n!}{3! \cdot (n-3)!} \cdot \frac{(n-3)!}{4! \cdot (n-7)!} \cdot \frac{(n-7)!}{5! \cdot (n-12)!} \cdot (n-12)!$

$= \frac{n!}{3! \cdot 4! \cdot 5!}$

Thus, the total number of valid permutations is $\frac{n!}{\textit{the product of sizes of the non-overlapping intervals}}$

To maintain the merged intervals efficiently, we store all disjoint or non-overlapping intervals in an ordered set sorted by their left endpoints. For each new interval $[x, y]$, we find the first potentially overlapping interval using binary search (lower_bound) and also check the previous interval to avoid missing overlaps. We then iterate over all overlapping intervals, remove them from the set while adding back their factorial contributions, and merge them with $[x, y]$. Finally, we insert the merged interval and divide the answer by the factorial of its size.

Bonus

This problem can also be solved using DSU (Disjoint Set Union). How?

Setter's Code:

// Author : Shailesh
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define pb push_back
#define endl "\n"
#define mod 1000000007
#define tot(a) a.begin(),a.end()
 
// ------------------------------------------------------------------------------------
 
ll binexp(ll a,ll b,ll mod2=mod)
{
    ll res=1;
    a%=mod2;
    while(b)
    {
        if(b%2)res=(res*a)%mod2;
        a=(a*a)%mod2;
        b>>=1;
    }
    return res;
}
 
ll modular_inverse(ll a,ll mod2=mod)
{
    // By Fermat's little theorem
    return binexp(a,mod2-2,mod2);
}
 
ll fact[200001];
void factorial()
{
    fact[0]=1;
    for(ll i=1;i<=200000;i++)fact[i]=(i*fact[i-1])%mod;
}
 
// ------------------------------------------------------------------------------------
 
void solve()
{
    ll n,q;
    cin>>n>>q;
    ll a[n],i;
    for(i=0;i<n;i++)cin>>a[i];
    ll ans=fact[n];
    set<pair<ll,ll>>s; // non-overlapping intervals

    while(q--)
    {
        ll x,y;
        cin>>x>>y;
        ll minl=x,maxr=y;
        auto it=s.lower_bound({x,-1});
        if(it!=s.begin())it--; // cuz while searching for [5, 8], we may miss [2, 9] which is before lower_bound
        if(!s.empty() && it->second<minl)it++; // cuz after doing it--, if we go to [2, 5] but our interval starts at 6, then we don't need it

        while(it!=s.end())
        {
            auto [l,r]=*it;
            if(l>y)break;

            // remove contribution to product
            ans=(ans*(fact[r-l+1]))%mod;
            minl=min(minl,l);
            maxr=max(maxr,r);

            it++;
            // remove the interval [l, r]
            s.erase({l,r});
        }
        
        // insert merged interval
        s.insert({minl,maxr});

        // add new contribution
        ans=(ans*(modular_inverse(fact[maxr-minl+1])))%mod;
        cout<<ans<<endl;
    }
}
 
// ------------------------------------------------------------------------------------
 
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    factorial();
    ll t;cin>>t;while(t--)
    solve();
    return 0;
}

Tester's Code:

//author nagajahnavidann1
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
template<class T>void inp(vector<T>&a){for(auto &x:a)cin>>x;}
const auto start_time = std::chrono::high_resolution_clock::now();
void time_taken(){auto end_time = std::chrono::high_resolution_clock::now();std::chrono::duration<double> diff = end_time-start_time;cerr<<"Time Taken : "<<diff.count()<<"\n";}
ll mod=1e9+7;
ll power(ll a, ll b){ll ans = 1;while(b){if(b & 1ll)ans = (ans*a)%mod;a = (a*a)%mod;b >>= 1ll;}return ans%mod;}
ll MAXSZ=1e6+1;
vector<ll> invfac(MAXSZ),fac(MAXSZ);
//precompute factorials and inverse factorials
void init()
{
    fac[0] = 1;
    for (int i = 1; i < MAXSZ; i++)
        fac[i] = fac[i - 1] * i % mod;
 
    invfac[MAXSZ-1] = power(fac[MAXSZ-1], mod-2);
 
    for (int i = MAXSZ-1; i >= 1; i--)
        invfac[i - 1] = invfac[i] * i % mod;
 
}
void dj()
{ 
    ll n,q;
    cin>>n>>q;
    vector<ll>a(n);//irrelavent to ans
    inp(a);
    map<ll,ll>mp;//stores start and end indices of all the non overlapping intervals that exist at the current query;
    ll cur_val=fac[n],rem_val=n;
    //rem_value: stores no of indices, not bound by any intervals
    //curr_value: ans at present
    while(q--)
    {
        ll l,r,nl,nr;
        cin>>l>>r;
        nl=l,nr=r;
        ll inter_int=0;
        auto it=mp.upper_bound(l);
        //merge any ovrelapping intervals into the new interval
        if(it!=mp.begin()){
            // cout<<"m";
            auto prev=it;
            prev--;
            if(prev->first<=l && prev->second>=l)
            {
                //undo interval
                ll length=prev->second-prev->first+1;
                cur_val=(((cur_val*fac[rem_val])%mod)*((fac[length]*invfac[rem_val+length])%mod))%mod;
                cur_val=((cur_val*fac[rem_val+length])%mod*invfac[rem_val])%mod;
                rem_val+=length;
                
                nl=min(nl,prev->first);
                nr=max(nr,prev->second);
                mp.erase(prev);
            }
        }
            while(it!=mp.end() && it->first<=r && it->second>=l){
                ll length=it->second-it->first+1;
                //undo inteval
                cur_val=(((cur_val*fac[rem_val])%mod)*((fac[length]*invfac[rem_val+length])%mod))%mod;
                cur_val=((cur_val*fac[rem_val+length])%mod*invfac[rem_val])%mod;
                rem_val+=length;
                
                nl=min(nl,it->first);
                nr=max(nr,it->second);
                it=mp.erase(it);
            }
 
            mp[nl]=nr;
            ll flength=nr-nl+1;
            ///add interval
            rem_val-=flength;
            cur_val=((cur_val*fac[rem_val])%mod*invfac[rem_val+flength])%mod;
            cur_val=(((cur_val*fac[rem_val+flength])%mod*invfac[flength])%mod*invfac[rem_val])%mod;
        
        cout<<cur_val<<endl;
    }
 
} 
// ------------------------------------------------------------------------------------
 
signed main(){ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    init();
int t=1;
cin>>t;
while(t--)
dj();
// time_taken();
}