Source Code
#include <bits/stdc++.h>
#define ll long long
#define all(x) x.begin(),x.end()
#define answer(x) cout << (x ? "YES\n" : "NO\n")
#define test ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; cin >> T; while(T--)
#define go ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
using namespace std;


const int N = 200100;
ll n, zero, mex, ans, a[N], vis[N], RightSide[N], seg[4 * N], lazy[4 * N], ind[N], mexOcc[N];



void chk (int p , int s , int e)
{
    if(lazy[p])
    {
        seg[p] += lazy[p];
        if(s!=e)
        {
            lazy[2*p] += lazy[p];
            lazy[2*p+1] += lazy[p];
        }

        lazy[p] = 0;
    }
}
void update(int p , int s , int e, int a , int b , ll v)
{
    chk(p,s,e);

    if(s >= a && e <= b)
    {
        seg[p] += v;

        if(s!=e)
        {
            lazy[2*p] += v;
            lazy[2*p+1] += v;
        }
        return ;
    }

    if(s>b || e<a) return ;
    update(2*p,s,(s+e)/2,a,b,v);
    update(2*p+1,(s+e)/2+1,e,a,b,v);

    seg[p] = seg[2*p] + seg[2*p+1];
}

ll gt(int p , int s , int e , int a , int  b)
{
    chk(p,s,e);
    if(s >= a && e <= b)return seg[p];
    if(s>b || e<a) return 0;
    return gt(2*p,s,(s+e)/2,a,b) + gt(2*p+1,(s+e)/2+1,e,a,b);
}


int main()
{
	test
	{
		cin >> n, mex = 0;
		for(int i=1 ; i<=n ; i++) cin >> a[i], zero = (!a[i] ? i : zero);

		for(int i=zero ; i<=n ; i++)
		{
			vis[a[i]] = 1;
			while(vis[mex]) mex ++;

			mexOcc[mex] = i;
			update(1, 1, n, i, i, mex);
		}

		ans = gt(1, 1, n, zero, n);
	
		for(int i=zero - 1; i>0 ; i--)
		{
			vis[a[i]] = 1;
			
			while(mexOcc[mex] && vis[mex])
			{
				update(1, 1, n, mexOcc[mex], n, 1);  
				mexOcc[mex + 1] = mexOcc[mex];
				mex ++; 
			}	
			
			ans += gt(1, 1, n, zero, n);
		}

		cout << ans << '\n';
		for(int i=0 ; i<=n + 10; i++) vis[i] = RightSide[i] = ind[i] = mexOcc[i] = 0;
		for(int i=0 ; i<=4 * n +2; i++) seg[i] = lazy[i] = 0;
	}
}
Copy
Mex MuhammedAlajam
GNU G++17
24 ms
364 KB
Wrong Answer