#1018945 (C++14) No.404 部分門松列

• 問題: No.404 部分門松列
• ユーザー: Kurl
• 提出日時: 2024-10-13 00:44:04
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 250 ms / 2,000 ms
• コード長: 2,109 bytes
• コンパイル時間: 1,677 ms
• コンパイル使用メモリ: 177,348 KB
• 実行使用メモリ: 23,736 KB
• 最終ジャッジ日時: 2024-10-13 00:44:14
• 合計ジャッジ時間: 8,335 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 4
other	AC * 31

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int N = 200010; 
ll n, cnt, godamn, q;
ll a[N], b[N];
ll lt[N], rt[N];
ll c[N];
vector <ll> G[N];
vector <ll> sum(N), ans(N);
map <ll, ll> id;
ll lowbit(ll x) {return x & (-x);}
void add(ll x, ll ADD)
{
    for (int i = x; i <= n; i += lowbit(i)) c[i] += ADD;
}
ll ask(ll x)
{
    ll res;
    res = 0;
    for (int i = x; i; i -= lowbit(i)) res += c[i];
    return res;
}
ll find(ll x, ll y) {return lower_bound(b, b + y, x) - b;}
int main()
{
    scanf("%lld", &n);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]), b[i] = a[i];
    sort(b, b + n);
    cnt = unique(b, b + n) - b;
    for (int i = 0; i < n; i++) a[i] = find(a[i], cnt);
    for (int i = 0; i < n; i++) G[a[i]].push_back(i);
//  cout << cnt << endl;
//  cout<<"?1\n";
    for (int i = 0; i < cnt; i++)
    {
        for (ll j = 0; j < G[i].size(); j++)
        {
            lt[G[i][j]] = j;
            rt[G[i][j]] = G[i].size() - 1 - j;
//          cout << lt[G[i][j]] << " " << rt[G[i][j]] << endl;
        }
    }
//  cout<<"?2\n";
    for (ll i = 0, ed; i < cnt; i++)
    {
        ed = G[i].size() - 1;
        for (ll j = 0; j <= ed; j++)
        {
            sum[G[i][j] + 1] += ((j + 1) * (ed - j) - j * (ed - j + 1));
//          cout << G[i][j] + 1 << " " << sum[G[i][j] + 1] << endl;
        }
    }
//  cout<<"?3\n";
    for (ll i = 0; i < n; i++)
    {
        sum[i + 1] += sum[i];
        ans[a[i] + 1] -= sum[i];
//      cout << sum[i + 1] << " " << ans[a[i] + 1] << endl;
    }
//  cout<<"?4\n";
    godamn = 0;
    for (ll i = 0; i < cnt; i++)
    {
        for (auto x : G[i])
        {
            ll num, num2, sum, sum2;
            num = ask(x);
            num2 = x - num - lt[x];
            sum = godamn - num;
            sum2 = (n - 1 - x) - sum - rt[x];
            ans[i + 1] += num * sum + num2 * sum2;
//          cout << num << " " << num2 << " " << sum << " " << sum2 << " " << ans[i + 1] << endl;
        }
        for (ll j = 0; j < G[i].size(); j++) ans[i + 1] += (G[i].size() - j) * j;
        godamn += G[i].size();
        for (auto x : G[i]) add(x + 1, 1);
    }
//  cout<<"?5\n";
    for (ll i = 0; i < cnt; i++) ans[i + 1] += ans[i];
    scanf("%lld", &q);
    while (q--)
    {
        ll l, h;
        scanf("%lld%lld", &l, &h);
        printf("%lld\n", ans[find(h + 1, cnt)] - ans[find(l, cnt)]);
    }
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX