巧克力王国

link

这个题目让我想起了李玉辉。

当异域的风唤醒南国的雨
那天宝的尘埃
醉了尘封多年的往事
你生拽着轮回几世的姊妹
千里迢迢亮了皇城
华清池畔的你
多了几分神的气质
1502年的盛夏
一个叫做哥伦布的浑身嵌着蓝宝石的家伙
虔诚地将你敬献
国王瞬间化作斗牛士
他双手托起王冠
想亲手为你加冕
从此，国王庄严地向全世界宣告
你的前世是荔枝
你的今生叫巧克力。
by 21世纪最伟大的教育家、文学家&哲学家♂ 木子

可以认为是K-D树模板题。当然这只是不带修改的K-D树，带修的以后写了再说。

作为一篇学习笔记，先介绍一下什么是K-D树。要明白一点，即K是一个变量，用来指代此数据结构处理和维护的空间维数，比如要维护平面上的点或者二元组集合那么就应该叫做2-D树（不然真的以为是kbd卡丹树吗，那样叫实在有点不雅）。接下来说一下它的思想。它的本质就是对于一个Nk维空间进行分治维护，相当于改良优化后的k维树状数组（当然它们有很多地方是不一样的）。哪e2-D树来说，它考虑的是把平面分割成一个个矩形，每个节点对应一个矩形，随着树的递归建造矩形被越分越小最后成为一个单点。由于每个节点是一个矩形，那么就可以考虑把这个矩形当成一个整体进行询问和修改，具体方式看题。最后，如果带插入的话可能会导致树的结构失衡，此时就需要使用替罪羊一样的方式进行拍扁重建，当然那都是后话了。

考虑到这道题，本质上它就是要询问满足\(ax+by的点\((x,y)\)的个数。很显然前面的表达式相当于一个半平面，而一个矩形只有三种情况，全不在半平面中全在以及一部分在。前两种情况可以直接看成一个整体累加答案，后面那种情况递归处理就可以了。复杂度……应该是\(O(NlogN)\)吧，毕竟它有分治在里面的嘛。

code：

#include
#include
//#define zczc
#define ll long long
using namespace std;
const int N=50010;
const int maxn=1e9;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
    wh*=f;return;
}
inline int min(int s1,int s2){return s1r)return 0;int wh=++cnt,mid=l+r>>1;kkk=k;
	nth_element(a+l,a+mid,a+r+1,cmp);t[wh]=a[mid];
	lc=build(l,mid-1,!k),rc=build(mid+1,r,!k);
	return pushup(wh),wh;
}
ll ans;int aa,b,c;
inline bool in(int x,int y){return 1ll*aa*x+1ll*b*y