因?yàn)橹挥衧td，沒有自我實(shí)現(xiàn)，所以是無碼專區(qū)

主要是為了訓(xùn)練思維能力

solution才是dls正解，但是因?yàn)橹挥辛什輲拙?#xff0c;所以大部分會(huì)有我自己基于正解上面的算法實(shí)現(xiàn)過程，可能選擇的算法跟std中dls的實(shí)現(xiàn)不太一樣。

std可能也會(huì)帶有博主自己的注釋。

---

problem

平面上有 $n$ 個(gè)點(diǎn)，$(x_i,y_i)$。

$q$ 次詢問，每次給定三個(gè)點(diǎn) $A(x+d,y),B(x,y),C(x,y+d)$。

求有多少個(gè)點(diǎn) $(x_i,y_i)$ 在這個(gè)三角形內(nèi)部或邊界上。

$10s,128MB,all\le 1e6$。

---

my idea

給定的三角新很有特點(diǎn)：是等腰直角三角形且直角邊分別與一條坐標(biāo)軸平行。

并不是任意的一個(gè)三角形。那么這個(gè)三角形最難處理的自然就是斜邊部分，因?yàn)椴慌c坐標(biāo)軸平行。

如果這是個(gè)正方形，就是個(gè)很簡單的二維差分?jǐn)?shù)點(diǎn)問題。

我曾試圖用所有的點(diǎn)減去沒有落在指定區(qū)域的點(diǎn)，但是發(fā)現(xiàn)外圍圖形仍然會(huì)被切割成若干個(gè)矩形和一個(gè)三角形，還是不會(huì)計(jì)算三角形。?

我曾試圖計(jì)算一個(gè)點(diǎn)的位置會(huì)被多少個(gè)三角形覆蓋，對(duì)這些三角形貢獻(xiàn) $1$。但是查詢的三角形壓根不能找到一種范圍限制能夠說明：橫縱坐標(biāo)簡單的加減為某個(gè)范圍時(shí)屬于這個(gè)三角形。?

這兩種思路都卡在了三角形重疊部分，更具體而言是沒有找到要貢獻(xiàn)的點(diǎn)坐標(biāo)的特征性，顯然這應(yīng)該是正解的思路，這導(dǎo)致我們只能嘗試不是正解的想法看能否優(yōu)化跑過。

既然題目給的是平行坐標(biāo)軸的直角三角形，那么這個(gè)直角邊一定是切入點(diǎn)。

三角形不好做，但是四邊形好做。

將三角形劃分成一個(gè)四邊形，和兩個(gè)三角形。

如圖：一個(gè)三角形存在很多種切割方式。

四邊形是很容易計(jì)算的，三角形就遞歸地切割。所以時(shí)間復(fù)雜度是跟這個(gè)三角形切割掛鉤的。

出于平衡左右時(shí)間的思想，我們肯定會(huì)選取“正半分”，使得兩個(gè)三角形“完全一樣”。

【但是如果只計(jì)算整點(diǎn)，“正半分”可能是分?jǐn)?shù)，所以是盡可能地“正半分”，讓兩邊地效率盡可能平衡。】

這種遞歸思想就是——分治。

沒錯(cuò)，我們可以采取分而治之的做法，遞歸求解計(jì)算。

最底層的出口就是直角邊某一條長度為 $1$ 的三角形，統(tǒng)計(jì)另一條邊的貢獻(xiàn)即可。

這樣，劃分最多 $log$ 層。

四邊形的計(jì)算由于 $N\times M$ 根本開不下，無法預(yù)處理然后 $O(1)$ 差分求解。

只能采取數(shù)據(jù)結(jié)構(gòu)計(jì)算。

具體而言：

將 $n$ 個(gè)點(diǎn)按 $x$ 第一關(guān)鍵字，$y$ 第二關(guān)鍵字排序。

需要在劃分的一個(gè)區(qū)間內(nèi)查詢一個(gè)區(qū)間的問題。又是它！——主席樹。

以 $y$ 建立線段樹，第 $i$ 個(gè)版本維護(hù)的是前 $i$ 個(gè)點(diǎn)的主席數(shù)信息，權(quán)值線段樹。

線段樹上節(jié)點(diǎn)維護(hù) $y\in [l,r]$ 的點(diǎn)有多少個(gè)。

$i\to i+1$，單點(diǎn)更新 $y_i$。

查詢 $(x1,y1,x2,y2)$。找到 $x1<x_l$ 的最小 $l$，以及 $xr<x2$ 的最大 $r$。二分查找。

然后就詢問 $l～r$ 版本中 $[y1,y2]$ 內(nèi)點(diǎn)的個(gè)數(shù)。

這樣來看數(shù)據(jù)結(jié)構(gòu)自帶兩個(gè) $log$，外層還有一個(gè)。時(shí)間復(fù)雜度是 $O(nlo{g}^{3}n)$ 的。

只能堪堪通過 $70\%$ 的數(shù)據(jù)點(diǎn) $2\times 10^5$。

【計(jì)算出來大概是 $8e8$ 的，$10s$ 跑 $1e9$，常數(shù)小寫得好看應(yīng)該是能跑過的。】

考慮優(yōu)化，優(yōu)化掉二分查找的 $log$。

最開始排序的 $log$ 省不了。

對(duì)于 $i$，直接二分找 $l,r$ 記錄下來 $L_i,R_i$。

這樣是將里面嵌套的 $log$ 放在了外面。

$O(n{\log }^{3}n)\to O(n{\log }^{2}n+n\log n)$。

就是兩個(gè) $log$ 的了。

算出來 $4e8$，相對(duì)與 $1e9$ 而言應(yīng)該是綽綽有余的，常數(shù)大點(diǎn)應(yīng)該沒關(guān)系。

trick：圖上一條線段分裂，但實(shí)際上計(jì)算的時(shí)候并不重疊。

中間界可以劃給三角形部分，也可以是矩形部分。

但具體實(shí)現(xiàn)會(huì)發(fā)現(xiàn)，將中間界劃分給三角形會(huì)比較好算，因?yàn)槭欠忾]的。

不好說明，給圖直觀感受。

但是也不是說不能寫，應(yīng)該也是能實(shí)現(xiàn)的。

---

solution

直接查詢，就是三維數(shù)點(diǎn)問題。$CDQ$ 分治做 $O(n{\log }^{2}n)$。

又來了，一句話一頁闡釋。

為什么是三維數(shù)點(diǎn)？？怎么數(shù)？？

---

擴(kuò)展：如何用三角形的三個(gè)坐標(biāo)表示三角形中任意一點(diǎn)的坐標(biāo)。

假設(shè)三角形三點(diǎn)分別為 $A(x1,y1),B(x2,y2),C(x3,y3)$，現(xiàn)要表示內(nèi)部點(diǎn) $O(x,y)$。

設(shè)射線 $AO$ 交 $BC$ 與點(diǎn) $D$，$AO=mAD,BD=nBC$。

則 $AO=mAD=m(AB+BD)=mAB+mnBC$。

即：
$$(x?x1,y?y1)=m(x2?x1,y2?y1)+mn(x3?x2,y3?y2)$$

$$=(m(x2?x1)+mn(x3?x2),m(y2?y1)+mn(y3?y2))$$

$$?\{\begin{array}{l}x?x1=m(x2?x1)+mn(x3?x2)?x=x1(1?m)+x2(m?mn)+x3mn\\ y?y1=m(y2?y1)+mn(y3?y2)?y=y1(1?m)+y2(m?mn)+y3mn\end{array}$$

換元表示 $a=1?m,b=m?mn$ ，則
$$\{\begin{array}{l}x=a?x1+b?x2+(1?a?b)x3\\ y=a?y1+b?y2+(1?a?b)y3\end{array}$$

dbq，我確實(shí)沒看懂這個(gè)三維數(shù)點(diǎn)怎么做。

觀察性質(zhì)，三角形區(qū)域 $(x^{\prime },y^{\prime })?(x^{\prime }+d,y^{\prime })?(x^{\prime },y^{\prime }+d)$。
相當(dāng)于總區(qū)域減去 $x<x^{\prime },y<y^{\prime },x+y>x^{\prime }+y^{\prime }+d$ 三個(gè)半平面。
然后補(bǔ)上三個(gè)被減了兩次的區(qū)域。
即 $x<x^{\prime }\wedge y<y^{\prime },x<x^{\prime }\wedge x+y>x^{\prime }+y^{\prime }+d^{\prime },y<y^{\prime }\wedge x+y>x^{\prime }+y^{\prime }+d$。

這三個(gè)部分都是二維數(shù)點(diǎn)，直接做，時(shí)間復(fù)雜度 $O(n\log n)$。

其實(shí)看題解的時(shí)候我并不懂，但是一看代碼就懂了！！

原來是我不會(huì)等腰直角三角形的二維數(shù)點(diǎn)！！其實(shí)很簡單。

---

code

#include <bits/stdc++.h> using namespace std; #define FOR(a,b,c) for (int a=b,_c=c;a<=_c;a++) #define FORD(a,b,c) for (int a=b;a>=c;a--) #define REP(i,a) for(int i=0,_a=(a); i<_a; ++i) #define REPD(i,a) for(int i=(a)-1; i>=0; --i) #define pb push_back #define mp make_pair #define fi first #define se second #define sz(a) int(a.size()) #define reset(a,b) memset(a,b,sizeof(a)) #define oo 1000000007using namespace std;typedef long long ll; typedef pair<int, int> pii;const int maxn = 1000007; const int maxv = 1000007;int n, q, BIT[maxn], ans[maxn]; struct node {int x, y, d, id; } a[maxn * 2];bool cmp1(const node &a, const node &b) {return a.y < b.y || (a.y == b.y && a.id > b.id); }bool cmp2(const node &a, const node &b) {int v1 = a.x + a.y + a.d;int v2 = b.x + b.y + b.d;return v1 < v2 || (v1 == v2 && a.id < b.id); }void update(int p) {for (int i = p; i <= maxv; i += i & (-i))BIT[i]++; }int get(int p) {int ans = 0;p = min(p, maxv);for (int i = p; i; i -= i & (-i))ans += BIT[i];return ans; }int main() {freopen("triangular.in", "r", stdin);freopen("triangular.out", "w", stdout);scanf("%d%d", &n, &q);FOR(i, 1, n) {scanf("%d%d", &a[i].x, &a[i].y);a[i].id = 0;}FOR(i, 1, q) {scanf("%d%d%d", &a[i + n].x, &a[i + n].y, &a[i + n].d);a[i + n].id = i;}sort(a + 1, a + n + q + 1, cmp1);FOR(i, 1, n + q)if (a[i].id)ans[a[i].id] -= get(a[i].x + a[i].d) - get(a[i].x - 1);elseupdate(a[i].x);sort(a + 1, a + n + q + 1, cmp2);reset(BIT, 0);FOR(i, 1, n + q)if (a[i].id)ans[a[i].id] += get(a[i].x + a[i].d) - get(a[i].x - 1);elseupdate(a[i].x);FOR(i, 1, q) printf("%d\n", ans[i]);return 0; }

總結(jié)

這道題大概斷斷續(xù)續(xù)想了兩天（每天 $40min$ 左右）吧，當(dāng)我突然意識(shí)到分拆遞歸處理的時(shí)候，后面的進(jìn)展就比較快了。

其實(shí)std的做法是很有局限性的，必須充分利用等腰直角，直角邊平行于坐標(biāo)軸三個(gè)條件，但也是挺妙的。

但是我的想法是可以扔掉等腰這個(gè)條件的，只需要直角三角形，直角邊平行于坐標(biāo)軸就可以了，但是多了個(gè) $log$。

當(dāng)然這也是我的想法，我也不知道是否正確，歡迎友好討論以及分享不同思路。

總結(jié)

以上是生活随笔為你收集整理的【无码专区8】三角形二维数点——计数有多少个给定点落在三角形区域内的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。