#include <bits/stdc++.h>
using namespace std;
int main() {
    freopen("in", "w", stdout);
    int n = 5e4;
    cout << n << ' ' << n << endl;
    for (int i = 1; i <= n; i++) printf("%d ", i);
    putchar('\n');
    for (int i = 1; i <= n; i++) printf("%d ", i);
    putchar('\n');
    for (int i = 1; i <= n; i++) printf("%d %d %d\n", 4, 1, n);
    return 0;
}

题解 ： TLE。

原因：题解中有这么一句话：

若当前节点有一个数列的 mn==mx 说明这个数列这一段区间的所有数是相等的（可以想想为什么），这个时候就可以直接累加上两个区间的矩阵乘积 。

以及题解代码中的 query:

void query(int p,int l,int r){
	if(t[p][0].l>r||t[p][0].r<l) return;
	if(l<=t[p][0].l&&t[p][0].r<=r){
	    if(t[p][0].mx==t[p][0].mn){
	    	ans+=t[p][0].mn.m*t[p][1].sum;
	    	return;
		}
		if(t[p][1].mx==t[p][1].mn){
			ans+=t[p][1].mn.m*t[p][0].sum;
			return;
		}
	}
	pushdown(p,0); pushdown(p,1);
	query(ls,l,r); query(rs,l,r);
}

我想了想为什么，然后发现这样做时间复杂度是错的。

这个时间复杂度是基于颜色段的，即只要颜色段非常多，时间复杂度就会升天。

我并没有在题面中找到对此相关的性质，因此我认为该题解有误。

正确的做法在题解中也并没有给出，申请撤下该题解。

@outcast

@feecle6418