1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
struct SegTree
{
    struct Node
    {
        int l,r;
        int lo; // 当前区间最小值
        int add; // 懒加标记
        int non; // 区间非零个数
        Node() : add(0) {}
        inline int len() { return r - l + 1; }
    };

    vector<Node> tree;
    vector<int> arr;

    SegTree(const vector<int>& _arr) : arr(_arr) 
    {
        tree.resize((_arr.size() + 5) << 2,Node());
        build(1,1,_arr.size()-1);   
    }

    void push_up(int p)
    {
        tree[p].lo = min(tree[ls(p)].lo,tree[rs(p)].lo);
        tree[p].non = tree[ls(p)].non + tree[rs(p)].non;
    }

    void apply_add(int p,int val)
    {
        tree[p].lo += val;
        tree[p].add += val;
    }

    void push_down(int p)
    {
        if(tree[p].add != 0)
        {
            apply_add(ls(p),tree[p].add);
            apply_add(rs(p),tree[p].add);
            tree[p].add = 0;
        }
    }

    void build(int p,int l,int r)
    {
        tree[p].l = l;
        tree[p].r = r;
        if(l == r)
        {
            tree[p].lo = arr[l];
            tree[p].non = 1; // 初始值>0
            return;
        }
        int mid = (l + r) >> 1;
        build(ls(p),l,mid);
        build(rs(p),mid+1,r);
        push_up(p);
    }

    void updateadd(int p,int ul,int ur,int val)
    {
        if(tree[p].l >= ul and tree[p].r <= ur)
        {
            apply_add(p,val);
            return;
        }   
        push_down(p);
        int mid = (tree[p].l + tree[p].r) >> 1;
        if(ul <= mid) updateadd(ls(p),ul,ur,val);
        if(ur > mid) updateadd(rs(p),ul,ur,val);
        push_up(p);
    }
    int query(int p,int ql,int qr,int k)
    {   
        // 如果都是0，一个也选不了
        if(tree[p].non == 0) return 0;
        if(ql <= tree[p].l and tree[p].r <= qr)  
        {
            // 全部大于K，区间减K即可
            if(tree[p].lo > k) 
            {
                updateadd(p,tree[p].l,tree[p].r,-k);
                return tree[p].non * k;
            } 
            else 
            {
                // 否则暴力递归到叶子节点，暴力拾取
                if(tree[p].l == tree[p].r) 
                {
                    int temp = tree[p].lo;
                    tree[p].lo = INF;
                    tree[p].non = 0;
                    tree[p].add = 0;
                    return temp;
                }
                push_down(p);
                int res = 0;
                int mid = (tree[p].l + tree[p].r) >> 1;
                if(mid >= ql) res += query(ls(p),ql,qr,k);
                if(mid < qr) res += query(rs(p),ql,qr,k); 
                push_up(p);
                return res;
            }
        }
        else
        {
            push_down(p);
            int res = 0;
            int mid = (tree[p].l + tree[p].r) >> 1;
            if(mid >= ql) res += query(ls(p),ql,qr,k);
            if(mid < qr) res += query(rs(p),ql,qr,k);
            push_up(p);
            return res;
        }
    }   
};
void solve()
{   
    int n;
    cin >> n;
    vector<int> arr(n+1);
    for(int i=1;i<=n;i++) cin >> arr[i];
    SegTree st(arr);
    int q;
    cin >> q;
    while(q--)
    {
        int l,r,k;
        cin >> l >> r >> k;
        cout << st.query(1,l,r,k) << endl;
    }
}