#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 300100, maxblock = sqrt(maxn) + 10, inf = 1e9 + 10;
ll n, q, h[maxn], block;
ll lazy[maxblock], sum[maxblock];
ll mx1[maxblock], fr[maxblock], mx2[maxblock];
void initialise(int N, int Q, int H[])
{
n = N;
q = Q;
block = max((ll)sqrt(n), (ll)(1));
for (int i = 1; i <= n; i ++)
{
h[i] = H[i];
lazy[i / block] = inf;
sum[i / block] += h[i];
if (h[i] > mx1[i / block])
{
mx2[i / block] = mx1[i / block];
mx1[i / block] = h[i];
fr[i / block] = 0;
}
if (h[i] == mx1[i / block])
{
fr[i / block] ++;
}
else if (h[i] > mx2[i / block])
{
mx2[i / block] = h[i];
}
}
}
void update_block(int bl)
{
mx1[bl] = mx2[bl] = 0;
fr[bl] = 0;
sum[bl] = 0;
for (int i = bl * block; i < (bl + 1) * block; i ++)
{
h[i] = min(h[i], lazy[bl]);
sum[bl] += h[i];
if (h[i] > mx1[bl])
{
mx2[bl] = mx1[bl];
mx1[bl] = h[i];
fr[bl] = 0;
}
if (h[i] == mx1[bl])
{
fr[bl] ++;
}
else if (h[i] > mx2[bl])
{
mx2[bl] = h[i];
}
}
lazy[bl] = inf;
}
void magic(int i, int x)
{
update_block(i / block);
h[i] = (ll)x;
update_block(i / block);
}
void cut(int l, int r, int k)
{
///cout << l << " : " << r << " : " << k << endl;;
while(k > 0)
{
ll max1 = 0, max2 = 0, freq = 0;
///update_block(l / block);
///update_block(r / block);
for (int i = l; i < min((ll)r + 1, (l / block + 1) * block); i ++)
{
h[i] = min(h[i], lazy[i / block]);
if (h[i] > max1)
{
max2 = max1;
max1 = h[i];
freq = 0;
}
if (h[i] == max1)
freq ++;
else if (h[i] > max2)
max2 = h[i];
}
for (int bl = l / block + 1; bl < r / block; bl ++)
{
if (mx1[bl] > max1)
{
max2 = max1;
max1 = mx1[bl];
freq = 0;
}
if (mx1[bl] == max1)
freq += fr[bl];
else if (mx1[bl] > max2)
max2 = mx1[bl];
if (mx2[bl] > max2)
max2 = mx2[bl];
}
if (l / block != r / block)
{
for (int i = (r / block) * block; i <= r; i ++)
{
h[i] = min(h[i], lazy[i / block]);
if (h[i] > max1)
{
max2 = max1;
max1 = h[i];
freq = 0;
}
if (h[i] == max1)
freq ++;
else if (h[i] > max2)
max2 = h[i];
}
}
if (max1 == 0)
break;
///cout << "heree " << max1 << " " << max2 << " " << freq << endl;
if (freq * (max1 - max2) <= k)
{
k = k - freq * (max1 - max2);
for (int i = l; i < min((ll)r + 1, (l / block + 1) * block); i ++)
{
if (h[i] > max2)
h[i] = max2;
}
update_block(l / block);
if (l / block != r / block)
{
for (int i = (r / block) * block; i <= r; i ++)
{
if (h[i] > max2)
h[i] = max2;
}
update_block(r / block);
}
for (int bl = l / block + 1; bl < r / block; bl ++)
{
if (mx1[bl] == max1)
{
lazy[bl] = max2;
sum[bl] -= fr[bl] * (mx1[bl] - max2);
mx1[bl] = max2;
}
if (mx1[bl] == mx2[bl])
update_block(bl);
}
}
else
{
ll dec = k / freq;
for (int i = l; i < min((ll)(r + 1), (l / block + 1) * block); i ++)
{
if (h[i] == max1)
h[i] -= dec;
}
update_block(l / block);
if (l / block != r / block)
{
for (int i = (r / block) * block; i <= r; i ++)
{
if (h[i] == max1)
h[i] -= dec;
}
update_block(r / block);
}
for (int bl = l / block + 1; bl < r / block; bl ++)
{
if (mx1[bl] == max1)
{
lazy[bl] = mx1[bl] - dec;
sum[bl] -= fr[bl] * dec;
mx1[bl] -= dec;
}
}
k = k - dec * freq;
max1 -= dec;
for (int i = l; i < min((ll)(r + 1), (l / block + 1) * block) && k > 0; i ++)
{
if (h[i] == max1)
h[i] --, k --;
}
update_block(l / block);
for (int bl = l / block + 1; bl < r / block; bl ++)
{
if (mx1[bl] == max1)
{
if (fr[bl] <= k)
{
k -= fr[bl];
lazy[bl] = mx1[bl] - 1;
sum[bl] -= fr[bl];
mx1[bl] --;
if (mx1[bl] == mx2[bl])
update_block(bl);
}
else
{
update_block(bl);
for (int i = bl * block; i < (bl + 1) * block && k > 0; i ++)
if (h[i] == max1)
h[i] --, k --;
update_block(bl);
break;
}
}
}
if (l / block != r / block)
{
for (int i = (r / block) * block; i <= r && k > 0; i ++)
{
if (h[i] == max1)
h[i] --, k --;
}
update_block(r / block);
}
break;
}
}
}
ll inspect(int l, int r)
{
/**for (int i = 1; i <= n; i ++)
update_block(i / block);
for (int i = 1; i <= n; i ++)
cout << h[i] << " ";
cout << endl;*/
///cout << l << " " << r << endl;
ll ans = 0;
update_block(l / block);
for (int i = l; i < min((ll)(r + 1), (l / block + 1) * block); i ++)
{
ans = ans + h[i];
}
if (l / block != r / block)
{
update_block(r / block);
for (int i = (r / block) * block; i <= r; i ++)
{
ans = ans + h[i];
}
}
for (int bl = l / block + 1; bl < r / block; bl ++)
{
ans = ans + sum[bl];
}
return ans;
}
int main()
{
freopen("weird.txt", "r", stdin);
int N, Q;
cin >> N >> Q;
int h[N + 1];
for (int i = 1; i <= N; ++i)
cin >> h[i];
initialise(N, Q, h);
int t;
while(cin >> t)
{
if (t == 1)
{
int l, r, k;
cin >> l >> r >> k;
cut(l, r, k);
}
else if (t == 2)
{
int i, x;
cin >> i >> x;
magic(i, x);
}
else
{
int l, r;
cin >> l >> r;
cout << inspect(l, r) << '\n';
}
}
return 0;
}
Compilation message
weirdtree.cpp: In function 'int main()':
weirdtree.cpp:282:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
282 | freopen("weird.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccE9cJgr.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccYARqPn.o:weirdtree.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
