// weirdtree_100_sqrt_ruxandra.cpp
#include <bits/stdc++.h>
#include "weirdtree.h"
#define DIMN 300010
using namespace std;
struct bucketinfo{
long long sum;
int maxi1, cntmaxi1, maxi2, lazy;
/// lazy este cea mai mare valoare care poate sa apara ever in subarb
} bucket[600];
int v[DIMN], n , bucksize;
int whichBucket(int i){
return (i - 1) / bucksize + 1;
}
int startOfBuck (int i){
return (i - 1) * bucksize + 1;
}
int endOfBuck (int i){
return startOfBuck(i) + bucksize - 1;
}
bucketinfo query (int l , int r){
int start, stop, i, val;
bucketinfo sol = {0 , 0 , 0 , 0 , 0};
if (whichBucket(l) == whichBucket(r)){
for (i = l ; i <= r ; i++){
sol.sum += min(v[i] , bucket[whichBucket(l)].maxi1);
val = min(v[i] , bucket[whichBucket(l)].maxi1);
if (sol.maxi1 < val){
sol.maxi2 = sol.maxi1;
sol.maxi1 = val;
sol.cntmaxi1 = 1;
}
else if (sol.maxi1 == val){
sol.cntmaxi1++;
}
else if (sol.maxi2 < val){
sol.maxi2 = val;
}
}
return sol;
}
start = (whichBucket(l) != whichBucket(l - 1) || l == 1 ? whichBucket(l) : whichBucket(l) + 1);
stop = (whichBucket(r) != whichBucket(r + 1) || r == n ? whichBucket(r) : whichBucket(r) - 1);
//printf ("%d %d %d\n", whichBucket(l), whichBucket(r), bucksize);
for (i = start ; i <= stop ; i++){
//printf ("%d %d %d %lld\n", i , startOfBuck(i), endOfBuck(i), bucket[i].sum);
sol.sum += bucket[i].sum;
if (sol.maxi1 < bucket[i].maxi1){
sol.maxi2 = sol.maxi1;
sol.maxi1 = bucket[i].maxi1;
sol.cntmaxi1 = bucket[i].cntmaxi1;
}
else if (sol.maxi1 == bucket[i].maxi1){
sol.cntmaxi1 += bucket[i].cntmaxi1;
}
if (sol.maxi2 < bucket[i].maxi2){
sol.maxi2 = bucket[i].maxi2;
}
if (sol.maxi2 < bucket[i].maxi1 && sol.maxi1 > bucket[i].maxi1){
sol.maxi2 = bucket[i].maxi1;
}
}
if (start != whichBucket(l)){
for (i = l ; whichBucket(i) != start; i++){
sol.sum += min(v[i] , bucket[whichBucket(l)].maxi1);
val = min(v[i] , bucket[whichBucket(l)].maxi1);
if (sol.maxi1 < val){
sol.maxi2 = sol.maxi1;
sol.maxi1 = val;
sol.cntmaxi1 = 1;
}
else if (sol.maxi1 == val){
sol.cntmaxi1++;
}
else if (sol.maxi2 < val){
sol.maxi2 = val;
}
}
}
if (stop != whichBucket(r)){
for (i = r ; whichBucket(i) != stop ; i--){
sol.sum += min(v[i] , bucket[whichBucket(r)].maxi1);
val = min(v[i] , bucket[whichBucket(r)].maxi1);
if (sol.maxi1 < val){
sol.maxi2 = sol.maxi1;
sol.maxi1 = val;
sol.cntmaxi1 = 1;
}
else if (sol.maxi1 == val){
sol.cntmaxi1++;
}
else if (sol.maxi2 < val){
sol.maxi2 = val;
}
}
}
return sol;
}
void updatemanually (int i , int &capacity, int maxi, int l , int r){
long long sum;
int maxi1, maxi2, cntmaxi1, val;
sum = 0;
maxi1 = 0;
maxi2 = 0;
cntmaxi1 = 0;
for (int j = startOfBuck(i) ; j <= endOfBuck(i) ; j++){
val = min(v[j], bucket[i].maxi1);
if (l <= j && j <= r && val > maxi - (capacity > 0)){
val = maxi - (capacity > 0);
if (capacity)
capacity--;
}
v[j] = val;
sum += val;
if (val > maxi1){
maxi2 = maxi1;
maxi1 = val;
cntmaxi1 = 1;
}
else if (val == maxi1){
cntmaxi1++;
}
else if (val > maxi2){
maxi2 = val;
}
}
bucket[i].sum = sum;
bucket[i].maxi1 = maxi1;
bucket[i].cntmaxi1 = cntmaxi1;
bucket[i].maxi2 = maxi2;
bucket[i].lazy = maxi1;
}
void goOverAndReplace (int l , int r , int capacity, int maxi){
int i , start , stop;
start = (whichBucket(l) != whichBucket(l - 1) || l == 1 ? whichBucket(l) : whichBucket(l) + 1);
stop = (whichBucket(r) != whichBucket(r + 1) || r == n ? whichBucket(r) : whichBucket(r) - 1);
if (whichBucket(l) == whichBucket(r)){
updatemanually(whichBucket(l), capacity, maxi, l , r);
return;
}
if (start != whichBucket(l) && bucket[whichBucket(l)].maxi1 > maxi - (capacity > 0)){
updatemanually(whichBucket(l), capacity, maxi, l , r);
}
for (i = start ; i <= stop ; i++){
if (bucket[i].maxi1 > maxi - (capacity > 0)){ /// there is something to change
if ((bucket[i].maxi2 < maxi - (capacity > 0) || bucket[i].cntmaxi1 == endOfBuck(i) - startOfBuck(i) + 1)
&& (capacity == 0 || capacity > bucket[i].cntmaxi1)){ /// just replace
bucket[i].sum = bucket[i].sum - 1LL * bucket[i].maxi1 * bucket[i].cntmaxi1
+ 1LL * ( maxi - (capacity > 0) ) * bucket[i].cntmaxi1;
bucket[i].maxi1 = maxi - (capacity > 0);
bucket[i].lazy = maxi - (capacity > 0);
if (capacity)
capacity -= bucket[i].cntmaxi1;
}
else { /// cannot be sure, update manually
updatemanually(i , capacity, maxi, l , r);
}
}
}
if (stop != whichBucket(r) && bucket[whichBucket(r)].maxi1 > maxi - (capacity > 0)){
updatemanually(whichBucket(r), capacity, maxi, l , r);
}
}
void initialise (int N , int q , int h[]){
int i, maxi1, maxi2, cntmaxi1;
long long sum;
n = N;
for (i = 1 ; i <= n ; i++){
v[i] = h[i];
}
bucksize = sqrt(n);
sum = 0;
maxi1 = 0;
maxi2 = 0;
cntmaxi1 = 0;
for (i = 1 ; i <= n ; i++){
sum += v[i];
if (v[i] > maxi1){
maxi2 = maxi1;
maxi1 = v[i];
cntmaxi1 = 1;
}
else if (v[i] == maxi1){
cntmaxi1++;
}
else if (v[i] > maxi2){
maxi2 = v[i];
}
if (whichBucket(i) != whichBucket(i + 1) || i == n){
bucket[whichBucket(i)].sum = sum;
bucket[whichBucket(i)].maxi1 = maxi1;
bucket[whichBucket(i)].cntmaxi1 = cntmaxi1;
bucket[whichBucket(i)].maxi2 = maxi2;
bucket[whichBucket(i)].lazy = maxi1;
sum = maxi1 = maxi2 = cntmaxi1 = 0;
}
}
}
void cut (int l, int r, int k){
long long cuts;
int capacity;
bucketinfo ans;
while (k){
ans = query(l , r);
if (ans.maxi1 == 0){
/// not much you can do
return;
}
cuts = 1LL * (ans.maxi1 - ans.maxi2) * ans.cntmaxi1;
if (cuts <= k){
/// all values equal to maxi1 become equal to maxi2 in [l , r]
k -= cuts;
capacity = 0;
goOverAndReplace(l , r, 0, ans.maxi2);
}
else {
/// too many values bigger than maxi2, do stuff
int valueToReach = ans.maxi1 - k / ans.cntmaxi1;
capacity = k % ans.cntmaxi1;
goOverAndReplace(l , r , capacity, valueToReach);
k = 0;
}
}
}
void magic (int poz, int k){
int i, maxi1, maxi2, cntmaxi1, start , stop, val;
long long sum;
start = startOfBuck(whichBucket(poz));
stop = endOfBuck(whichBucket(poz));
sum = 0;
maxi1 = 0;
maxi2 = 0;
cntmaxi1 = 0;
for (i = start ; i <= stop ; i++){
if (i == poz){
val = k;
}
else {
val = min(v[i], bucket[whichBucket(poz)].maxi1);
}
v[i] = val;
sum += val;
if (val > maxi1){
maxi2 = maxi1;
maxi1 = val;
cntmaxi1 = 1;
}
else if (val == maxi1){
cntmaxi1++;
}
else if (val > maxi2){
maxi2 = val;
}
}
bucket[whichBucket(poz)].sum = sum;
bucket[whichBucket(poz)].maxi1 = maxi1;
bucket[whichBucket(poz)].cntmaxi1 = cntmaxi1;
bucket[whichBucket(poz)].maxi2 = maxi2;
bucket[whichBucket(poz)].lazy = maxi1;
}
long long inspect (int l, int r){
return query(l , r).sum;
}
