2024年蓝桥杯JavaB组拼十字（压轴题）线段树解法

拼十字

在给出 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 代码如下

<span class="token keyword">import</span> <span class="token import"><span class="token namespace">java<span class="token punctuation">.</span>util<span class="token punctuation">.</span></span><span class="token operator">*</span></span><span class="token punctuation">;</span> <span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">Main</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">static</span> <span class="token keyword">int</span> max<span class="token operator">=</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span><span class="token number">1e5</span><span class="token operator">+</span><span class="token number">10</span><span class="token punctuation">;</span> <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span> <span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token class-name">Scanner</span> scan <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Scanner</span><span class="token punctuation">(</span><span class="token class-name">System</span><span class="token punctuation">.</span>in<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">int</span> n<span class="token operator">=</span>scan<span class="token punctuation">.</span><span class="token function">nextInt</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>f1<span class="token operator">=</span><span class="token keyword">new</span> <span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span><span class="token number">4e5</span><span class="token operator">+</span><span class="token number">100</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>f2<span class="token operator">=</span><span class="token keyword">new</span> <span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span><span class="token number">4e5</span><span class="token operator">+</span><span class="token number">100</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>f3<span class="token operator">=</span><span class="token keyword">new</span> <span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span><span class="token number">4e5</span><span class="token operator">+</span><span class="token number">100</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span>f<span class="token operator">=</span><span class="token keyword">new</span> <span class="token keyword">int</span> <span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator"><</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">=</span>scan<span class="token punctuation">.</span><span class="token function">nextInt</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">=</span>scan<span class="token punctuation">.</span><span class="token function">nextInt</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token operator">=</span>scan<span class="token punctuation">.</span><span class="token function">nextInt</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token class-name">Arrays</span><span class="token punctuation">.</span><span class="token function">sort</span><span class="token punctuation">(</span>f<span class="token punctuation">,</span><span class="token punctuation">(</span>o1<span class="token punctuation">,</span>o2<span class="token punctuation">)</span><span class="token operator">-></span>o1<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">==</span>o2<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">?</span>o1<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">-</span>o2<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">:</span>o1<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">-</span>o2<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">long</span> res<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>mod<span class="token operator">=</span><span class="token punctuation">(</span><span class="token keyword">long</span><span class="token punctuation">)</span><span class="token number">1e9</span><span class="token operator">+</span><span class="token number">7</span><span class="token punctuation">;</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator"><</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">if</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> res<span class="token operator">+=</span><span class="token function">calc</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f2<span class="token punctuation">)</span><span class="token punctuation">;</span> res<span class="token operator">%=</span>mod<span class="token punctuation">;</span> res<span class="token operator">+=</span><span class="token function">calc</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f3<span class="token punctuation">)</span><span class="token punctuation">;</span> res<span class="token operator">%=</span>mod<span class="token punctuation">;</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>f1<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token operator">==</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> res<span class="token operator">+=</span><span class="token function">calc</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f1<span class="token punctuation">)</span><span class="token punctuation">;</span> res<span class="token operator">%=</span>mod<span class="token punctuation">;</span> res<span class="token operator">+=</span><span class="token function">calc</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f3<span class="token punctuation">)</span><span class="token punctuation">;</span> res<span class="token operator">%=</span>mod<span class="token punctuation">;</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>f2<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{<!-- --></span> res<span class="token operator">+=</span><span class="token function">calc</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f1<span class="token punctuation">)</span><span class="token punctuation">;</span> res<span class="token operator">%=</span>mod<span class="token punctuation">;</span> res<span class="token operator">+=</span><span class="token function">calc</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f2<span class="token punctuation">)</span><span class="token punctuation">;</span> res<span class="token operator">%=</span>mod<span class="token punctuation">;</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>f3<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>res<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">long</span> <span class="token function">calc</span><span class="token punctuation">(</span><span class="token keyword">int</span> k<span class="token punctuation">,</span> <span class="token keyword">int</span> l<span class="token punctuation">,</span> <span class="token keyword">int</span> r<span class="token punctuation">,</span> <span class="token keyword">int</span> s<span class="token punctuation">,</span> <span class="token keyword">int</span> t<span class="token punctuation">,</span><span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>f<span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">if</span> <span class="token punctuation">(</span>l <span class="token operator">==</span> s <span class="token operator">&&</span> r <span class="token operator">==</span> t<span class="token punctuation">)</span> <span class="token keyword">return</span> f<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">int</span> m <span class="token operator">=</span> l <span class="token operator">+</span> r <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>t <span class="token operator"><=</span> m<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token function">calc</span><span class="token punctuation">(</span>k <span class="token operator">+</span> k <span class="token punctuation">,</span> l<span class="token punctuation">,</span> m<span class="token punctuation">,</span> s<span class="token punctuation">,</span> t<span class="token punctuation">,</span>f<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>s <span class="token operator">></span> m<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token function">calc</span><span class="token punctuation">(</span>k <span class="token operator">+</span> k <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> m <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> r<span class="token punctuation">,</span> s<span class="token punctuation">,</span> t<span class="token punctuation">,</span>f<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">else</span> <span class="token keyword">return</span> <span class="token function">calc</span><span class="token punctuation">(</span>k <span class="token operator">+</span> k<span class="token punctuation">,</span> l<span class="token punctuation">,</span> m<span class="token punctuation">,</span> s<span class="token punctuation">,</span> m<span class="token punctuation">,</span>f<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">calc</span><span class="token punctuation">(</span>k <span class="token operator">+</span> k <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> m <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> r<span class="token punctuation">,</span> m <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> t<span class="token punctuation">,</span>f<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token keyword">int</span> k<span class="token punctuation">,</span> <span class="token keyword">int</span> l<span class="token punctuation">,</span> <span class="token keyword">int</span> r<span class="token punctuation">,</span> <span class="token keyword">int</span> x<span class="token punctuation">,</span> <span class="token keyword">int</span> y<span class="token punctuation">,</span><span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>f<span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> f<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">+=</span> y<span class="token punctuation">;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>l<span class="token operator">==</span>r<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token punctuation">;</span> <span class="token keyword">int</span> m <span class="token operator">=</span> l <span class="token operator">+</span> r <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>x <span class="token operator"><=</span> m<span class="token punctuation">)</span> <span class="token function">add</span><span class="token punctuation">(</span>k <span class="token operator">+</span> k <span class="token punctuation">,</span> l<span class="token punctuation">,</span> m<span class="token punctuation">,</span> x<span class="token punctuation">,</span> y<span class="token punctuation">,</span>f<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">else</span> <span class="token function">add</span><span class="token punctuation">(</span>k <span class="token operator">+</span> k <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> m <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> r<span class="token punctuation">,</span> x<span class="token punctuation">,</span> y<span class="token punctuation">,</span>f<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> 
<span class="token keyword">import</span> <span class="token import"><span class="token namespace">java<span class="token punctuation">.</span>util<span class="token punctuation">.</span></span><span class="token operator">*</span></span><span class="token punctuation">;</span> <span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">Main</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">static</span> <span class="token keyword">int</span> max<span class="token operator">=</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span><span class="token number">1e5</span><span class="token operator">+</span><span class="token number">10</span><span class="token punctuation">;</span> <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span> <span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token class-name">Scanner</span> scan <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Scanner</span><span class="token punctuation">(</span><span class="token class-name">System</span><span class="token punctuation">.</span>in<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">int</span> n<span class="token operator">=</span>scan<span class="token punctuation">.</span><span class="token function">nextInt</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>f1<span class="token operator">=</span><span class="token keyword">new</span> <span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span><span class="token number">4e5</span><span class="token operator">+</span><span class="token number">100</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>f2<span class="token operator">=</span><span class="token keyword">new</span> <span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span><span class="token number">4e5</span><span class="token operator">+</span><span class="token number">100</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>f3<span class="token operator">=</span><span class="token keyword">new</span> <span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span><span class="token number">4e5</span><span class="token operator">+</span><span class="token number">100</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span>f<span class="token operator">=</span><span class="token keyword">new</span> <span class="token keyword">int</span> <span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator"><</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">=</span>scan<span class="token punctuation">.</span><span class="token function">nextInt</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">=</span>scan<span class="token punctuation">.</span><span class="token function">nextInt</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token operator">=</span>scan<span class="token punctuation">.</span><span class="token function">nextInt</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token class-name">Arrays</span><span class="token punctuation">.</span><span class="token function">sort</span><span class="token punctuation">(</span>f<span class="token punctuation">,</span><span class="token punctuation">(</span>o1<span class="token punctuation">,</span>o2<span class="token punctuation">)</span><span class="token operator">-></span>o1<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">==</span>o2<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">?</span>o1<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">-</span>o2<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">:</span>o1<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">-</span>o2<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">long</span> res<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>mod<span class="token operator">=</span><span class="token punctuation">(</span><span class="token keyword">long</span><span class="token punctuation">)</span><span class="token number">1e9</span><span class="token operator">+</span><span class="token number">7</span><span class="token punctuation">;</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator"><</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">if</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> res<span class="token operator">+=</span><span class="token function">calc</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f2<span class="token punctuation">)</span><span class="token punctuation">;</span> res<span class="token operator">%=</span>mod<span class="token punctuation">;</span> res<span class="token operator">+=</span><span class="token function">calc</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f3<span class="token punctuation">)</span><span class="token punctuation">;</span> res<span class="token operator">%=</span>mod<span class="token punctuation">;</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>f1<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token operator">==</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> res<span class="token operator">+=</span><span class="token function">calc</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f1<span class="token punctuation">)</span><span class="token punctuation">;</span> res<span class="token operator">%=</span>mod<span class="token punctuation">;</span> res<span class="token operator">+=</span><span class="token function">calc</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f3<span class="token punctuation">)</span><span class="token punctuation">;</span> res<span class="token operator">%=</span>mod<span class="token punctuation">;</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>f2<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{<!-- --></span> res<span class="token operator">+=</span><span class="token function">calc</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f1<span class="token punctuation">)</span><span class="token punctuation">;</span> res<span class="token operator">%=</span>mod<span class="token punctuation">;</span> res<span class="token operator">+=</span><span class="token function">calc</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f2<span class="token punctuation">)</span><span class="token punctuation">;</span> res<span class="token operator">%=</span>mod<span class="token punctuation">;</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>f3<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>res<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">long</span> <span class="token function">calc</span><span class="token punctuation">(</span><span class="token keyword">int</span> k<span class="token punctuation">,</span> <span class="token keyword">int</span> l<span class="token punctuation">,</span> <span class="token keyword">int</span> r<span class="token punctuation">,</span> <span class="token keyword">int</span> s<span class="token punctuation">,</span> <span class="token keyword">int</span> t<span class="token punctuation">,</span><span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>f<span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">if</span> <span class="token punctuation">(</span>l <span class="token operator">==</span> s <span class="token operator">&&</span> r <span class="token operator">==</span> t<span class="token punctuation">)</span> <span class="token keyword">return</span> f<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">int</span> m <span class="token operator">=</span> l <span class="token operator">+</span> r <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>t <span class="token operator"><=</span> m<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token function">calc</span><span class="token punctuation">(</span>k <span class="token operator">+</span> k <span class="token punctuation">,</span> l<span class="token punctuation">,</span> m<span class="token punctuation">,</span> s<span class="token punctuation">,</span> t<span class="token punctuation">,</span>f<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>s <span class="token operator">></span> m<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token function">calc</span><span class="token punctuation">(</span>k <span class="token operator">+</span> k <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> m <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> r<span class="token punctuation">,</span> s<span class="token punctuation">,</span> t<span class="token punctuation">,</span>f<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">else</span> <span class="token keyword">return</span> <span class="token function">calc</span><span class="token punctuation">(</span>k <span class="token operator">+</span> k<span class="token punctuation">,</span> l<span class="token punctuation">,</span> m<span class="token punctuation">,</span> s<span class="token punctuation">,</span> m<span class="token punctuation">,</span>f<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">calc</span><span class="token punctuation">(</span>k <span class="token operator">+</span> k <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> m <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> r<span class="token punctuation">,</span> m <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> t<span class="token punctuation">,</span>f<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token keyword">int</span> k<span class="token punctuation">,</span> <span class="token keyword">int</span> l<span class="token punctuation">,</span> <span class="token keyword">int</span> r<span class="token punctuation">,</span> <span class="token keyword">int</span> x<span class="token punctuation">,</span> <span class="token keyword">int</span> y<span class="token punctuation">,</span><span class="token keyword">int</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>f<span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> f<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">+=</span> y<span class="token punctuation">;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>l<span class="token operator">==</span>r<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token punctuation">;</span> <span class="token keyword">int</span> m <span class="token operator">=</span> l <span class="token operator">+</span> r <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>x <span class="token operator"><=</span> m<span class="token punctuation">)</span> <span class="token function">add</span><span class="token punctuation">(</span>k <span class="token operator">+</span> k <span class="token punctuation">,</span> l<span class="token punctuation">,</span> m<span class="token punctuation">,</span> x<span class="token punctuation">,</span> y<span class="token punctuation">,</span>f<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">else</span> <span class="token function">add</span><span class="token punctuation">(</span>k <span class="token operator">+</span> k <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> m <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> r<span class="token punctuation">,</span> x<span class="token punctuation">,</span> y<span class="token punctuation">,</span>f<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> 
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
声明📢本站内容均来自互联网，归原创作者所有，如有侵权必删除。本站文章皆由CC-4.0协议发布，如无来源则为原创，转载请注明出处。
THE END