路终会有尽头，但视野总能看到更远的地方。

题目大意

数轴上有很多单位线段，一开始时所有单位线段的权值都是1。有两种操作，第一种操作将某一区间内的单位线段权值乘以w，第二种操作将某一区间内的单位线段权值取w次幂。并且你还需要回答一些询问，每个询问需要求出某一区间的单位线段权值之积。由于答案可能很大，你只需要求出答案 mod (10^9+7)的值。

题目大意

平面上有n个点，求出用这些点可以构成的三角形数。

题目分析

显然能够构成三角形需满足三点不共线。
枚举点$i$，枚举尚未枚举过的点$j$，计算出直线$i\rightarrow j$直线的斜率。
用双指针扫描一下跳过斜率相同的，然后计算个数即可。

题目大意

对于给定正整数n，m，我们称正整数c为好的，当且仅当存在非负整数x，y，使得$nx+my=c$。
现在给出多组数据，对于每组数据，给定n，m，q，求[1,q]内有多少个正整数不是好的。
n≤10^5 , m≤10^9 , q≤10^18 , T≤10

题目分析

由题，$nx+my=c$该式完全对称，但是$n$与$m$的范围却不一样，这说明我们需要往$n$的方向考虑。

题目大意

多次询问一个矩阵中点的个数。

题目分析

基本同园丁的烦恼。
因为题目保证了点互不相同，所以排序只需要处理两种情况即可。

题目大意

多次询问一个矩阵中点的个数。

题目分析

这便是一个普通的二维偏序问题。
我们在Mokia处提到过本题解法且升级成了待修改版。
在这里我们再对二维偏序的处理方式进行详细说明。

题目大意

你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：

题目分析

基本同Mokia。
只是没有初始值而已。

题目大意

维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.

题目分析

这道题其实也是三维偏序的变种。
关于三维偏序可以看这两篇文章：传送门1、传送门2。
为什么这道题是三维偏序呢？我们来胡乱分析分析。

题目大意

维护三维偏序，统计有$i$个比当前点大的点有多少个。

三维偏序普适框架

维护三维偏序使用CDQ分治解决。
CDQ分治是什么？请参考这里
在这里我们提出一种不需要在CDQ中排序的方法，普适性强，常数更小。
初学者请先使用排序的方法，更容易理解，再接受本文方法。

题目大意

求出三维偏序的最长序列长度。（偏序指各个维度对应单调）

CDQ分治简介

维护三维偏序，CDQ分治经典应用。
CDQ分治的思想：
我们在网上搜索CDQ分治的学习资料时都大同小异，大概都是说先递归左边，计算左边信息对右边的影响，再递归右边。
实际上这确实是CDQ分治的思想，但是就这么一句话并不能使新学CDQ分治的同学们理解。
在这里我先总结一下CDQ分治解决偏序问题的思路，CDQ分治可以解决很多问题，等我以后整理学习笔记吧。

题目大意

给定一个带权树，树上任意两点间的路径权值$d(x,y)$定义为$x$,$y$这两个点之间路径上的最小值，树上任意一点$x$的权值定义为这个点到树上其他所有点的路径权值和，即$\sum_i(d(x,i)), 1\le i\le n$，现求树上一点，使得这个点的权值最大，输出这个值。

题目分析

考虑每个点显然是不可做的，因此考虑每条边对答案的贡献。
如果一条边是权值最小的，如图：