算贡献、set、迭代器、二分查找

题意：

https://atcoder.jp/contests/abc140/tasks/abc140_e?lang=en

分析：

首先这种题有一个非常常用的技巧：算贡献
这非常重要！！！！当然，牛客上也有一题位数差并不是算贡献而是二分解决的应当十分注意！！！
在这一题中我也尝试了二分递归但是失败了。我们来看看贡献。
我们尝试算出任意一个数值他的贡献(也就是他被算了多少次)
请看接下来的数组：
[7,*,*,10,*,*,5,*,*,*,6,*,*,11,*,19] *代表比6小的数字
我们要算5的贡献度，即要算5一共被加了多少次！那么我们怎么做？
我么会发现，若果我们想取到5那么我们最终的区间一定要包括10或者6且不能再包括任何其他比5大的数字了！！
这世隔大发现我们以5为中心向两边扩张记录左右分别第一个大于他的数字的索引3与10
再想左右扩张发现左右第二个大于5的数字的索引0和13
那么，5总共出现的次数就为：(3-0)*(13-10) = 9!
我们已经发现规律了，就是我们只需要看他左右第一次大于，和第二次大于就可以了！！
但是倘若我们一个个进行遍历的话就很容易造成O(n^2)的局面
我们可以先按照数值对坐标排次序！！(从大到小)
这样我们从左到右遍历时只需要向他的前面找坐标正好比他小的和正好比它大的就可以了。
这很容易让我们想到在从左向右遍历的时候也维护一个有序的序列，这样寻找正好小于或者说是正好大于只需要进行二分查找就可以了！！！！！！
用set维护，二分查找返回迭代器！！
在刚开始进行一些特判就可以了

代码如下，写的冗长

#include<iostream>
#include<algorithm>
#include<functional>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const int max_n = 1e5 + 100;
pii a[max_n];
int n;
ll ans = 0;

int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 0;i < n;i++) {
        cin >> a[i].first;
        a[i].second = i;
    }sort(a, a + n, greater<pii>());
    set<ll> myset;
    for (int i = 0;i < n;i++) {
        if (myset.empty()) {
            myset.insert(a[i].second);
            continue;
        }
        if (myset.size() == 1) {
            ll x = *myset.begin();
            ll y = a[i].second;
            if (x > y) { x = x ^ y;y = x ^ y;x = x ^ y; }
            ans += (x + 1) * (n - y) * a[i].first;
            myset.insert(a[i].second);
            continue;
        }
        set<ll>::iterator fr = myset.lower_bound(a[i].second);
        if (fr == myset.end()) {
            set<ll>::iterator be = --fr;
            ll right = n;ll x = *be;
            ll left = *(--be);ll y = a[i].second;
            ans += (x - left) * (right - y) * a[i].first;
        }
        else if (fr == myset.begin()) {
            ll left = -1;ll x = a[i].second;
            ll y = *fr;ll right = *(++fr);
            ans += (x - left) * (right - y) * a[i].first;
        }
        else {
            set<ll>::iterator be = --fr;fr++;
            ll behind = *be;ll front = *fr;
            ll left;ll right;
            if (be == myset.begin())left = -1;
            else left = *(--be);
            if (fr == --myset.end())right = n;
            else right = *(++fr);
            ll x = behind;ll y = a[i].second;
            ans += (x - left) * (front - y) * a[i].first;
            x = a[i].second;y = front;
            ans += (x - behind) * (right - y) * a[i].first;
        }myset.insert(a[i].second);
    }cout << ans << endl;
}

这道题有几个注意点：

set<ll>::iterator fr = myset.lower_bound(a[i].second);

重点注意！！！set进行二分查找时只能使用其自带的二分查找！！！！！！！
坑死我了！坑死我了！坑死我了！坑死我了！坑死我了！坑死我了！坑死我了！！！！！！
还有迭代器的操作，这个怨我，没大用过。靠！！！！！！！