20 September 2018: Prefix-Sum Arrays and Fenwick Trees

From UMCPC Wiki
Revision as of 12:08, 20 September 2018 by Mkarutz (talk | contribs) (Added workshop problems and solutions.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Reverse Pairs

def LSB(i):
    return i & -i

class BIT:
    def __init__(self, n):
        self.n = n+1
        self.A = [0 for _ in range(n+1)]

    def get(self, i):
        ans = 0
        while i > 0:
            ans += self.A[i]
            i -= LSB(i)
        return ans
    
    def add(self, i, k):
        while i < self.n:
            self.A[i] += k
            i += LSB(i)

class Solution:
    def reversePairs(self, nums):
        V = sorted(list(set(nums + [2*n for n in nums])))
        R = {v:i+1 for i, v in enumerate(V)}
        
        bit = BIT(len(R))
        
        ans = 0
        for i, n in enumerate(nums):
            ans += i - bit.get(R[2*n])
            bit.add(R[n], 1)
        
        return ans

816B: Karen and Coffee

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, k, q;
    vector<int> A(200001, 0);

    scanf("%d%d%d", &n, &k, &q);

    for (int i = 0; i < n; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        A[l]++;
        A[r+1]--;
    }

    for (int i = 1; i <= 200000; i++) {
        A[i] += A[i-1];
    }
    for (int i = 1; i <= 200000; i++) {
        A[i] = (A[i] >= k);
    }
    for (int i = 1; i <= 200000; i++) {
        A[i] += A[i-1];
    }

    for (int i = 0; i < q; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", A[b] - A[a-1]);
    }
}

1042D: Petya and Array

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define LSB(i) ((i) & -(i))

class BIT {
  private:
    int N;
    vector<ull> F;

  public:
    BIT(int n) : N(n+1), F(N, 0) {}

    ull get(int i) {
        ull sum = 0;
        for (; i > 0; i -= LSB(i)) {
            sum += F[i];
        }
        return sum;
    }

    void add(int i, ull k) {
        for (; i < N; i += LSB(i)) {
            F[i] += k;
        }
    }
};

int main() {
    int n;
    ll t;

    scanf("%d%lld", &n, &t);

    vector<ll> S;
    for (ll sum = 0, i = 0; i < n; i++) {
        ll a;
        scanf("%lld", &a);
        sum += a;
        S.push_back(sum);
    }

    set<ll, greater<ll>> V = { 0 };
    for (auto sum : S) {
        V.insert(sum);
        V.insert(sum - t + 1);
    }

    unordered_map<ll, int> CC;
    for (auto v : V) {
        int idx = CC.size();
        CC[v] = idx;
    }

    BIT bit(V.size());
    bit.add(CC[0] + 1, 1);

    ull ans = 0;
    for (int i = 0; i < n; i++) {
        ans += bit.get(CC[S[i] - t + 1] + 1);
        bit.add(CC[S[i]] + 1, 1);
    }

    printf("%llu\n", ans);
}