DynamicSegmentTree
2024-10-14 23:14:22
最近尝试了一下动态开点线段树，英文直译就是Dynamic Open Point Segment Tree，太SB了。
就跟之前的主席树写法差不多。
if(!x || x == y) {
x = ++tot;
}
主席树
if(!o) {
o = ++tot;
}
动态开点线段树
实际上当普通线段树用就行了......
例题：洛谷P1908 逆序对
我们可以不离散化，使用动态开点，直接在1e9上开值域线段树。吸氧后堪堪A掉。
// luogu-judger-enable-o2
#include <cstdio> typedef long long LL;
const int N = ; int sum[N * ], tot, ls[N * ], rs[N * ], a[N], root; void add(int L, int R, int l, int r, int &o) {
if(!o) {
o = ++tot;
}
if(L <= l && r <= R) {
sum[o]++;
return;
}
int mid = (l + r) >> ;
if(L <= mid) {
add(L, R, l, mid, ls[o]);
}
if(mid < R) {
add(L, R, mid + , r, rs[o]);
}
sum[o] = sum[ls[o]] + sum[rs[o]];
return;
} int ask(int L, int R, int l, int r, int o) {
if(!o) {
return ;
}
if(L <= l && r <= R) {
return sum[o];
}
int mid = (l + r) >> ;
int ans = ;
if(L <= mid) {
ans += ask(L, R, l, mid, ls[o]);
}
if(mid < R) {
ans += ask(L, R, mid + , r, rs[o]);
}
return ans;
} int main() {
//printf("%d", sizeof(sum) / 1024 / 1024 * 3);
int n, m = 1e9; scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
} LL ans = ;
for(int i = ; i <= n; i++) {
ans += ask(a[i] + , m, , m, );
add(a[i], a[i], , m, root);
}
printf("%lld", ans);
return ;
}
AC代码
例题：洛谷P2471 降雨量
这个题的难点TM在于分类讨论......大毒瘤。
对于未知的位置，我们用一个bool数组维护就行了。
询问的时候查x，y，(x,y)三段，然后暴力讨论.....
#include <cstdio>
#include <algorithm> const int N = , E = 1e9 + ; int root, large[N * ], tot, ls[N * ], rs[N * ];
bool maybe, sure[N * ]; void change(int p, int v, int l, int r, int &o) {
//printf("change : %d %d %d %d \n", p, v, l, r);
//getchar();
if(!o) {
o = ++tot;
}
if(l == r) {
large[o] = v;
sure[o] = ;
return;
}
int mid = l + (r - l) / ;
if(p <= mid) {
change(p, v, l, mid, ls[o]);
}
else {
change(p, v, mid + , r, rs[o]);
}
large[o] = std::max(large[ls[o]], large[rs[o]]);
sure[o] = sure[ls[o]] & sure[rs[o]];
return;
} int ask(int L, int R, int l, int r, int o) {
//printf("%d %d %d %d \n", L, R, l, r);
if(!o) {
maybe = ;
return ;
}
if(L <= l && r <= R) {
if(!sure[o]) {
maybe = ;
}
return large[o];
}
int mid = l + (r - l) / ;
int ans = ;
if(L <= mid) {
ans = std::max(ans, ask(L, R, l, mid, ls[o]));
}
if(mid < R) {
ans = std::max(ans, ask(L, R, mid + , r, rs[o]));
}
return ans;
} int main() {
int n, limit = E << , x, y;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d%d", &x, &y);
change(x + E, y, , limit, root);
}
scanf("%d", &n);
while(n--) {
scanf("%d%d", &y, &x);
if(y == x) {
printf("true\n");
continue;
}
int c = ask(y + E, y + E, , limit, root);
int cc = maybe;
maybe = ;
int d = ask(x + E, x + E, , limit, root);
int dd = maybe;
maybe = ;
//printf("%d %d %d %d \n", c, cc, d, dd); false -> maybe
if(y + == x) {
if(cc || dd){
printf("maybe\n");
}
else {
if(c >= d) {
printf("true\n");
}
else {
printf("false\n");
}
}
continue;
}
int e = ask(y + + E, x - + E, , limit, root);
int ee = maybe;
maybe = ;
//printf("%d %d \n", e, ee);
if(dd) {
if(cc) {
printf("maybe\n");
}
else {
if(e >= c) {
printf("false\n");
}
else {
printf("maybe\n");
}
}
continue;
}
if(cc) {
if(e >= d) {
printf("false\n");
}
else {
printf("maybe\n");
}
continue;
}
if(ee) {
if(e >= d || c < d) {
printf("false\n");
}
else {
printf("maybe\n");
}
continue;
}
if(e >= d || c < d) {
printf("false\n");
}
else {
printf("true\n");
}
} return ;
}
AC代码
最新文章
- （转）gulp使用
- ThinkPHP登录功能代码
- jQuery源码分析之=>jQuery的定义
- ADO.NET完整增删改
- 尝试使用word发布博客
- Four Operations---hdu5938（暴力）
- web 页面内容优化管理与性能技巧
- 小小的封装了一个pie的echarts
- MongoDB Connector for Hadoop
- C++标准库类型vector及迭代器iterator简介
- 它们的定义PropertyPlaceHolder无法完成更换任务
- 再说php依赖注入
- mosquitto验证client互相踢
- Python中编码的详细讲解
- poj2182（线段树求序列第k小）
- day04-Servlet介绍(1)
- laravel 数据验证
- HDU 4509 湫湫系列故事——减肥记II (简单模拟）
- 【模块化】 RequireJS入门教程总结与推荐
- Integer源码分析