acpc 2017 problem L tle

#include <bits/stdc++.h>
using namespace std;

#define ll long long

// use a segtree to store water level sum
// O(n(logn)^2)
struct Wall {
    struct SegTree {
        int length;
        vector<ll> value;
        bitset<400001> lazy;
        void resize(const int& n) {
            for (length = 1; length < n; length*=2);
            value.resize(2*length);
            //lazy.resize(2*length);
            clear();
        }
        void clear() {
            memset(&value[0], 0, 2*length*sizeof(value[0]));
            //memset(&lazy[0], 0, length*sizeof(lazy[0]));
            lazy.reset();
        }
        // lazy propagate happens only after overwrite so we can do this
        void propagate(const int& i) {
            value[2*i] = value[2*i+1] = value[i]/2;
            lazy[2*i] = lazy[2*i+1] = true;
            lazy[i] = false;
        }
        void increase(const int& x, const ll& h, const int& start, const int& end) {
            // get index
            const int i = (length+x-1)/(end-start+1);
            if (start == end) {
                value[i] += h;
                return;
            }
            // lazy propagation
            if (lazy[i]) propagate(i);
            // update sum
            value[i] += h;

            const int mid = (start+end-1)/2;
            if (x <= mid) increase(x, h, start, mid);
            else increase(x, h, mid+1, end);
        }
        void increase(const int& x, ll h) {
            increase(x, h, 1, length);
        }
        void overwrite(const int& xl, const int& xr, const ll& h, const int& start, const int& end) {
            // get index
            const int i = (length+xl-1)/(end-start+1);
            if (xl == start && xr == end) {
                value[i] = (xr-xl+1)*h;
                lazy[i] = true;
                return;
            }
            // no lazy propagation because overwrite
            // update sum
            value[i] += (xr-xl+1)*h - query(xl, xr);

            const int mid = (start+end-1)/2;
            if (xr <= mid) overwrite(xl, xr, h, start, mid);
            else if (xl > mid) overwrite(xl, xr, h, mid+1, end);
            else {
                overwrite(xl, mid, h, start, mid);
                overwrite(mid+1, xr, h, mid+1, end);
            }
        }
        void overwrite(const int& xl, const int& xr, ll h) {
            if (xl > xr) overwrite(xr, xl, h, 1, length);
            else overwrite(xl, xr, h, 1, length);
        }
        ll query(const int& xl, const int& xr, const int& start, const int& end) {
            // get index
            const int i = (length+xl-1)/(end-start+1);
            if (xl == start && xr == end) {
                return value[i];
            }
            // lazy propagation
            if (lazy[i]) propagate(i);

            const int mid = (start+end-1)/2;
            if (xr <= mid) return query(xl, xr, start, mid);
            else if (xl > mid) return query(xl, xr, mid+1, end);
            else {
                return query(xl, mid, start, mid) + query(mid+1, xr, mid+1, end);
            }
        }
        ll query(const int& xl, const int& xr) {
            return query(xl, xr, 1, length);
        }
        ll query(const int& x) {
            return query(x, x, 1, length);
        }
    };
    SegTree water; // water level = max(height of water, height of wall)
    int wallsum; // sum of blocks
    vector<int> wallheight; // heights
    // highest water level
    int maxindex;
    int maxheight;
    Wall(const int& n) {
        water.resize(n);
        wallheight.resize(n+1);
    }
    void clear() {
        water.clear();
        memset(&wallheight[0], 0, wallheight.size()*sizeof(wallheight[0]));
        wallsum = 0;
        maxindex = 1;
        maxheight = 0;
    }
    ll volume(const int& n) {
        return water.query(1, n) - wallsum;
    }
    int searchinc(int left, int right, const int& upperbound) {
        int mid;
        while (left <= right) {
            mid = (left+right)/2;
            if (water.query(mid) > upperbound)
                right = mid-1;
            else left = mid+1;
        }
        if (water.query(mid) > upperbound)
            mid--;
        return mid;
    }
    int searchdec(int left, int right, const int& upperbound) {
        int mid;
        while (left <= right) {
            mid = (left+right)/2;
            if (water.query(mid) > upperbound)
                left = mid+1;
            else right = mid-1;
        }
        if (water.query(mid) > upperbound)
            mid++;
        return mid;
    }
    void insert(const int& i, const int& h) {
        // get waterheight
        const int waterheight = water.query(i);
        // increase wall height
        wallheight[i] += h;
        wallsum += h;
        // update water height
        if (wallheight[i] > waterheight) {
            if (wallheight[i] >= maxheight) {
                // new maximum
                // update everything between i and maxheight.first
                water.overwrite(i, maxindex, maxheight);
                water.overwrite(i, i, wallheight[i]);
                // update new max height
                maxindex = i;
                maxheight = wallheight[i];
            }
            else {
                // update everything between wallheight and next water level
                if (i < maxindex)
                    water.overwrite(i, searchinc(i,maxindex,wallheight[i]), wallheight[i]);
                else
                    water.overwrite(searchdec(maxindex,i,wallheight[i]), i, wallheight[i]);
            }
        }
    }
};

int main() {
    //ios::sync_with_stdio(0);
    cin.tie(0);

    Wall waterwall(100000);
    int cols, queries, index, height;
    char type;
    int T;
    scanf("%d", &T);
    while (T--) {
        waterwall.clear();
        scanf("%d %d", &cols, &queries);
        for (int i = 0; i < cols; i++) {
            scanf("%d", &height);
            waterwall.insert(i+1, height);
        }
        for (int i = 0; i < queries; i++) {
            type = getchar();
            while (isspace(type))
                type = getchar();
            if (type == 'P') {
                printf("%d\n", waterwall.volume(cols));
            }
            else {
                scanf("%d %d", &index, &height);
                waterwall.insert(index, height);
            }
        }
    }

    return 0;
}