给n个数求每个子区间的价值,区间的价值是最大值-最小值
套路题= =,分别算最大值和最小值的贡献,用并查集维护,把相邻点连一条边,然后sort,求最大是按边价值(两个点的最大价值)小的排,求最小是按最大排
类似的题:http://www.cnblogs.com/acjiumeng/p/8320666.html
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-9; const int N=1000000+10,maxn=3000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f; struct edge{ int u,v,ma,mi; }e[N]; int father[N],sz[N],val[N]; int Find(int x) { return father[x]==x?x:father[x]=Find(father[x]); } bool cmp1(edge a,edge b) { return max(val[a.u],val[a.v])<max(val[b.u],val[b.v]); } bool cmp2(edge a,edge b) { return min(val[a.u],val[a.v])>min(val[b.u],val[b.v]); } int main() { int n,cnt=0; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&val[i]); if(i>1) { e[cnt].u=i-1,e[cnt].v=i; cnt++; } father[i]=i,sz[i]=1; } sort(e,e+cnt,cmp1); // for(int i=0;i<cnt;i++) // printf("%d %d ",e[i].u,e[i].v); ll ans=0; for(int i=0;i<cnt;i++) { int x=Find(e[i].u),y=Find(e[i].v); if(x!=y) { ans+=(ll)sz[x]*sz[y]*max(val[e[i].u],val[e[i].v]); father[x]=y,sz[y]+=sz[x]; } } for(int i=1;i<=n;i++)father[i]=i,sz[i]=1; sort(e,e+cnt,cmp2); for(int i=0;i<cnt;i++) { int x=Find(e[i].u),y=Find(e[i].v); if(x!=y) { ans-=(ll)sz[x]*sz[y]*min(val[e[i].u],val[e[i].v]); father[x]=y,sz[y]+=sz[x]; } } printf("%lld ",ans); return 0; } /******************** ********************/