论我耗光了512MB

	struct segTree {
		struct segTree_Node {
			int sum, tag;
			segTree_Node* ls;
			segTree_Node* rs;
			segTree_Node() : sum(0), tag(0), ls(NULL), rs(NULL) {}
		};
		segTree_Node nulltree;
		segTree_Node* root;
		int MINval,MAXval;
		segTree() : root(NULL), MINval(0), MAXval(0) {} void merge(segTree_Node* m1, segTree_Node* m2, segTree_Node* &m3) {
			if (m3 == NULL) m3 = new segTree_Node();
			if (m1 == NULL && m2 == NULL) m3->sum = 0;
			else if (m1 == NULL) m3->sum = m2->sum;
			else if (m2 == NULL) m3->sum = m1->sum;
			else m3->sum = m1->sum + m2->sum;
		} void merge(segTree_Node m1, segTree_Node m2, segTree_Node &m3) {
			m3.sum = m1.sum + m2.sum;
		} void add_tag(int dl, int dr, segTree_Node* &rt, ll k) {
			if (rt == NULL) rt = new segTree_Node();
			rt->tag += k;
			rt->sum += (dr - dl + 1) * k;
		} void down(int dl, int dr, segTree_Node* &rt) {
			if (rt == NULL) return;
			if (rt->tag != 0) {
				int mid = (dl + dr) >> 1;
				add_tag(dl, mid, rt->ls, rt->tag);
				add_tag(mid + 1, dr, rt->rs, rt->tag);
				rt->tag = 0;
			}
		} void build(int dl, int dr, segTree_Node* &rt, ll *arr) {
			if (rt == NULL) rt = new segTree_Node();
			if (dl == dr) {
				rt->sum = arr[dl];
				return;
			}
			int mid = (dl + dr) >> 1;
			build(dl, mid, rt->ls, arr);
			build(mid + 1, dr, rt->rs, arr);
			merge(rt->ls, rt->rs, rt);
		} segTree_Node query(int dl, int dr, segTree_Node* rt, int l, int r) {
			if (rt == NULL) return nulltree;
			if (l <= dl && dr <= r) return *rt;
			down(dl, dr, rt);
			int mid = (dl + dr) >> 1;
			segTree_Node res=nulltree;
			if (l <= mid) merge(query(dl, mid, rt->ls, l, r), res, res);
			if (r > mid) merge(res, query(mid + 1, dr, rt->rs, l, r), res);
			return res;
		} void edit(int dl, int dr, segTree_Node* &rt, int l, int r, ll k) {
			if (rt == NULL) rt = new segTree_Node();
			if (l <= dl && dr <= r) {
				add_tag(dl, dr, rt, k);
				return;
			}
			down(dl, dr, rt);
			int mid = (dl + dr) >> 1;
			if (l <= mid) edit(dl, mid, rt->ls, l, r, k);
			if (r > mid) edit(mid + 1, dr, rt->rs, l, r, k);
			merge(rt->ls,rt->rs,rt);
		} void build(int n, ll *arr) {
			build(1, n, root, arr);
		} void resize(int _MINval,int _Maxval){
			MAXval=_Maxval,MINval=_MINval;
		} segTree_Node query(int l,int r){
			return query(MINval,MAXval,root,l,r);
		} void edit(int l,int r,ll k){
			edit(MINval,MAXval,root,l,r,k);
		} void clear(segTree_Node* rt){
			if(rt==NULL) return;
			clear(rt->ls);
			clear(rt->rs);
			delete rt;
		} void clear(){
			clear(root);
			root=NULL;
		}
	};
	struct segTree_2D {
		struct segTree_2D_Node {
			segTree sum, tag;
			segTree_2D_Node* ls;
			segTree_2D_Node* rs;
			segTree_2D_Node() : ls(NULL), rs(NULL) {}
		};
		segTree_2D_Node* root;
		int MINxval,MAXxval,MINyval,MAXyval;
		segTree_2D() : root(NULL), MINxval(0), MAXxval(0), MINyval(0), MAXyval(0) {} 
		ll query(int dl, int dr, segTree_2D_Node* rt, int lx, int rx, int ly, int ry, ll tag) {
			if (rt == NULL) return tag;
			if (lx <= dl && dr <= rx) return rt->sum.query(ly,ry).sum+tag;
			int mid = (dl + dr) >> 1;
			ll nwtag=rt->tag.query(ly,ry).sum, res=0;
			if (lx <= mid) res+=query(dl,mid,rt->ls,lx,rx,ly,ry,tag+nwtag);
			if (rx > mid) res+=query(mid+1,dr,rt->rs,lx,rx,ly,ry,tag+nwtag);
			return res;
		} void edit(int dl, int dr, segTree_2D_Node* &rt, int lx, int rx, int ly, int ry, ll k) {
			if (rt == NULL) rt = new segTree_2D_Node(), rt->sum.resize(MINyval,MAXyval),rt->tag.resize(MINyval,MAXyval);
			rt->sum.edit(ly,ry,(min(dr,rx)-max(dl,lx)+1)*k);
			if (lx <= dl && dr <= rx) {
				rt->tag.edit(ly,ry,k);
				return;
			}
			int mid = (dl + dr) >> 1;
			if (lx <= mid) edit(dl, mid, rt->ls, lx, rx, ly, ry, k);
			if (rx > mid) edit(mid + 1, dr, rt->rs, lx, rx, ly, ry, k);
		} void resize(int _MINxval,int _Maxxval,int _MINyval,int _Maxyval){
			MAXxval=_Maxxval,MINxval=_MINxval,MAXyval=_Maxyval,MINyval=_MINyval;
		} ll query(int lx,int rx,int ly,int ry){
			return query(MINxval,MAXxval,root,lx,rx,ly,ry,0);
		} void edit(int lx,int rx,int ly,int ry,ll k){
			edit(MINxval,MAXxval,root,lx,rx,ly,ry,k);
		} void clear(segTree_2D_Node* rt){
			if(rt==NULL) return;
			clear(rt->ls);
			clear(rt->rs);
			rt->sum.clear();
			rt->tag.clear();
			delete rt;
		} void clear(){
			clear(root);
			root=NULL;
		}
	};
segTree_2D tree;
int n,m,x,a,b,c;
const int MXN=2e6+5;
int main() {
	//	freopen(".in", "r", stdin);
	//	freopen(".out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	I n >> m;
	tree.resize(1,n,1,MXN);
	for(int i=1;i<=n;i++) I x,tree.edit(i,i,x,x,1);
	for(int i=1;i<=m;i++){
		I a >> b >> c;
		O tree.query(a,b,1,c) << "\n";
	}
	return 0;
}