也是比较巧妙的一个转换思想。
我们考虑列式：
\[ \sum_{i = 1}^n \sum_{j = i + 1}^n {a_i + b_i + a_j + b_j \choose a_i + b_i} \]
直接去算或者是按贡献计算都不行，我们考虑转换成这样：
\[ \frac{ \sum_{i = 1}^n \sum_{j = 1}^n {a_i + b_i + a_j + b_j \choose a_i + b_i} – \sum_{i = 1}^n {2(a_i + b_i) \choose a_i + b_i} }{2} \]
前面那个部分我们可以把点\((-a_i, -b_i)\)放在平面上，然后算一个路径计数的 DP 即可（因为平面大小比较小）。前半部分就是所有第三象限的点走到\((x_i, y_i)\)的路径总数，后半部分直接暴力算即可。
好您妈神仙啊。
考虑用 Lucas 把组合数分解：
\[ {n \choose m} = {n / k \choose m / k} {n \mod k \choose m \mod k} \]
后缀自动机是处理字符串信息的有力工具。后缀自动机存储在 Trie 树上，配合 Link 指针就可以被认为是一张 DAG。任意一条从原点出发的路径都可以被认为是这个字符串的一个子串，且在后缀自动机上不会存在重复的子串信息（然而，我们可以进行一些扩展来维护子串位置信息）。
这道题粗看需要 Link Cut Tree，其实不然：如果我们仍然在把节点 \(1\) 作为根节点来处理子树信息、放入线段树，之后的询问我们只需要灵活的分类讨论即可。在实根为 \(root\) 时，\(u, v\) 之间的 \(LCA\) 显然是 \(lca(u, v), lca(root, u), lca(root, v)\) 之间深度最大的那一个。而修改权值和查询权值，只需要讨论两种祖先关系和平行关系即可。
Continue reading →做一个容斥即可，答案等于：
\[ f_0 – f_1 + f_2 – f_3 \]
其中 \(f_i\) 代表环上至少有 \(i\) 对矛盾。计算方式如下：
节点内子树的值都比本身要小（堆的性质），且整个子树在序列上是一段连续的子串。
HDU-1506 单调栈的裸题。
// HDU-1506.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e5 + 200;
struct node
{
int ch[2], idx, fa, val;
void clear() { ch[0] = ch[1] = idx = fa = val = 0; }
} nodes[MAX_N];
int n, stk[MAX_N << 1], top;
ll ans;
int build()
{
for (int i = 1; i <= n; i++)
{
int k = i - 1;
while (nodes[k].val > nodes[i].val)
k = nodes[k].fa;
nodes[i].ch[0] = nodes[k].ch[1];
nodes[k].ch[1] = i;
nodes[i].fa = k, nodes[nodes[i].ch[0]].fa = i;
}
return nodes[0].ch[1];
}
int dfs(int u)
{
if (u == 0)
return 0;
int siz = 1;
for (int bit = 0; bit < 2; bit++)
siz += dfs(nodes[u].ch[bit]);
ans = max(ans, 1LL * siz * nodes[u].val);
return siz;
}
int main()
{
while (scanf("%d", &n) && n != 0)
{
ans = 0;
nodes[0].ch[0] = nodes[0].ch[1] = nodes[0].idx = nodes[0].fa = nodes[0].val = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &nodes[i].val), nodes[i].idx = i, nodes[i].fa = 0;
memset(nodes[i].ch, 0, sizeof(nodes[i].ch));
}
dfs(build());
printf("%lld\n", ans);
}
return 0;
}