拼十字
在给出 N 个矩形，其中第 i 个矩形的长度和宽度分别问 li，wi，并且矩形颜色 ci 为红 (0)/黄 (1)/蓝 (2) 中的一种。现在小蓝想知道在这 N 个矩形中有多少对矩形可以 “拼十字”？
两个矩形可以“拼十字”的充要条件是：
注意，矩形长度和宽度属性是固定的，是不可以通过旋转矩形而发生转变的。
输入格式
第一行一个整数 N，表示有 N 个矩形。接下来 N 行，每行输入三个整数 l、w、c 表示一个矩形的长、宽和颜色
输出格式
出一个整数表示答案。由于答案可能会很大，所以你需要将答案对109 + 7 取模之后输出。
样例输入
5
1 10 0
6 6 0
8 6 1
6 10 0
1 2 1
样例输出
2
样例说明
第 3 个矩形可以和第 1 个矩形拼十字，第 3 个矩形也可以和第 4 个矩形拼十字。所以一共有两对矩形可以拼十字，答案为 2。
【评测用例规模与约定】对于 30% 的评测用例：1 ≤ N ≤ 5000。对于 100% 的评测用例：1 ≤ N ≤ 105，1 ≤ l,w ≤ 105，0 ≤ c ≤ 2。
题目最大开到了十的五次方，所以双层for循环判断每两个矩形是否可以拼十字肯定是不可取的！这个时候我们就要去思考怎么去优化暴力的解法！
矩形只有三种颜色，代表我们要建立三颗线段树 f1 ，f2，f3 代表三种颜色！
可以匹配的两个矩形，要保证矩形 1 的长度严格大于矩形 2 的长度并且矩形 1 的宽度严格小于矩形 2的宽度。
那我们安装矩形的长度从小到大排序，如果长度相同，按照宽度从小到大排序！
然后我们遍历存储矩形的数组
AC JAVA 代码如下
import java.util.*; public class Main { static int max=(int)1e5+10; public static void main(String [] args) { Scanner scan = new Scanner(System.in); int n=scan.nextInt(); int []f1=new int [(int)4e5+100]; int []f2=new int [(int)4e5+100]; int []f3=new int [(int)4e5+100]; int [][]f=new int [n][3]; for(int i=0;i<n;i++) { f[i][0]=scan.nextInt(); f[i][1]=scan.nextInt(); f[i][2]=scan.nextInt(); } Arrays.sort(f,(o1,o2)->o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0]); long res=0,mod=(long)1e9+7; for(int i=0;i<n;i++) { if(f[i][2]==0) { res+=calc(1,1,max,f[i][1]+1,max,f2); res%=mod; res+=calc(1,1,max,f[i][1]+1,max,f3); res%=mod; add(1,1,max,f[i][1],1,f1); } else if(f[i][2]==1) { res+=calc(1,1,max,f[i][1]+1,max,f1); res%=mod; res+=calc(1,1,max,f[i][1]+1,max,f3); res%=mod; add(1,1,max,f[i][1],1,f2); } else { res+=calc(1,1,max,f[i][1]+1,max,f1); res%=mod; res+=calc(1,1,max,f[i][1]+1,max,f2); res%=mod; add(1,1,max,f[i][1],1,f3); } } System.out.println(res); } public static long calc(int k, int l, int r, int s, int t,int []f) { if (l == s && r == t) return f[k]; int m = l + r >> 1; if (t <= m) return calc(k + k , l, m, s, t,f); else if (s > m) return calc(k + k + 1, m + 1, r, s, t,f); else return calc(k + k, l, m, s, m,f) + calc(k + k + 1, m + 1, r, m + 1, t,f); } public static void add(int k, int l, int r, int x, int y,int []f) { f[k] += y; if(l==r) return ; int m = l + r >> 1; if (x <= m) add(k + k , l, m, x, y,f); else add(k + k + 1, m + 1, r, x, y,f); } } 原文链接：https://blog.csdn.net/m0_53720063/article/details/137957817?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522171949575216800227424539%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=171949575216800227424539&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~times_rank-28-137957817-null-null.nonecase&utm_term=2024%E9%AB%98%E8%80%83
