yukicoder No.404 部分門松列

問題

No.404 部分門松列 - yukicoder

解法

とりあえず配列 A は座圧しておきます。

そうすると, 各 A[i] を真ん中とする門松列の数は, 基本的には

• (i より左側にある A[i] より小さい値の数) * (i より右側にある A[i] より小さい値の数)
• (i より左側にある A[i] より大きい値の数) * (i より右側にある A[i] より大きい値の数)

の和になります。ただ, これだと i の左側と右側で同じ値になっている場合を余計に数えているので不十分です。

index が i の時点で左側と右側で同じ数になっているペアの数を same 個, i より左側にある各数字の数をまとめた配列を l, i より右側にある各数字の数をまとめた配列を r とします。

すると, i の左側と右側で同じ値になっているペアの数は, same - l[A[i]] * r[A[i]] となります(上の二つの場合では A[i] が共通の場合は数えてないのでこの分を引く)。

後は l, r, same が各 i ごとに更新できれば良いですが,

• l, r は簡単
• l 側に A[i] が増えるので, r[A[i]] だけ same が増える
• r 側で A[i+1] が減るので, l[A[i+1]] だけ same が減る

となります。

// 0-based Binary Indexed Tree
// 数え上げ用
template<typename T> struct BIT {
    int max;
    vector<T> bit;
    BIT(int max) : max(max) {bit.resize(max+1);}
    // [0, i)
    T sum(int i) {
        T s = 0;
        while (i > 0) {
            (s += bit[i]);
            i ^= i&-i;
        }
        return s;
    }
    // 0-basedな座標iに値xを追加する
    void add(int i, T x) {
        ++i;
        while (i <= max) {
            (bit[i] += x);
            i += i&-i;
        }
    }
    // [a, b)
    T sum(int a, int b) {
        return sum(b)-sum(a);
    }
    // sum(0, i) >= wとなる最小のiを求める 存在しなければmaxを返す
    int lb(T w) {
        if (w <= 0) return 0;
        int k = 1;
        while (k <= max) k <<= 1;
        int i = 0;
        for (; k > 0; k >>= 1) if (i+k <= max && bit[i+k] < w) {
            w -= bit[i+k];
            i += k;
        }
        return i+1;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> A(N), B(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		B[i] = A[i];
	}
	sort(B.begin(), B.end());
	B.erase(unique(B.begin(), B.end()), B.end());
	int n = B.size();
	BIT<ll> b1(n), b2(n);
	vector<ll> l(n), r(n);
	for (int i = 0; i < N; i++) {
		A[i] = lower_bound(B.begin(), B.end(), A[i]) - B.begin();
	}
	for (int i = 0; i < N; i++) {
		r[A[i]]++;
		b2.add(A[i], 1);
	}
	r[A[0]]--;
	ll same = 0;
	vector<ll> calc(n);
	for (int i = 0; i < N; i++) {
		ll ans = 0;
		b2.add(A[i], -1);
		// 両端が A[i] より小さい
		ans += b1.sum(A[i]) * b2.sum(A[i]);
		// 両端が A[i] より大きい
		ans += (i - b1.sum(A[i]+1)) * (N - i - 1 - b2.sum(A[i]+1));
		// 両端で同じ数になる場合
		// どっちも A[i] であることはない
		ans -= same - l[A[i]] * r[A[i]];
		// same, l, r の更新
		if (i+1 < N) {
			r[A[i + 1]]--;
			same += r[A[i]];
			same -= l[A[i + 1]];
			l[A[i]]++;
		}
		b1.add(A[i], 1);
		// sum の更新
		calc[A[i]] += ans;
	}
	vector<ll> sum(n + 1);
	for (int i = 0; i < n; i++) {
		sum[i + 1] = sum[i] + calc[i];
	}
	int Q;
	cin >> Q;
	while (Q--) {
		int L, H;
		cin >> L >> H;
		int low = lower_bound(B.begin(), B.end(), L) - B.begin();
		int high = upper_bound(B.begin(), B.end(), H) - B.begin();
		cout << sum[high] - sum[low] << endl;
	}
	return 0;
}