結果

問題 No.404 部分門松列
コンテスト
ユーザー mayoko_
提出日時 2016-07-26 22:19:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 410 ms / 2,000 ms
コード長 2,932 bytes
コンパイル時間 939 ms
コンパイル使用メモリ 109,544 KB
実行使用メモリ 11,520 KB
最終ジャッジ日時 2024-06-28 17:02:03
合計ジャッジ時間 9,907 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>
#include<random>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

// 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;
}
0