Add #2
Description
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef set<int> si;
typedef set<ii> sii;
typedef set<ld> sd;
typedef set<ll> sl;
typedef map<int, int> mii;
typedef priority_queue<int> pqi;
typedef queue<int> qi;
#define mp make_pair
#define pb push_back
#define f first
#define s second
mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
T least_significant_one(T x) {
return (x & (-x));
}
struct fenwick_tree {
int n;
vl freq;
fenwick_tree(int N) : n(N), freq(N + 1, 0) {};
ll sum(int a) {
ll res = 0;
for (; a; a -= least_significant_one(a)) res += freq[a];
return res;
}
void add(int a, int v) {
for (; a <= n; a += least_significant_one(a)) freq[a] += v;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
vi a(n); for (auto &x : a) cin >> x;
// compression
si a_compress; for (auto &x : a) a_compress.insert(x);
mii key, rkey;
int ct = 1;
for (auto &x : a_compress) {
key[x] = ct;
rkey[ct] = x;
ct++;
}
fenwick_tree ct(a_compress.size() + 5), sum(a_compress.size() + 5);
for (int i = 0; i < k - 1; i++) {
ct.add(key[a[i]], 1);
sum.add(key[a[i]], a[i]);
}
}
/*
USE LONG LONG!!!!
:pray: :fishy15:
:pray: :summitosity:
:pray: :prodakcin:
.= , =.
_ _ /'/ )\,/,/(_ \ \
`//-.| ( ,\\)\//\)\/_ ) |
//___\ `\\\/\\/\/\\///' /
,-"~`-._ `"--'_ `"""` _ \`'"~-,_
\ `-. '_`. .'_` \ ,-"~`/
`.__.-'`/ (-\ /-) |-.__,'
|| | \O) /^\ (O/ | . <- BESSIE THE COW
`\\ | / `\ /
\\ \ / `\ /
`\\ `-. /' .---.--.\
`\\/`~(, '() ('
/(O) \\ _,.-.,_)
// \\ `\'` /
/ | || `""""~"`
/' |__||
`o
*/