@[_皎月半洒花](/space/show?uid=28313) 复杂度是$O(nlog^2n)$??
复杂度是伪的
```
#include <bits/stdc++.h>
#define rep(i, j, k) for(int (i) = (j); (i) <= (k); ++(i))
#define dep(i, j, k) for(int (i) = (j); (i) >= (k); --(i))
#define popcount(x) __builtin_popcount(x)
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 5;
int n, m, U, Std, fa[maxn], OP, con;
inline int rand_(int l, int r) {
return rand() % (r - l + 1) + l;
}
int main() {
freopen("data.in", "w", stdout);
srand(time(NULL));
n = 1e5; m = 2e5;
cout << n << " " << m << endl;
con = 1; OP = 0;
rep(i, 1, n) {
if(OP >= 50) con++, OP = 0;
printf("%d ", con);
OP++;
}
cout << endl;
rep(i, 1, n) {
printf("%d %d\n", rand_(1, 50), rand_(n - 50, n));
}
return 0;
}
/*
*/
```
这个生成出来的数据, 你的代码大概要跑很久很久...
by ViXbob @ 2019-03-22 18:33:27
一分钟之内跑不出来
by ViXbob @ 2019-03-22 18:34:03
@[ViXbob](/space/show?uid=50971) 大概是这样的。
但是这道题主席树应该是可以做的吧……虽然不知道到底要怎么做，但是应该是可以的吧……
还有，似乎https://www.luogu.org/problemnew/show/CF840D
这道题是可以过的qaq
所以主席树的话，应该怎么写呢？
by 皎月半洒花 @ 2019-03-22 18:48:40
@[_皎月半洒花](/space/show?uid=28313)
奇数长度数组优化是啥啊？
by あ→_→ @ 2019-03-22 18:56:11
@[ViXbob](/space/show?uid=50971) 您 slay tql (逃
by lrj124 @ 2019-03-22 20:11:49
所以主席树不存在$\log^2$，此帖完结。
by 皎月半洒花 @ 2019-03-23 07:15:25
@[ViXbob](/space/show?uid=50971) 您 slay tql (逃
by EDT_ @ 2019-03-23 09:06:00