Source Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

#define forr(_a, _b, _c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a, _b, _c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a, _b, _c) for(_a = (_b); _a < (_c); ++_a)
#define mp make_pair
#define fi first
#define se second
#define vi vector
#define sz(_v) _v.begin(), _v.end()
#define mask(_x) (1ll << (_x))
#define bit(_x,_y) (((_x) >> (_y)) & 1)

string yes[2] = {"NO\n","YES\n"};
const ld eps = ld(1e-7);
const ll inf = ll(1e16) + 1;
const ll mod = ll(1e9) + 7;

const int N = 2e5 + 5;
int n, i, a[N], pos[N], rmq[N][21], j, L, R, l, r, m;
ll o, x, y;

int get(int x, int y) {
	int z = __lg(y - x + 1);
	return min(rmq[x][z],rmq[y - mask(z) + 1][z]);
}

void solve() {
	cin >> n;
	forr(i,1,n) {
		cin >> a[i];
		pos[a[i]] = i;
		rmq[i][0] = a[i];
	}
	forr(j,1,20) forr(i,1,n - mask(j) + 1) {
		rmq[i][j] = min(rmq[i][j - 1],rmq[i + mask(j - 1)][j - 1]);
	}
	L = R = pos[0];
	o = 0;
	forr(i,1,n) {
		if(L <= pos[i] && pos[i] <= R) continue;
		l = 1;
		r = L - 1;
		while(l <= r) {
			m = (l + r) >> 1;
			if(get(m,L - 1) > i) r = m - 1;
			else l = m + 1;
		}
		x = L - l + 1;
		l = R + 1;
		r = n;
		while(l <= r) {
			m = (l + r) >> 1;
			if(get(R + 1,m) > i) l = m + 1;
			else r = m - 1;
		}
		y = r - R + 1;
		o += x * y * i;
		L = min(L,pos[i]);
		R = max(R,pos[i]);
	}
	cout << o << "\n";
}

void precalc() {
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	#ifdef umf
		freopen("test.inp","r",stdin);
		freopen("test.out","w",stdout);
	#endif

	int tc = 1;
	cin >> tc;
	precalc();
	while(tc --> 0) {
		solve();
	}

	return 0;
}
Copy
Mex thqdothabit
GNU G++17
12 ms
432 KB
Wrong Answer