#pragma GCC optimize("O2,unroll-loops") #include "weirdtree.h" #include <bits/stdc++.h> using namespace std; #define sz(x) (int)x.size() #define all(x) x.begin() , x.end() const int N = 3e5 + 7; const int inf = 1e9 + 7; struct Node{ int maxcnt , max1 , max2 , chmin; long long sum; Node():maxcnt(0),max1(0),max2(0),sum(0),chmin(inf){} } dumb; Node merge(Node a , Node b){ Node c; c.max1 = max(a.max1 , b.max1); if(c.max1 == a.max1)c.maxcnt += a.maxcnt; if(c.max1 == b.max1)c.maxcnt += b.maxcnt; if(c.max1 != a.max1)c.max2 = max(c.max2 , a.max1); if(c.max1 != a.max2)c.max2 = max(c.max2 , a.max2); if(c.max1 != b.max1)c.max2 = max(c.max2 , b.max1); if(c.max1 != b.max2)c.max2 = max(c.max2 , b.max2); c.sum = a.sum + b.sum; return c; } vector<Node> tree(4 * N); void push(int ind , int l , int r){ if(tree[ind].chmin != inf){ // cout << "push0 : " << ind << " " << l << " " << r << endl; // cout << "max1 : " << tree[ind].max1 << endl; // cout << "max2 : " << tree[ind].max2 << endl; // cout << "maxcnt : " << tree[ind].maxcnt << endl; // cout << "chmin : " << tree[ind].chmin << endl; if(tree[ind].chmin <= tree[ind].max1 and tree[ind].max2 < tree[ind].chmin){ tree[ind].sum -= 1LL * tree[ind].maxcnt * (tree[ind].max1 - tree[ind].chmin); tree[ind].max1 = tree[ind].chmin; if(l != r){ tree[ind*2].chmin = min(tree[ind*2].chmin , tree[ind].chmin); tree[ind*2+1].chmin = min(tree[ind*2+1].chmin , tree[ind].chmin); } } else if(tree[ind].chmin <= tree[ind].max2){ assert(l != r); int mid = (l + r) / 2; tree[ind*2].chmin = min(tree[ind*2].chmin , tree[ind].chmin); push(ind*2 , l , mid); tree[ind*2+1].chmin = min(tree[ind*2+1].chmin , tree[ind].chmin); push(ind*2+1 , mid+1 , r); tree[ind] = merge(tree[ind*2] , tree[ind*2+1]); } tree[ind].chmin = inf; // cout << "push1" << endl; } } Node query(int ql , int qr , int ind=1 , int l=0 , int r=N){ push(ind,l,r); // cout << "SUM = " << l << " " << r << " : " << tree[ind].sum << endl; if(l >= ql and r <= qr){ // cout << " GOT IT : " << l << " " << r << " " << tree[ind].sum << endl; return tree[ind]; } else if(l > qr or r < ql){ return dumb; } int mid = (l + r) / 2; return merge(query(ql,qr,ind*2,l,mid) , query(ql,qr,ind*2+1,mid+1,r)); } void update_set(int qp , int qv , int ind=1 , int l=0 , int r=N){ push(ind,l,r); if(l == r){ push(ind,l,r); tree[ind].maxcnt = 1; tree[ind].max1 = qv; tree[ind].sum = qv; tree[ind].max2 = -inf; tree[ind].chmin = inf; // cout << l << " " << r << " | sum : " << tree[ind].sum << endl; return; } int mid = (l + r) / 2; if(qp <= mid)update_set(qp , qv , ind*2 , l , mid); else update_set(qp , qv , ind*2+1 , mid+1 , r); push(ind*2 , l , mid); push(ind*2+1 , mid+1 , r); tree[ind] = merge(tree[ind*2] , tree[ind*2+1]); // cout << l << " " << r << " | sum : " << tree[ind].sum << endl; } void update_chmin(int ql , int qr , int qv , int ind=1 , int l=0 , int r=N){ push(ind,l,r); if(l >= ql and r <= qr){ // cout << "APPLIED : " << l << " " << r << " " << qv << endl; tree[ind].chmin = min(tree[ind].chmin , qv); push(ind,l,r); return; } else if(l > qr or r < ql)return; int mid = (l + r) / 2; update_chmin(ql , qr , qv , ind*2 , l , mid); update_chmin(ql , qr , qv , ind*2+1 , mid+1 , r); push(ind*2 , l , mid); push(ind*2+1 , mid+1 , r); tree[ind] = merge(tree[ind*2] , tree[ind*2+1]); } void initialise(int N, int Q, int h[]) { // cout << "flag0" << endl; for(int i = 1;i<=N;i++){ update_set(i , h[i]); } // cout << "flag1" << endl; // cout << "DONEEE" << endl; } void cut(int l, int r, int k) { // cout << "cut : " << l << " " << r << " " << k << endl; // cout << "BEFORE : ";for(int i = 1;i<=5;i++)cout << query(i,i).max1 << " ";cout << endl; // cout << "flag2" << endl; while(k){ // cout << "NEWCYCLE!!!" << endl; // cout << "K : " << k << endl; Node tmp = query(l,r); if(tmp.max1 == 0)break; // cout << "max1 : " << tmp.max1 << endl; // cout << "max2 : " << tmp.max2 << endl; // cout << "maxcnt : " << tmp.maxcnt << endl; int steps = min(tmp.max1 - tmp.max2 , k / tmp.maxcnt); // cout << "steps : " << steps << endl; // cout << "flag2.1 : " << steps << endl; if(steps){ // cout << "shave off" << endl; update_chmin(l , r , tmp.max1 - steps); k -= steps * tmp.maxcnt; } // cout << "K : " << k << endl; // cout << "flag2.3" << endl; if(steps != tmp.max1 - tmp.max2 and k % tmp.maxcnt){ // cout << "MID : ";for(int i = 1;i<=5;i++)cout << query(i,i).max1 << " ";cout << endl; // cout << "tirtikla : " << k % tmp.maxcnt << endl; // cout << "TARGET : " << tmp.max1 - steps << endl; int L = l , R = r; while(L < R){ int MID = (L + R) / 2; auto bro = query(l,MID); // cout << "MID " << MID << " : " << bro.max1 << " , " << bro.maxcnt << endl; if(bro.max1 != tmp.max1-steps or bro.maxcnt < k % tmp.maxcnt){ // cout << "FLAG0" << endl; L = MID+1; } else { // cout << "FLAG1" << endl; R = MID; } } // cout << "L : " << L << endl; update_chmin(l , L , tmp.max1 - steps - 1); k -= k % tmp.maxcnt; } // cout << "K : " << k << endl; // cout << "flag2.4" << endl; } // cout << "flag3" << endl; // cout << "AFTER : ";for(int i = 1;i<=5;i++)cout << query(i,i).max1 << " ";cout << endl; } void magic(int i, int x) { // cout << "magic : " << i << " " << x << endl; update_set(i , x); // cout << "AFTER : ";for(int i = 1;i<=5;i++)cout << query(i,i).max1 << " ";cout << endl; } long long int inspect(int l, int r) { // cout << "bfrquery : ";for(int i = 1;i<=5;i++)cout << query(i,i).max1 << " ";cout << endl; return query(l,r).sum; } // int main() { // int N, Q; // cin >> N >> Q; // int h[N + 1]; // for (int i = 1; i <= N; ++i) cin >> h[i]; // initialise(N, Q, h); // for (int i = 1; i <= Q; ++i) { // int t; // 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; // }