C++(g++ 7.5.0) 解法, 执行用时: 1072ms, 内存消耗: 162604K, 提交时间: 2023-05-05 21:43:17

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid ((l+r)>>1)
// #define double long double
#define eps (1e-15)
#define lowbit(i) ((i)&(-i))
const int mod=998244353;
void solve()
{
	int n;cin>>n;
	vector<int> a(n+1),p(n+1);
	vector<vector<int> > inc(n+1),dec(n+1);
	vector<int> ql(n+1),qr(n+1);
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
		p[a[i]]=i;
	}
	set<int> q;
	for(int i=1;i<=n;++i)
	{
		int id=p[i];
		q.insert(id);
		auto it=q.upper_bound(id);
		if(it==q.end()) continue;
		inc[*it].emplace_back(id);
		++it;
		if(it!=q.end()) dec[(*it)-1].emplace_back(id);
	}
	q.clear();
	for(int i=n;i>=1;--i)
	{
		int id=p[i];
		q.insert(-id);
		auto it=q.upper_bound(-id);
		if(it==q.end()) continue;
		qr[id]=-(*it);
		++it;
		if(it!=q.end()) ql[id]=-(*it)+1;
		else ql[id]=1;
	}
	vector<int> tr(n+1);
	auto update=[&](int x,int k) -> void
	{
		for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=k;
	};
	auto query=[&](int y) -> int
	{
		int sum=0;
		for(int i=y;i>=1;i-=lowbit(i)) sum+=tr[i];
		return sum;
	};
	int ans=0;
	for(int i=1;i<=n;++i)
	{
		for(int x:inc[i]) update(x,1);
		if(ql[i]&&qr[i]) ans+=query(qr[i])-query(ql[i]-1);
		for(int x:dec[i]) update(x,-1);
	}
	cout<<ans<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T=1; //cin>>T;
    while(T--) solve();
    // cout<<clock()-st<<'\n';
    return 0;
}
/*
3*5 7*4 11*3 15*2 19*1
\sum (st+4i)(t-i)
\sum (st*t-i*st+4*i*t-4*i*i0)

*/

C++14(g++5.4) 解法, 执行用时: 834ms, 内存消耗: 146684K, 提交时间: 2020-09-05 20:16:14

#include <bits/stdc++.h>
using namespace std;
#define N 1000010
typedef long long ll;
int n,a[N],rev[N],ql[N],qr[N],tree[N];
vector<int> vl[N],vr[N];

void insert(int x,int k)
{
    for(;x<N;x+=(x&(-x))) tree[x]+=k;
}

ll query(int x)
{
    ll res=0;
    for(;x>0;x-=(x&(-x))) res+=tree[x];
    return res;
}

ll query(int l,int r)
{
    return query(r)-query(l-1);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),rev[a[i]]=i;
    set<int> s;
    for(int i=1;i<=n;i++)
    {
        int id=rev[i];
        s.insert(id);
        auto x=s.upper_bound(id);
        if(x==s.end()) continue;
        vl[*x].push_back(id);
        x++;
        if(x!=s.end()) vr[(*x)-1].push_back(id);
    }
    s.clear();
    for(int i=n;i>=1;i--)
    {
        int id=rev[i];
        s.insert(-id);
        auto x=s.upper_bound(-id);
        if(x==s.end()) continue;
        qr[id]-=*x;
        x++;
        if(x!=s.end()) ql[id]-=(*x)-1;
        else ql[id]=1;
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        for(auto j:vl[i]) insert(j,1);
        if(ql[i]&&qr[i]) ans+=query(ql[i],qr[i]);
        for(auto j:vr[i]) insert(j,-1);
    }
    cout<<ans<<endl;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1611ms, 内存消耗: 136836K, 提交时间: 2020-06-28 00:17:11

#include<bits/stdc++.h>
using namespace std;

set<int>T;
set<int>::iterator it;
vector<int>R1[1000005],R2[1000005];
int i,j,n,V[1000005],S[1000005]={0},l[1000005]={0},r[1000005]={0};
int lowbit(int x)
{
	return x&(-x);
}
void update(int i,int x)
{
	while(i<=n)S[i]+=x,i+=lowbit(i);
}
int getsum(int i)
{
	int s=0;
	while(i)s+=S[i],i-=lowbit(i);
	return s;
}
int main()
{
	long long ans=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&j),V[j]=i;
	T.insert(n+1);
	for(i=1;i<=n;i++)
	{
		j=V[i],T.insert(j),it=T.upper_bound(j);
		if(*it==n+1)continue;
		R1[*it].push_back(j),R2[*(++it)-1].push_back(j);
	}
	T.clear(),T.insert(0);
	for(i=n;i>=1;i--)
	{
		j=V[i],T.insert(-j),it=T.upper_bound(-j);
		if(*it==0)continue;
		r[j]=-*it,l[j]=1-*(++it);
	}
	for(i=1;i<=n;i++)
	{
		for(j=0;j<R1[i].size();j++)update(R1[i][j],1);
		if(l[i])ans+=getsum(r[i])-getsum(l[i]-1);
		for(j=0;j<R2[i].size();j++)update(R2[i][j],-1);
	}
	printf("%lld\n",ans);
}