【问题描述】
给出一个随机的排列，请你计算最大值减最小值的差小于等于0~n-1的区间分别有多少个。
输入格式
输入文件名为sum.in。
第一行一个数T(<=10)，表示数据组数
对于每一组数据：
第一行一个数n（1<=n<=100,000）
第二行n个数a1...an，表示一个随机的排列
【输出】
输出文件名为sum.out。
对于每组数据输出n行，分别表示差值小于等于0~n-1的区间个数
【输入输出样例】
| sum.in | sum.out |
| 1 4 3 2 4 1 | 4 5 7 10 |
【数据说明】
对于30%的数据，1<=n<=300；
对于60%的数据，1<=n<=5000
对于100%的数据，1<=n<=100000
分析：考虑暴力，O(n^2)枚举区间，O(n)求最值，可以过30分.
如何把n^3优化到n^2？我们可以在找最值的时候优化一下，我们并不一定非要在固定了区间后再去找最值然后更新当前区间，而是我们先固定左端点，然后从左往右扩展去找最值，用最值更新区间信息.
比如，我们已经求得当前区间的最小值minx和最大值maxx,向右扩展一位得到新的minx和maxx,那么ans[maxx - minx]++.当然，我们也可以用ST表O(1)维护最值，复杂度也是O(n^2)的.
题目数据范围很明显提示复杂度要O(nlogn),考虑怎么优化60分的算法.我们向右跳并不需要每次只跳一位，因为可能有很多位置不会更新minx和maxx,我们需要找到下一位能更新minx和maxx的位置，利用单调栈来记录.维护一个单调上升的单调栈和一个单调下降的.因为这是一个随机的排列，所以差不多会跳logn次.
#include#include #include #include using namespace std;int T,n,a[100010],nextmin[100010],nextmax[100010],head,pos[100010],p[100010],minx,maxx;long long ans[100010];int main(){ scanf("%d", &T); while (T--) { memset(ans, 0, sizeof(ans)); memset(a, 0, sizeof(a)); scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) nextmin[i] = nextmax[i] = n + 1; head = 0; memset(p, 0, sizeof(p)); for (int i = 1; i <= n; i++) { while (head > 0 && a[i] < p[head]) { nextmin[a[pos[head]]] = i; head--; } p[++head] = a[i]; pos[head] = i; } memset(pos, 0, sizeof(pos)); head = 0; memset(p, 0x3f3f3f, sizeof(p)); for (int i = 1; i <= n; i++) { while (head > 0 && a[i] > p[head]) { nextmax[a[pos[head]]] = i; head--; } p[++head] = a[i]; pos[head] = i; } for (int i = 1; i <= n; i++) { minx = maxx = a[i]; int j = i; while (j <= n) { if (nextmax[maxx] < nextmin[minx]) { ans[maxx - minx] += nextmax[maxx] - j; j = nextmax[maxx]; maxx = a[nextmax[maxx]]; } else { ans[maxx - minx] += nextmin[minx] - j; j = nextmin[minx]; minx = a[nextmin[minx]]; } } } for (int i = 1; i < n; i++) ans[i] += ans[i - 1]; for (int i = 0; i < n; i++) printf("%lld\n", ans[i]); } return 0;}