백준11591 VUDU

작성일 | In

문제 링크

  • http://icpc.me/11591

문제 출처

  • 2015/2016 COCI #2 5번

사용 알고리즘

  • 세그먼트 트리

시간복잡도

  • $O(N \log N)$

풀이

구간 $[l, r]$의 평균이 $P$ 이상이 되는 경우의 수를 구하는 문제입니다.

$\frac{S_r - S_{l-1}}{r-l+1} \geq P$는 $S_r - S_{l-1} \geq Pr - P(l-1)$로 바꿀 수 있고, 다시 $S_r - Pr \geq S_{l-1} - P(l-1)$로 바꿀 수 있습니다.
Inversion Counting 하듯이 구하면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
using namespace std;

typedef long long ll;

ll tree[1010101];
void update(int x){ for(x++; x<1010101; x+=x&-x) tree[x]++; }
ll query(int x){ ll ret = 0; for(x++; x; x-=x&-x) ret += tree[x]; return ret; }
ll query(int l, int r){ return query(r) - query(l-1); }

ll n, a[1010101], k, ans;
vector<ll> comp;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n; for(int i=1; i<=n; i++) cin >> a[i], a[i] += a[i-1];
    cin >> k; for(int i=0; i<=n; i++) a[i] -= k*i, comp.push_back(a[i]);
    compress(comp); for(int i=0; i<=n; i++) a[i] = IDX(comp, a[i]) + 1;
    for(int i=0; i<=n; i++) ans += query(1, a[i]), update(a[i]);
    cout << ans;
}