三维数点的CDQ分治板子
2024-10-07 02:07:33
int n, k, tot;
struct _ {int x,r,f;} a[N];
struct __ {
int type;
ll x,y;
bool operator < (const __ & rhs) const {
if (x!=rhs.x) return x<rhs.x;
if (y!=rhs.y) return y<rhs.y;
return type<rhs.type;
}
} e[N];
ll ans, b[N];
int c[N];
inline void add(int x, int v) {
for (; x<=*b; x+=x&-x) c[x]+=v;
}
inline int qry(int x) {
int r = 0;
for (; x; x^=x&-x) r+=c[x];
return r;
}
inline void qry(ll x1, ll y1, ll x2, ll y2) {
e[++tot] = {1,x2,y2};
e[++tot] = {1,x1-1,y1-1};
e[++tot] = {2,x1-1,y2};
e[++tot] = {2,x2,y1-1};
b[++*b]=y2, b[++*b]=y1-1;
}
inline void ins(int x, int y) {
e[++tot] = {0,x,y};
} void merge(int l, int r) {
if (l==r) return;
merge(l,mid),merge(mid+1,r);
int now = l;
REP(i,mid+1,r) {
while (now<=mid&&e[now].x<=e[i].x) {
if (e[now].type==0) add(e[now].y,1);
++now;
}
if (e[i].type==1) ans+=qry(e[i].y);
else if (e[i].type==2) ans-=qry(e[i].y);
}
while (now!=l) {
if (e[--now].type==0) add(e[now].y,-1);
}
inplace_merge(e+l,e+mid+1,e+r+1);
} int main() {
REP(i,1,n) {
// qry();
// ins();
}
sort(b+1,b+1+*b),*b=unique(b+1,b+1+*b)-b-1;
REP(i,1,tot) e[i].y=lower_bound(b+1,b+1+*b,e[i].y)-b;
merge(1,tot);
printf("%lld\n", ans);
}
最新文章
- C#移动跨平台开发(1)环境准备
- struts2回显指定的错误信息
- linux脚本^M: bad interpreter:解决方法
- ZOJ 刷题记录 (。・ω・)ノ゙(Progress:31/50)
- F - The Circumference of the Circle
- laravel artisan 命令工具
- 在Ubuntu16.04.4上安装jdk
- Cannot set the value of read-only property &#39;outputFile&#39; for ApkVariantOutputImpl_Decorated{...
- 在Winform开发框架中使用DevExpress的内置图标资源
- SSH 免密码登陆到多台机器
- BZOJ.2159.Crash的文明世界(斯特林数 树形DP)
- Eclipse中JSP生成的类文件存放在哪
- POJ 2370
- ms-sql 给表列添加注释
- 20165318 《Java程序设计》实验一(Java开发环境的熟悉)实验报告
- 多线程模块:thread
- Rails 5 Test Prescriptions 第9章 Testing-JavaScript: Integration Testing,❌挂一个问题webpacker::helper
- Python请求外部POST请求,常见四种请求体
- HDU1717--小数化分数2
- 170328、Maven+SpringMVC+Dubbo 简单的入门demo配置