标签：

「JSOI2014」矩形并

传送门

我们首先考虑怎么算这个期望对照好。

我们不难发明每一个矩形要和 \(n - 1\) 个矩形去交，而总共又有 \(n\) 个矩形，所以我们把矩形两两之间的交全部加起来再除以 \(n(n - 1)\) 就是答案。

至于算矩形之间的交我们可以考虑把每个矩形都视为在这个矩形范畴内区间加上 \(1\) ，那么我们只需要盘问一个矩形内的和 - 该矩形自身的孝敬就可以算出一个矩形与其他矩形的交。

所以此刻相当于我们只需要实现二维的区间加/盘问。

但是数据范畴很大我们不成能用二维树状数组搞 不然这题就被爆艹了 。

所以我们考虑扫描线 + 一维树状数组来搞。

为什么不用线段树？这题线段树会欠好搞，下面会讲到。

我们把纵坐标用树状数组维护起来，横坐标用扫描线取代。

对付每个矩形弄四条扫描线，两条改削两条盘问。

此中一条改削在左界限加，另一条在右界限右边一个位置减。

此中一个盘问在左界限左边一个位置算负的孝敬，另一个在右界限算正的孝敬。

那么有一个问题，，为什么我们要对付左界限左边搞一条扫描线算负孝敬呢？

我们考虑差分时的效果，我们对付一条加的改削扫描线，我们是把这条扫描线以左的一整块矩形区域都加了 \(1\)

那么我们如果在加之前，把一段区间的孝敬减失，实际上是减失了若干个两个差别矩形左界限之间的值，那么我们这时如果在右边碰到一条盘问正孝敬的扫描线，我们会发明这两条扫描线的孝敬一结合恰好就得到了一块矩形交的孝敬，也就是说我们这样算就可以很便利地算矩形之间的交了。那么我们之所以欠好用线段树就是因为我们这若干个两个差别矩形左界限之间的值的个数是 \(O(n)\) 的，所以欠好搞。

具体细节可以手画一下图，那么我们接下来就用二维树状数组的实现技巧来搞。

还有一些小问题：运算过程中可能会爆 long long 所以我们用 long double 来存；然后就是树状数组不能以零为下标，所以我们再输入时把所有矩形的横纵坐标都往各正标的目的平移 \(2\) 个单位。

参考代码：

#include <algorithm> #include <cstdio> #define rg register #define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout) using namespace std; template < class T > inline void read(T& s) { s = 0; int f = 0; char c = getchar(); while ('0' > c || c > '9') f |= c == '-', c = getchar(); while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar(); s = f ? -s : s; } typedef long double LL; const int _ = 2e5 + 5, __ = 2e6 + 5; int n, num = 0; LL ans = 0; struct node { int opt, x, l, r, v; } t[_ << 2]; inline bool cmp(const node& a, const node& b) { return a.x != b.x ? a.x < b.x : (a.opt != b.opt ? a.opt < b.opt : a.v < b.v); } struct BIT { LL tr[__]; inline void update(int x, LL v) { for (rg int i = x; i < __; i += i & -i) tr[i] += v; } inline LL query(int x) { LL res = 0; for (rg int i = x; i >= 1; i -= i & -i) res += tr[i]; return res; } } tr1, tr2, tr3, tr4; inline void Update(int x, int y, int v) { tr1.update(y, v), tr2.update(y, x * v), tr3.update(y, y * v), tr4.update(y, (LL) x * y * v); } inline LL Query(int x, int y) { return tr1.query(y) * (x + 1) * (y + 1) - tr2.query(y) * (y + 1) - tr3.query(y) * (x + 1) + tr4.query(y); } int main() { #ifndef ONLINE_JUDGE file("cpp"); #endif read(n); for (rg int x, y, a, b, i = 1; i <= n; ++i) { read(x), read(y), read(a), read(b); x += 2, y += 2; t[++num] = (node) { 0, x, y, y + b - 1, 1 }; t[++num] = (node) { 0, x + a, y, y + b - 1, -1 }; t[++num] = (node) { 1, x - 1, y, y + b - 1, -1 }; t[++num] = (node) { 1, x + a - 1, y, y + b - 1, 1 }; ans -= 1ll * a * b; } sort(t + 1, t + num + 1, cmp); for (rg int i = 1; i <= num; ++i) { if (t[i].opt == 0) Update(t[i].x, t[i].l, t[i].v), Update(t[i].x, t[i].r + 1, -t[i].v); else ans += t[i].v * (Query(t[i].x, t[i].r) - Query(t[i].x, t[i].l - 1)); } printf("%.9Lf\n", 1.0 * ans / n / (n - 1)); return 0; }

「JSOI2014」矩形并