这道题最关键的点就在离散化吧。
假如有三张海报[1, 10] [10, 13][15, 20] 仅仅三个区间就得占用到20了。
但是离散化后就可以是[1, 2] [2, 3] [4, 5] n到1e4 不重叠的话最大也只到2e4
那么就可以做了
离散化技巧需要好好消化
代码如下
#include <cstring>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define lp p<<1
#define rp p<<1|1
using namespace std;
const int N = +;
int tree[N<<];
int a[N], ans;
bool vis[N];
pair<int,int> p[N]; inline void pushdown(int p) {
if (tree[p]) {
tree[lp] = tree[rp] = tree[p];
tree[p] = ;
}
}
void build(int p, int l, int r) {
if (tree[p]) {
if (!vis[tree[p]]) {
vis[tree[p]] = ;
ans++;
}
return;
}
int mid = l + r >> ;
build(lp, l, mid);
build(rp, mid + , r);
}
void change(int p, int l, int r, int x, int y, int z) {
if (x <= l && y >= r) {
tree[p] = z;
return;
}
pushdown(p);
int mid = l + r >> ;
if (x <= mid) change(lp, l, mid, x, y, z);
if (y > mid) change(rp, mid + , r, x, y, z);
}
int main()
{
int T; scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
for (int i = ; i <= * n; i++) {
scanf("%d", &p[i].first);
p[i].second = i;
}
sort(p + , p + * n + );
int last = , cnt = ;
for (int i = ; i <= * n; i++) {
if (p[i].first == last) {
a[p[i].second] = cnt;
} else {
a[p[i].second] = ++cnt, last = p[i].first;
}
}
memset(tree, , sizeof(tree));
for (int i = ; i <= * n; i += ) {
change(, , cnt, a[i], a[i+], (i + ) / );
}
memset(vis, , sizeof(vis));
ans = ;
build(, , cnt);
printf("%d\n", ans);
}
return ;
}