题目里的算法即单调队列。

考虑对于区间里每个数，求出它能在队列里存活多久。

对于每个 $i$，求出一个 $t_i$。这个数表示 $a_i$ 后面第一个 $< a_i$ 的数是 $a_{t_i}$。若 $a_i$ 从队尾弹出，则是在压入 $a_{t_i}$ 时弹出的。特别地，若 $a_i$ 是后缀最小值，则 $t_i=n+1$。

$t$ 可以单调栈求出。

$a_i$ 也有可能在队头弹出，设此次询问 $(l_j,r_j,k_j)$，则若 $i \le r_j-k_j$ 且在往队列里压入 $a_{i+k_j}$ 时还没有从队尾弹出，则它会被弹出。

若 $i > r_j-k_j$，显然 $i$ 不会从队尾弹出，但是它最多也只能存活到 $r_j$。

综上答案为

$$\sum_{i=l_j}^{r_j-k_j} \min(t_i-1,i+k_j-1) + \sum_{i=r_j-k_j+1}^{r_j} \min(t_i-1,r_j) - \sum_{i=l_j}^{r_j} (i-1)$$

对于左式，变化为 $\sum_{i=l_j}^{r_j-k_j} \min(t_i-i,k_j)+\sum_{i=l_j}^{r_j-k_j}(i-1)$。

直接二维数点。时间复杂度 $O((n+q) \log n)$，可以通过。

记得特判 $k \ge r-l+1$ 的情况。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=300100;
int n,q,m,x[N],t[N],s[N],ans[N],A;
stack<int> stk;
struct BIT{
	int b[N];
	void clr(){memset(b,0,sizeof(b));}
	void add(int p,int k){while(p<=n) b[p]+=k,p+=p&-p;}
	int qry(int p){int r=0; while(p) r+=b[p],p-=p&-p; return r;}
	BIT(){clr();}
}B1,B2;
struct query{int x,y,idx;};
vector<query> q1[N],q2[N];
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>x[i],s[i]=s[i-1]+i-1;
	for(int i=n;i>=1;i--){
		while(!stk.empty()&&x[stk.top()]>x[i]) stk.pop();
		t[i]=stk.empty()?n+1:stk.top(),stk.push(i);
	}
	for(int i=1,l,r,k;i<=q;i++){
		cin>>l>>r>>k,ans[i]=-s[r]+s[max(r-k,l-1)];
		if(k<r-l+1) q1[l-1].push_back({k,-1,i}),q1[r-k].push_back({k,1,i});
		q2[max(r-k,l-1)].push_back({r,-1,i}),q2[r].push_back({r,1,i});
	}
	for(int i=1;i<=n;i++){
		B1.add(t[i]-i,t[i]-i),B2.add(t[i]-i,1);
		for(auto [x,y,z]:q1[i]) ans[z]+=y*(B1.qry(x)+x*(i-B2.qry(x)));
	}
	B1.clr(),B2.clr();
	for(int i=1;i<=n;i++){
		B1.add(t[i]-1,t[i]-1),B2.add(t[i]-1,1);
		for(auto [x,y,z]:q2[i]) ans[z]+=y*(B1.qry(x)+x*(i-B2.qry(x)));
	}
	for(int i=1;i<=q;i++) A^=(i*i+ans[i]);
	return cout<<A<<'\n',0;
}