Submission #69875903

---

Source Code Expand

/* Code By WCM */
/*
Date:
大致思路：
复杂度：
期望得分：
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <vector>
#include <queue>
#include <cmath>
#define int long long

using namespace std;

inline int read();
void write(int);
void writeln(int);

const int N = 3e5 + 5, B = 800, inf = 1e18;

struct D {
    int a[B], siz, mnv, mxv, sum;
    bool fl;
} bl[B];
int st[B], ed[B], cnt = 0, Size = 0;

void rebuild(int idx) {
    D& blo = bl[idx];
    blo.mnv = inf, blo.mxv = -inf, blo.sum = 0, blo.fl = 1;
    for(int i = 0; i < blo.siz; i++) {
        int vl = blo.a[i];
        blo.fl = (vl > 0 ? 0 : blo.fl), blo.mnv = min(blo.mnv, vl), blo.mxv = max(blo.mxv, vl), blo.sum += vl;
    }
    if(blo.mnv == inf) blo.mnv = blo.mxv = 0;
}

void init(int A[], int n) {
    Size = sqrt(n) + 1, cnt = (n + Size - 1) / Size;
    for(int i = 0; i < cnt; i++) {
        st[i] = i * Size, ed[i] = min((i + 1) * Size - 1, n - 1), bl[i].siz = ed[i] - st[i] + 1;
        for(int j = 0; j < bl[i].siz; j++) bl[i].a[j] = A[st[i] + j];
        rebuild(i);
    }
}

int modify(int idx, int Ql, int Qr, int k) {
    D& blo = bl[idx];
    if(blo.fl) return 0;
    int L = st[idx], R = ed[idx], cc = 0;
    for(int i = max(L, Ql); i <= min(R, Qr); i++) {
        int id = i - L, bc = min(blo.a[id], k);
        cc += bc, blo.a[id] -= bc;
    }
    rebuild(idx);
    return cc;
}

int update(int idx, int k) {
    D& blo = bl[idx];
    if(blo.fl) return 0;
    if(blo.mnv >= k) {
        int cc = k * blo.siz;
        for(int i = 0; i < blo.siz; i++) blo.a[i] -= k;
        blo.mnv -= k, blo.mxv -= k, blo.sum -= cc;
        if(blo.mnv == 0) blo.fl = 1;
        return cc;
    } 
	else if(blo.mxv <= k) {
        int cc = blo.sum;
        for(int i = 0; i < blo.siz; i++) blo.a[i] = 0;
        blo.mnv = blo.mxv = blo.sum = 0, blo.fl = 1;
        return cc;
    } 
	else {
        int cc = 0;
        for(int i = 0; i < blo.siz; i++) {
            int bc = min(blo.a[i], k);
            cc += bc, blo.a[i] -= bc;
        }
        rebuild(idx);
        return cc;
    }
}

int query(int l, int r, int k) {
    int ret = 0;
    for(int i = 0; i < cnt; i++) {
        if(st[i] > r) break;
        if(ed[i] < l) continue;
        if(l <= st[i] && ed[i] <= r) ret += update(i, k);
        else ret += modify(i, l, r, k);
    }
    return ret;
}

int n, Q, A[N];

signed main() {
	
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

    n = read();
    for(int i = 0; i < n; i++) A[i] = read();
    
    init(A, n);
    Q = read();
    for(int i = 0; i < Q; i++) {
        int l = read() - 1, r = read() - 1, k = read();
        printf("%lld\n", query(l, r, k));
    }
    
//	printf("\nThe time used: ");
//	printf("%.2lfs",(double)clock()/CLOCKS_PER_SEC);

	return 0;

}

inline int read() {
	int res = 0, f = 1;
	char ch = getchar();
	while( !(ch >= '0' && ch <= '9') ) {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		res = (res << 1) + (res << 3) + (ch ^ 48);
		ch = getchar();
	}
	return res * f;
}

void write(int x) {
	static int sta[35];
	int top = 0;
	do {
		sta[top++] = x % 10;
		x /= 10;
	} while(x);
	while(top) putchar(sta[--top] ^ 48);
}

void writeln(int x) {
	write(x);
	putchar('\n');
}

Submission Info

Judge Result