#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef short int si;
typedef vector<si> vsi;
typedef vector<vsi> vvsi;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)
/*
This segment tree stores the
cities in order of decreasing number of attractions
With this setup, we can compute the sum of the x largest elements quickly
Segtree index = kth order statistic (in decreasing array)
*/
class Tree {
public:
ll l, r; // SEGTREE index, NOT Node index
Tree *lt, *rt;
ll v, act;
Tree(ll a_l, ll a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), v(0ll), act(0ll) {};
void combine() {
act = lt->act + rt->act;
v = lt->v * min(1ll, lt->act) + rt->v * min(1ll, rt->act);
}
void build(const vpll& a_ind) {
if(l == r) {
v = a_ind[l].fi;
act = 0ll;
return;
}
ll m = (l + r) >> 1ll;
lt = new Tree(l, m);
rt = new Tree(m + 1ll, r);
lt->build(a_ind);
rt->build(a_ind);
combine();
}
void set_activation(ll i, ll nact) {
if(l == r && r == i) {
act = nact;
return;
}
(i <= ((l + r) >> 1ll) ? lt : rt)->set_activation(i, nact);
combine();
}
// We need to walk on the segment tree instead of doing a binary search
// Binary search is too slow
ll find_kth_active(ll x) {
if(act < x) return -1ll;
if(l == r) return l;
ll m = (l + r) >> 1ll;
if(x <= lt->act) {
return lt->find_kth_active(x);
} else {
return rt->find_kth_active(x - lt->act); // lt is guaranteed to be non-null due to the l == r check
}
}
ll sum_range(ll ql, ll qr) {
if(ql > r || qr < l) return 0ll;
if(ql == l && qr == r) return v;
ll m = (l + r) >> 1ll;
return lt->sum_range(ql, min(qr, m)) + rt->sum_range(max(ql, m + 1ll), qr);
}
ll sum_of_largest(ll x) {
if(x <= 0ll) return 0ll;
ll ind_of_last_active = find_kth_active(x);
if(ind_of_last_active == -1ll) {
ind_of_last_active = r;
// cout << "OOB" << endl;
}
return sum_range(0ll, ind_of_last_active);
}
};
void compute_fr(ll l, ll r, ll vl, ll vr, ll s, ll n, vll& a_inv, vll& fr, vll& maxvr, Tree& tr) {
if(r < l) return;
// Compute value at midpoint
ll m = (l + r) >> 1ll;
ll maxv = 0ll, maxi = vl;
// Line sweep, activate values one by one
L(i, vl, vr + 1ll) {
tr.set_activation(a_inv[i], 1ll);
// Get the sum of the largest elements
// The segment in consideration is [s, i]
// movement cost is i - s, so the total
// number of visitable cities is m - i + s
ll newv = tr.sum_of_largest(m - i + s); // ! TODO rethink
// cout << "Anya likes peanuts, Anya hates carrots " << i << ", a_inv = " << a_inv[i] << " " << m << " " << m - i + s << " " << vr - vl << " " << newv << endl;
if(newv > maxv) {
maxv = newv;
maxi = i;
}
}
// Deactivate values
L(i, vl, vr + 1ll) {
tr.set_activation(a_inv[i], 0ll);
}
// Set fr[m] and maxvr[m] to its new value
fr[m] = maxi;
maxvr[m] = maxv;
// Recurse toward the left (compute all left values)
compute_fr(l, m - 1ll, vl, fr[m], s, n, a_inv, fr, maxvr, tr);
// Activate everything to the left (i.e., from vl to fr[m]) (assume left has been deactivated)
L(i, vl, fr[m]) {
tr.set_activation(a_inv[i], 1ll);
}
// Recurse toward the right (compute all right values)
compute_fr(m + 1ll, r, fr[m], vr, s, n, a_inv, fr, maxvr, tr);
// Deactivate everything in the range vl to vr in NODE INDEX SPACE (not segtree space)
// This is necessary to "reset" the segtree back to its original state for the next iteration
L(i, vl, vr + 1ll) {
tr.set_activation(a_inv[i], 0ll);
}
// Per level, the amount of work done is O(n log n), which should pass
}
void compute_fl(ll l, ll r, ll vl, ll vr, ll s, ll n, vll& a_inv, vll& fl, vll& maxvl, Tree& tr) {
if(r < l) return;
// Compute value at midpoint
ll m = (l + r) >> 1ll;
ll maxv = tr.sum_of_largest(m - 2 * (s - vr)), maxi = vr;
// Line sweep, activate values one by one
LR(i, vr - 1ll, vl - 1ll) {
tr.set_activation(a_inv[i], 1ll);
// Get the sum of the largest elements
// The segment in consideration is [i, s)
// movement cost is 2(s - i), so the total
// number of visitable cities is m - 2(s - i)
ll newv = tr.sum_of_largest(m - 2 * (s - i));
// cout << "Anya likes peanuts, Anya hates carrots " << i << ", a_inv = " << a_inv[i] << " " << m << " " << m - 2 * (s - i) << " " << newv << endl;
if(newv > maxv) {
maxv = newv;
maxi = i;
}
}
// Set fl[m] and maxvl[m] to its new value
fl[m] = maxi;
maxvl[m] = maxv;
// Deactivate values
LR(i, vr - 1ll, vl - 1ll) {
tr.set_activation(a_inv[i], 0ll);
}
// Recurse toward the left (compute all left values)
compute_fl(l, m - 1ll, fl[m], vr, s, n, a_inv, fl, maxvl, tr);
// Activate everything to the right (i.e., flom fl[m] to vr exclusive)
L(i, fl[m], vr) {
tr.set_activation(a_inv[i], 1ll);
}
// Recurse toward the right (compute all right values)
compute_fl(m + 1ll, r, vl, fl[m], s, n, a_inv, fl, maxvl, tr);
// Deactivate everything in the range vl to vr in NODE INDEX SPACE (not segtree space)
// This is necessary to "reset" the segtree back to its original state for the next iteration
L(i, vl, vr) {
tr.set_activation(a_inv[i], 0ll);
}
// Per level, the amount of work done is O(n log n), which should pass
}
ll solve(ll n, ll s, ll d, const vll& a) {
// Create a segment tree, sorted by decreasing values
// Each node should have schema Node { v: ll, i: ll }
// Here, Node.i maps from segtree ind to node ind
// ofc, we also need a node ind to segtree ind converter
// Which is essentially just the inverse permutation
vpll a_ind(n, {0ll, 0ll});
L(i, 0ll, n) {
a_ind[i] = {a[i], i};
}
sort(a_ind.begin(), a_ind.end(), greater<pll>());
Tree tr(0ll, n - 1ll);
tr.build(a_ind);
// a_ind :: tree ind -> [v, node ind]
// a_ind_inv :: node ind -> tree ind
vll a_ind_inv(n, 0ll);
/// Invert the permutation
L(i, 0ll, n) {
a_ind_inv[a_ind[i].se] = i;
}
// First, the goal is to compute the max indices f(d) for each day d
// This could be done using a DnC approach
// I guess also store the maximum value for each corresponding d
vll fr(d + 1ll, -1ll);
vll maxvr(d + 1ll, -1ll);
compute_fr(0ll, d, s, n - 1ll, s, n, a_ind_inv, fr, maxvr, tr);
vll fl(d + 1ll, -1ll);
vll maxvl(d + 1ll, -1ll);
L(i, 0ll, n) tr.set_activation(i, 0ll); // No need for the a_inv stuff, it's just a permutation of [0, n - 1] anyways
compute_fl(0ll, d, 0ll, s, s, n, a_ind_inv, fl, maxvl, tr);
// In the end, we'll have two sequences fL and fR, then we'll compute
// term index d of the max-plus convolution of fL and fR
ll ans = 0ll;
L(i, 0ll, d + 1ll) {
// cout << i << " " << maxvr[i] << " " << maxvl[d - i] << endl;
ans = max(ans, maxvr[i] + maxvl[d - i]);
}
return ans;
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
vll a(n, 0ll);
L(i, 0ll, n) a[i] = attraction[i];
ll ans = 0ll;
ans = max(ans, solve((ll)n, (ll)start, (ll)d, a));
reverse(a.begin(), a.end());
start = n - start - 1ll;
ans = max(ans, solve((ll)n, (ll)start, (ll)d, a));
return ans;
}
