注意到如果 $\text{query}(a,b,c)$ 为真，那么 $\text{query}(\geq a,\geq b,c)$ 一定为真。
从小到大枚举询问中 $a$ 的值，按横坐标从小到大依次加入每个点，维护 $f_c$ 表示最小的 $b$ 满足 $\text{query}(a,b,c)$ 为真。
假设当前正在加入点 $(x,y,w)$，有 $f_{(c+w)\bmod n}=\min(f_{(c+w)\bmod n},\max(f_c,y))$。
观察状态转移方程可知，如果 $y\geq f_{(c+w)\bmod n}$，那么就没有更新的必要。令 $m=\max(f_0,f_1,\dots,f_{n-1})$，那么如果 $y\geq m$，则这个点是完全无用的，可以直接跳过。
由于数据随机，可以近似地认为加入 $k$ 个点后，所有 $2^k$ 个子集和模 $n$ 的结果在 $[0,n)$ 等概率均匀分布。可以看作 $2^k$ 个小球随机放入 $n$ 个洞之中，填满所有 $n$ 个洞所需的期望球数是 $O(n\log n)$，因此 $k=O(\log n)$ 时期望可以填满整个 $f$ 数组。这说明，$f$ 数组的最大值的期望值等于所有已经加入的点的纵坐标的第 $O(\log n)$ 小值，即 $O(\frac{n\log n}{k})$。
于是，加入的第 $k$ 个点的纵坐标 $y<m$ 的概率为 $O(\frac{\log n}{k})$，期望只需要更新 $O(\sum_{k=1}^n\frac{\log n}{k})=O(\log^2n)$ 遍 $f$ 数组。由于这个值并不大，每次暴力 $O(n)$ 更新整个数组即可。有了 $f$ 数组就可以很容易地求出最终的答案。
时间复杂度 $O(n\log^2n)$。
#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
const int N=500005;
int n,i,j,mx,f[N],g[N];ull suf[N],sum,ans;
struct E{int x,y,v;}e[N];
inline bool cmp(const E&a,const E&b){return a.x<b.x;}
inline void insert(int y,int v){if(y>=mx||v==n)return;for(int i=0;i<n;i++)g[i]=f[i];for(int i=0,j=v;i<n;){int tmp=max(f[i],y);if(tmp<g[j])g[j]=tmp;i++;j++;if(j==n)j=0;}mx=0;sum=0;for(int i=0;i<n;i++){f[i]=g[i];sum+=i*suf[f[i]];if(f[i]>mx)mx=f[i];}
}
int main(){ios_base::sync_with_stdio(0);cin.tie(0);cin>>n;for(i=1;i<=n;i++)cin>>e[i].x>>e[i].y>>e[i].v;sort(e+1,e+n+1,cmp);for(i=n;i;i--)suf[i]=suf[i+1]+i;for(i=0;i<n;i++)f[i]=n+1;f[0]=0;mx=n+1;for(i=j=1;i<=n;i++){while(j<=n&&e[j].x<=i){insert(e[j].y,e[j].v);j++;}ans+=sum*i;}cout<<ans;
}
