KD-tree

强制在线就不能愉快的做这道题了。

我们用KD-tree维护平面上的点,这样建出来的树高大概是log,复杂度过得去,但是插入过多会使树深很深,这样就能卡死,那么我们每个10000次插入就重构一次。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + ;
int n, root, cnt, m = , d, last;
struct data {
int x, y, mx_x, mn_x, mx_y, mn_y, lc, rc, sum, val;
bool friend operator < (const data &a, const data &b) {
if(d == ) return a.x == b.x ? a.y < b.y : a.x < b.x;
if(d == ) return a.y == b.y ? a.x < b.x : a.y < b.y;
}
bool friend operator == (const data &a, const data &b) {
return a.x == b.x && a.y == b.y;
}
} a[N], b[N];
inline void read(int &x)
{
x = ;
int f = ; char c = getchar();
while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }
while(c >= '' && c <= '') { x = (x << ) + (x << ) + c - ''; c = getchar(); }
x *= f;
}
bool in(int x1, int y1, int x2, int y2, int X1, int Y1, int X2, int Y2)
{
return X1 >= x1 && Y1 >= y1 && x2 >= X2 && y2 >= Y2;
}
bool out(int x1, int y1, int x2, int y2, int X1, int Y1, int X2, int Y2)
{
return x1 > X2 || x2 < X1 || y1 > Y2 || y2 < Y1;
}
void update(int x)
{
a[x].mn_x = min(a[x].x, min(a[a[x].lc].mn_x, a[a[x].rc].mn_x));
a[x].mx_x = max(a[x].x, max(a[a[x].lc].mx_x, a[a[x].rc].mx_x));
a[x].mn_y = min(a[x].y, min(a[a[x].lc].mn_y, a[a[x].rc].mn_y));
a[x].mx_y = max(a[x].y, max(a[a[x].lc].mx_y, a[a[x].rc].mx_y));
a[x].sum = a[x].val + a[a[x].lc].sum + a[a[x].rc].sum;
}
int build(int l, int r, int D)
{
if(l > r) return ;
d = D;
int mid = (l + r) >> ;
nth_element(b + l, b + mid, b + r + );
a[mid] = b[mid];
a[mid].lc = build(l, mid - , D ^ );
a[mid].rc = build(mid + , r, D ^ );
update(mid);
return mid;
}
void insert(int &x, const data &tmp, int D)
{
d = D;
if(!x)
{
x = ++cnt;
a[x].x = a[x].mn_x = a[x].mx_x = tmp.x;
a[x].y = a[x].mn_y = a[x].mx_y = tmp.y;
a[x].sum = a[x].val = tmp.val;
return;
}
if(a[x] == tmp)
{
a[x].val += tmp.val;
a[x].sum += tmp.val;
return;
}
if(tmp < a[x]) insert(a[x].lc, tmp, D ^ );
else insert(a[x].rc, tmp, D ^ );
update(x);
}
int query(int x, int x1, int y1, int x2, int y2)
{
if(!x) return ;
int ret = ;
if(in(x1, y1, x2, y2, a[x].mn_x, a[x].mn_y, a[x].mx_x, a[x].mx_y)) return a[x].sum;
if(out(x1, y1, x2, y2, a[x].mn_x, a[x].mn_y, a[x].mx_x, a[x].mx_y)) return ;
if(in(x1, y1, x2, y2, a[x].x, a[x].y, a[x].x, a[x].y)) ret += a[x].val;
ret += query(a[x].lc, x1, y1, x2, y2) + query(a[x].rc, x1, y1, x2, y2);
return ret;
}
int main()
{
// freopen("bzoj_4066.in", "r", stdin);
// freopen("bzoj_4066.out", "w", stdout);
a[].mn_x = 1e9;
a[].mx_x = -1e9;
a[].mn_y = 1e9;
a[].mx_y = -1e9;
b[].mn_x = 1e9;
b[].mx_x = -1e9;
b[].mn_y = 1e9;
b[].mx_y = -1e9;
read(n);
while()
{
int opt, x1, y1, x2, y2;
data tmp;
read(opt);
if(opt == )
{
read(tmp.x);
read(tmp.y);
read(tmp.val);
tmp.x ^= last;
tmp.y ^= last;
tmp.val ^= last;
insert(root, tmp, );
if(cnt == m)
{
for(int i = ; i <= cnt; ++i) b[i] = a[i];
root = build(, cnt, );
m += ;
}
}
if(opt == )
{
read(x1);
read(y1);
read(x2);
read(y2);
x1 ^= last;
x2 ^= last;
y1 ^= last;
y2 ^= last;
printf("%d\n", last = query(root, x1, y1, x2, y2));
}
if(opt == ) break;
}
// fclose(stdin);
// fclose(stdout);
return ;
}

最新文章

  1. SQL分页查询的几种方式
  2. AE影视后期之跳跃音符制作
  3. python2.x 默认编码问题
  4. NuGet 让你都美好的PM
  5. ZOJ 3644 Kitty&#39;s Game dfs,记忆化搜索,map映射 难度:2
  6. tcp 和 udp 缓冲区的默认大小及设置【转】
  7. ANDROID_MARS学习笔记_S01原始版_005_ProgressBar
  8. Centos6.5 install Python2.7 &amp; django &amp; mysql &amp; apache
  9. NC V6 nchome文件目录及其作用介绍
  10. IO库 8.4
  11. noip推荐系列:遥控车[字符串+高精+二分答案]
  12. 学习python的*args和 **kwargs
  13. C++Builder中MessageBox的基本用法
  14. 杨老师课堂_Java核心技术下之控制台模拟微博用户注册案例
  15. 深入浅出的webpack构建工具---webpack3版本的CommonsChunkPlugin详解(六)
  16. 配置Tomcat监听80端口 配置Tomcat虚拟主机 Tomcat日志
  17. [ios]IOS的AppDelegate方法中的事件触发调用 以及 关闭 ios应用程序
  18. 常见Java工具——jps
  19. mysql获取外键, 根据数据库名和表名获取表所对应的所有外键
  20. # 学号20155308 2006-2007-2 《Java程序设计》第4周学习总结

热门文章

  1. android-BroadcastReceive广播接收器
  2. ubuntu下调试ffmpeg程序出现undefined reference to pthread_once ,undefined reference to uncompress错误
  3. Unity3D游戏开发之简单的碰撞检測
  4. 编码知识 (Unicode、UTF-8、ANSI)
  5. cocos2d0基础篇笔记二
  6. UVA1422-Processor(二分法+优先队列)
  7. codeforces 557 C
  8. vue-导入静态文件
  9. React Native学习(二)之View
  10. Android-通过SlidingMenu高仿微信6.2最新版手势滑动返回(二)