首先由题意，我们有一个平行于z轴的棱柱和一个平行于y轴的棱柱。想要通过三维几何运算来获得体积的方式显然是比较困难的。但我们注意到我们已经有的是两个保证底面为凸多边形的棱柱。这样有什么好处？我们考虑找一个垂直于x轴的平面，沿着平面对着这两个棱柱砍一刀会得到什么。
是两个长方形对不对？那么这两个长方形的交是什么？（注意，这时候我们砍的x是一样的）
依然是一个长方形！而且显然在两个棱柱交的地方，对于每一个x砍一刀都有一个长方形。注意题意“两个保证底面为凸多边形的棱柱”，这是导致了当前情况的关键，凸多边形使得不会出现下图的情况：
这样砍出来就不是长方形了，不过题目说了是凸多边形，所以不会出现上述情况。
那么现在我们要使用辛普森积分了。辛普森积分是形如下图的公式：
证明见关于辛普森积分法的研究。作为一个咸鱼选手当然只想知道板子怎么用。首先是辛普森积分在什么条件下使用：当我们的积分函数是二次及以下时，辛普森积分能够保证较高的精度。接下来是实际的使用：本题中我们首先将第一个多边形的x和第二个多边形的x全部取出存入一个vector，为什么要这么做？因为在这些x两两之间最后交出来的长方形的边长都是同一线性变化的，或者你看图，理解为我们切割时碰到了x的段点，这个时候长方形之后的边长虽然还是线性变化，却已经不是之前的变化函数了所以需要重新计算。而对于边长同一线性变化的区间，或者说两个相邻的x，我们就能使用辛普森积分进行计算。辛普森积分需要的是左端点(x1),右端点(x2),左端点函数值(fa,即在x1点我们切割两个棱柱得到的长度相乘。我们直接枚举棱柱的边求交，然后找y最大值-y最小值就是长度(z同理)，表现为代码中的width)，右段点（同理），中点（同理），有了这些函数值后我们就能获得面积沿x的积分，也就是这段的体积，最后我们逐段体积相加即可。
对于该题，我们建立如下图所示坐标系，横坐标为风速，纵坐标为在该风速下飞机到达0点的时间。那么显然在两条直线有交点的时候表示两架飞机同时到达0点。
虽然知道了这点，但我们不能O(n^2)求直线交，该题期望的是O(nlogn)的解法。在看了杜老师(%%%)的代码后我学到了一种新的姿势：已知多条直线在两个坐标x1,x2(这道题是-w，w)的情况下，我们可以使用树状数组求逆序对的方式来计算直线的交点数量。以本题为例：我们首先定义一个结构体，储存x(坐标的绝对值),v’(考虑风速后的速度),e(通过该值在左端点一样的情况下能够比较右端点),id。我们将-w各个点的值保存在一个vector up中，w保存在另一个vector down中，然后对两个数组根据到零点时间从小到大排序。对每个点我们利用id记录up（左端点）的左边排名，然后对右端点从上往下计算，每次我们查看在该点左端点之前排名的（也就右端点在它上面，左端点在它下面的直线）有几条，利用树状数组来维护这个值即可，最后的和就是我们需要的答案。
基础树形dp，但看了题解才做出来。。
树形dp有两种基本形式：从根到叶子，从叶子到根。本题稍微有点特别，需要进行两次dfs才能完成整个dp。
我们定义一个dp数组dp[MAXN][3]。dp[i][0]记录的是节点i子树中所有节点到子树根节点i的最大距离，dp[i][1]记录的是节点i往根方向的最大距离，dp[i][2]记录的是节点i子树中所有点的到子树根节点i的次大距离。为什么要这样设计dp状态？如果我们将i节点设为根节点，我们能发现原来父亲节点也变成了一棵子树。但我们不能对每个节点都dfs一次，所以我们考虑使用一个dp[i][1]从顶向下来计算父亲节点这棵子树的距离最大值，dp[i][0],dp[i][2]的作用在后文中会写到。
对于dp[i][0]，dp[i][2]我们在第一次dfs中就计算出来，注意我们要记录一个一个点最长距离走的是哪个儿子longest[i],这个值在后面会用到。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17int dfs1(int u,int fa){
dp[u][0]=0;
for(int i=head[u];~i;i=nxt[i]){
int go=to[i];
if(go==fa)continue;
int temp=dfs1(go,u)+len[i];
if(temp>dp[u][0]){
dp[u][2]=dp[u][0];
dp[u][0]=temp;
islongest[u]=go;
}
else if(temp>dp[u][1]){
dp[u][1]=temp;
}
}
return dp[u][0];
}
在第二次dfs中我们计算dp[i][1]。我们在父亲节点时计算儿子节点的dp[son][1]而不是dfs进入儿子后计算。然后分类讨论
最后遍历所有节点取max(dp[i][0],dp[i][1])即可
题意是给定一个匹配好的括号序列，后面有Q次操作，每次操作将第q位的括号反转，你需要找到一个位置反转该位置上的括号让它重新匹配。位置要求是所有可行位置中最左边的。
我们令左括号为1，右括号为-1，并求出前缀和。考虑将右括号变为左括号的过程，我们能发现该操作的影响是从该位置到序列尾部的前缀和加2。将左括号变为右括号则是区间-2。为了反转后的括号序列是合法的，我们的前缀和中不能出现小于0的数。因而对操作是右括号变为左括号的情况我们可以将问题转化为哪个位置到末尾的最小值是2，以上所有操作可以使用二分+区间更新线段树实现。而对于左括号变为右括号的操作，我们只要维护一个set保存右括号的下标，然后取出最小的下标即可（很简单的思路，简单画一画就能发现）。