双倍经验。

怎么 USACO 都开始出原题了。。。

思路：

插入标记回收算法板子。

考虑扫描线，在 $l$ 处将 $x$ 插入进去，每扫过一个对全局进行一次变换，最后再 $r$ 处将 $x$ 取出。

考虑一次全局变换是什么：

• 若 $x > 0$，那么 $x \gets x - a_i$。

• 否则若 $x \le 0$，那么 $x \gets x + a_i$。

考虑使用平衡树维护上述过程，首先按照 $\le 0$ 分裂为 $x, y$，将 $x$ 打上 $+a_i$ 的懒标记，$y$ 打上 $-a_i$ 的懒标记。

但是此时两平衡树值域有交，使用平衡树有交合并算法即可做到 $O(N \log^2 N)$。

完整代码：

 #include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 2e5 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x > 9)
	  write(x / 10);
	putchar(x % 10 + '0');
}
int n, m, l, r, x, rt, cnt;
int id[N], a[N], ans[N];
vector<int> V[N];
vector<pair<int, int>> Q[N];
namespace DSU{
	int fa[N];
	inline void init(int n){
		for(int i = 1; i <= n; ++i)
		  fa[i] = i;
	}
	inline int Find(int x){
		if(x != fa[x])
		  return fa[x] = Find(fa[x]);
		return fa[x];
	}
	inline void merge(int x, int y){
		x = Find(x), y = Find(y);
		if(x == y)
		  return ;
		fa[x] = y;
	}
};
mt19937 R(time(0));
struct Node{
	int fa;
	int lson, rson;
	ll data, add;
	bool tag;
	ll key;
}X[N];
inline int newnode(ll v){
	++cnt;
	X[cnt].lson = X[cnt].rson = X[cnt].add = X[cnt].tag = 0;
	X[cnt].key = R();
	X[cnt].data = v;
	return cnt;
}
inline void pushup(int k){
	X[X[k].lson].fa = X[X[k].rson].fa = k;
}
inline void add(int k, ll v){
	if(!k)
	  return ;
	X[k].data += v;
	X[k].add += v;
}
inline void rev(int k){
	if(!k)
	  return ;
	X[k].data = -X[k].data;
	X[k].add = -X[k].add;
	X[k].tag ^= 1;
}
inline void push_down(int k){
	if(X[k].tag){
		swap(X[k].lson, X[k].rson);
		rev(X[k].lson);
		rev(X[k].rson);
		X[k].tag = 0;
	}
	if(X[k].add){
		add(X[k].lson, X[k].add);
		add(X[k].rson, X[k].add);
		X[k].add = 0;
	}
}
inline void split(int k, ll v, int &x, int &y){
	if(!k){
		x = y = 0;
		return ;
	}
	push_down(k);
	if(X[k].data <= v){
		x = k;
		split(X[x].rson, v, X[x].rson, y);
		pushup(x);
	}
	else{
		y = k;
		split(X[y].lson, v, x, X[y].lson);
		pushup(y);
	}
}
inline int merge(int x, int y){
	if(!x || !y)
	  return x + y;
	if(X[x].key < X[y].key){
		push_down(x);
		X[x].rson = merge(X[x].rson, y);
		pushup(x);
		return x;
	}
	else{
		push_down(y);
		X[y].lson = merge(x, X[y].lson);
		pushup(y);
		return y;
	}
}
inline void dfsfa(int k, int v){
	if(!k)
	  return ;
	DSU::merge(k, v);
	dfsfa(X[k].lson, v);
	dfsfa(X[k].rson, v);
}
inline int Merge(int x, int y){
	if(!x || !y)
	  return x + y;
	if(X[x].key >= X[y].key)
	  swap(x, y);
	push_down(x);
	int l, r, p;
	split(y, X[x].data, l, r);
	split(l, X[x].data - 1, l, p);
	dfsfa(p, x);
	X[x].lson = Merge(X[x].lson, l);
	X[x].rson = Merge(X[x].rson, r);
	pushup(x);
	return x;
}
inline void insert(ll v){
	int x, y;
	split(rt, v, x, y);
	rt = merge(merge(x, newnode(v)), y);
}
inline ll getval(int k){
	if(X[k].fa)
	  getval(X[k].fa);
	push_down(k);
	return X[k].data;
}
bool End;
int main(){
//	open("A.in", "A.out");
	n = read();
	for(int i = 1; i <= n; ++i)
	  a[i] = read();
	m = read();
	DSU::init(m);
	for(int i = 1; i <= m; ++i){
		l = read(), r = read(), x = read();
		Q[l].push_back({x, i});
		V[r].push_back(i);
	}
	for(int i = 1; i <= n; ++i){
		for(auto t : Q[i]){
			insert(t.fi);
			id[t.se] = cnt;
		}
		int x, y;
		split(rt, 0, x, y);
		add(x, a[i]), add(y, -a[i]);
		rt = Merge(x, y);
		for(auto v : V[i])
		  ans[v] = getval(DSU::Find(id[v]));
	}
	for(int i = 1; i <= m; ++i){
		write(ans[i]);
		putchar('\n');
	}
	cerr << '\n' << abs(&Begin - &End) / 1048576 << "MB";
	return 0;
}