結果
問題 | No.404 部分門松列 |
ユーザー |
|
提出日時 | 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 |
ソースコード
# 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;}