因为楼主模拟赛时认为 P1083 $1\leqslant n\leqslant 10^6$ 的数据下，$\Omicron(n\log^2n)$ 的算法会去世，但是事实是 AC 了。

记录

代码如下：

#include<bits/stdc++.h>
#define LL k<<1
#define RR k<<1|1
#define int long long
using namespace std;
const int N = 1e6 + 1;
int n, m, a[N];
struct Node {
	int l, r, minn,lazy; //l:代表起始的天数 r同理
} t[4 * N + 1];
void pushup(int k) {
	t[k].minn = min(t[LL].minn, t[RR].minn);
}
void pushdown(int k){
	if(t[k].lazy){
		t[LL].lazy+=t[k].lazy;
		t[RR].lazy+=t[k].lazy;
		t[LL].minn-=t[k].lazy;
		t[RR].minn-=t[k].lazy;
		t[k].lazy=0;
	}
}
void build(int l, int r, int k) {
	t[k].l = l;
	t[k].r = r;
	if (l == r) {
		t[k].minn = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(l, mid, LL);
	build(mid + 1, r, RR);
	pushup(k);
}
int qurmin(int l, int r, int k) { //查询区间最小值
	int ans = INT_MAX;
	if (l <= t[k].l && r >= t[k].r) {
		return t[k].minn;
	}
	pushdown(k);
	int mid = t[k].l + t[k].r >> 1;
	if (l <= mid) {
		ans = min(ans, qurmin( l, r, LL));
	}
	if (r > mid) {
		ans = min(ans, qurmin( l, r, RR));
	}
	return ans;
}
void change(int l, int r, int k, int sum) { //将区间最小值更新
	if (l <= t[k].l && r >= t[k].r) {//只需要更新大区间即可，反正大区间会覆盖小区间
		t[k].minn-=sum;
		t[k].lazy+=sum;
		pushdown(k);
		return;
	}
	pushdown(k);
	int mid = t[k].l + t[k].r >> 1;
	if (l <= mid) {
		change(l, r, LL, sum);
	}
	if (r > mid) {
		change(l, r, RR, sum);
	}
	pushup(k);
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	build(1, n, 1);
	for (int i = 1; i <= m; i++) {
		int d, s, t;
		cin >> d >> s >> t;
		int minn = qurmin(s, t, 1);
		if (minn < d) {
			cout << "-1\n" << i;
			return 0;
		} else change(s, t, 1, d);
	}
	cout<<0;
	return 0;
}

所以楼主非常疑惑。

楼主最开始认为 $10^6$ 应该是 $\Omicron(n)$ 才对，后面发现 $\Omicron(n\log n)$ 也可以通过，现在发现 $\Omicron(n\log^2n)$ 也可以通过？？？

所以楼主想问一下在 $n$ 大于多少小于多少时，$\Omicron(n\log n)$ 可以通过而 $\Omicron(n \log^2 n)$ 不可以，以及卡掉双 log 是否困难。