题目链接:https://codeforces.com/problemset/problem/1849/E
大致题意:
长度为n的序列,求有多少个区间满足区间最大值在区间最小值的右边?
解题思路:
(此题有使用线段树等其他做法,本处使用的是单调栈做法)
我们先求出每个a【i】 的左边的比他小的LMIN,左边比他大的LMAX,右边比他大的RMAX,右边比他小的RMIN;
我们枚举每个a【i】为最大值,此刻以他为最大值的区间为,L= LMAX【i】,R = RMAX【i】;
1:枚举k从 i 到 L+1 :
以k为左端点的时候,比 k 到 i 中的数都 小的 数在 x 的时候,
a: x < i,那么答案增加 i - x
b:x > R时,答案增加R - i
其他时候答案不增加
2:枚举k从i 到R-1;
以k为右端点的时候,比i到k中的数都小的数在x的时候,
如果x大于L,那么答案增加x-L
其他时候答案都不增加
以上结论都是比较显然的,读者可以思考一下就推出;
复杂度的话,我们将俩种情况结合起来,也就是,如果 i - L < R - i,那么使用第一种情况,否则使用第二种情况;
我们思考区间最大值从大到小来看,每个区间扫描都会不大于之前那个区间的一半;
故时间复杂度:O(nlogn);
代码:
#include<bits/stdc++.h> signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int n; std::cin >> n; std::vector<int> a(n + 1, 0); std::vector<int> LMIN(n + 1, 0), LMAX(n + 1, 0), RMIN(n + 1, n + 1), RMAX(n + 1, n + 1); for (int i = 1; i <= n; ++i)std::cin >> a[i]; std::stack<int> st; for (int i = 1; i <= n; ++i) { while (st.size() && a[st.top()] > a[i])RMIN[st.top()] = i, st.pop(); st.push(i); } while (st.size())st.pop(); for (int i = 1; i <= n; ++i) { while (st.size() && a[st.top()] < a[i])RMAX[st.top()] = i, st.pop(); st.push(i); } while (st.size())st.pop(); for (int i = n; i >= 1; --i) { while (st.size() && a[st.top()] > a[i])LMIN[st.top()] = i, st.pop(); st.push(i); } while (st.size())st.pop(); for (int i = n; i >= 1; -- i) { while (st.size() && a[st.top()] < a[i])LMAX[st.top()] = i, st.pop(); st.push(i); } while (st.size())st.pop(); //for (int i = 1; i <= n; ++i)std::cout << LMIN[i] << " \n"[i == n]; //for (int i = 1; i <= n; ++i)std::cout << LMAX[i] << " \n"[i == n]; //for (int i = 1; i <= n; ++i)std::cout << RMIN[i] << " \n"[i == n]; //for (int i = 1; i <= n; ++i)std::cout << RMAX[i] << " \n"[i == n]; long long ans = 0; for (int i = 1; i <= n; ++i) { int L = LMAX[i], R = RMAX[i]; if (i - L < R - i) { int mi = RMIN[i], I = i; for (int j = i; j > L; --j) { if (a[j] < a[I])I = j; mi = RMIN[I]; if (mi >= R)ans += R - i - (i == j); else if (mi > i)ans += mi - i - (i == j); } } else { int mi = LMIN[i], I = i; for (int j = i; j < R; ++j) { if (a[j] < a[I])I = j; mi = LMIN[I]; if (mi > L)ans += mi - L; //std::cout << mi << " " << L << "\n"; } } //std::cout << ans << "\n"; } std::cout << ans << "\n"; return 0; }
其实说难也不是很难,就是需要考虑的有些细:)
- 数据结构 Educational Codeforces 结构 数据数据结构educational codeforces结构 数据结构codeforces mountain结构 数据结构codeforces结构 数学 数据结构codeforces mountains结构 数据结构codeforces beautiful结构 数据结构codeforces结构 数据 educational codeforces round rated educational codeforces round 151 construction educational codeforces round educational codeforces round 147