HDU-6058 Kanade's sum - 2017 Multi-University Training Contest - Team 3(思维+模拟链表)
题意：
给两个数n，k和1..n的某个排列，求∑(n,l=1)∑(n,r=l) f(l,r,k)，其中f(l,r,k)是区间[l,r]第k大的值，如果区间数的个数不足k个，则f(l,r,k)为0。
思路：
由于n比较大而k最大为80，所以对于每个数x，我们只要求出其左边大于x的k个数的位置，和其右边大于x的k个数位置就可以求出所有以x为第k大数的所有区间。然而这样暴力去求肯定不行的，由于是1..n的某个排列，所以每个数只会出现一次且不同。所以我们是通过一个模拟链表去记录每个数位置后面的位置(其实就是为了官方题解说的实现O(1)地找大于当前数的数)，并从1开始去进行上述操作，所以每次操作完便可以将这个数从链表"删除"，因为前面的数不会影响后面的数寻找比它大的嘛。然后再求满足要求的区间就好了。
代码：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 5e5+5;
int t, n, k;
int pos[maxn], pre[maxn], net[maxn];
int zuo[85], you[85];
int main()
{
//freopen("in.txt", "r", stdin);
scanf("%d", &t);
while(t--)
{
LL ans = 0;
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; ++i)
{
int x;
scanf("%d", &x);
pos[x] = i;
pre[i] = i-1; net[i] = i+1;
}
for(int x = 1; x <= n; ++x)
{
int i1, i2, j1, j2;
i1 = i2 = pos[x];
j1 = 0, j2 = 0;
zuo[0] = you[0] = pos[x];
while(i1 != 0 && j1 < k)
{
zuo[++j1] = pre[i1];
i1 = pre[i1];
}
while(i2 != n+1 && j2 < k)
{
you[++j2] = net[i2];
i2 = net[i2];
}
int i = 0;
while(i < j1)
{
int j = k-1-i;
if(j < j2) ans += 1ll*x*(zuo[i]-pre[zuo[i]])*(net[you[j]]-you[j]);
++i;
}
net[pre[pos[x]]] = net[pos[x]];
pre[net[pos[x]]] = pre[pos[x]];
}
printf("%lld\n", ans);
}
return 0;
}继续加油～