分析
我们将所有的元素从小到大排一下序，用线段树维护该元素的两边有多少元素比它小
再将所有的元素从大到小排一下序，用线段树维护该元素的两边有多少元素比它大
最后统计答案即可
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
typedef long long ll;
struct asd{
int wz;
ll qz;
}b[maxn];
ll sumlmin[maxn],sumrmin[maxn],sumlmax[maxn],sumrmax[maxn];
bool cmpmin(asd aa,asd bb){
return aa.qz<bb.qz;
}
bool cmpmax(asd aa,asd bb){
return aa.qz>bb.qz;
}
bool cmp(asd aa,asd bb){
return aa.wz<bb.wz;
}
struct trr{
int l,r;
ll mmin,mmax;
}tr[maxn<<2];
void push_up(int da){
tr[da].mmin=tr[da<<1].mmin+tr[da<<1|1].mmin;
tr[da].mmax=tr[da<<1].mmax+tr[da<<1|1].mmax;
}
void build(int da,int l,int r){
tr[da].l=l,tr[da].r=r;
if(l==r){
tr[da].mmin=tr[da].mmax=0;
return;
}
int mids=(l+r)>>1;
build(da<<1,l,mids);
build(da<<1|1,mids+1,r);
push_up(da);
}
void xgmin(int da,int t,ll w){
if(tr[da].l==tr[da].r){
tr[da].mmin+=w;
return;
}
int mids=(tr[da].l+tr[da].r)>>1;
if(t<=mids) xgmin(da<<1,t,w);
else xgmin(da<<1|1,t,w);
push_up(da);
}
void xgmax(int da,int t,ll w){
if(tr[da].l==tr[da].r){
tr[da].mmax+=w;
return;
}
int mids=(tr[da].l+tr[da].r)>>1;
if(t<=mids) xgmax(da<<1,t,w);
else xgmax(da<<1|1,t,w);
push_up(da);
}
ll cxmin(int da,int l,int r){
if(tr[da].l>=l && tr[da].r<=r){
return tr[da].mmin;
}
int mids=(tr[da].l+tr[da].r)>>1;
ll ans=0;
if(l<=mids) ans+=cxmin(da<<1,l,r);
if(r>mids) ans+=cxmin(da<<1|1,l,r);
return ans;
}
ll cxmax(int da,int l,int r){
if(tr[da].l>=l && tr[da].r<=r){
return tr[da].mmax;
}
int mids=(tr[da].l+tr[da].r)>>1;
ll ans=0;
if(l<=mids) ans+=cxmax(da<<1,l,r);
if(r>mids) ans+=cxmax(da<<1|1,l,r);
return ans;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&b[i].qz);
b[i].wz=i;
}
build(1,1,n);
sort(b+1,b+1+n,cmpmin);
for(int i=1;i<=n;i++){
sumlmin[b[i].wz]=cxmin(1,1,b[i].wz);
sumrmin[b[i].wz]=cxmin(1,b[i].wz,n);
xgmin(1,b[i].wz,1);
}
sort(b+1,b+1+n,cmpmax);
for(int i=1;i<=n;i++){
sumlmax[b[i].wz]=cxmax(1,1,b[i].wz);
sumrmax[b[i].wz]=cxmax(1,b[i].wz,n);
xgmax(1,b[i].wz,1);
}
sort(b+1,b+1+n,cmp);
ll ansmin=0,ansmax=0;
for(int i=1;i<=n;i++){
ansmin+=sumlmin[i]*sumrmin[i];
ansmax+=sumlmax[i]*sumrmax[i];
}
printf("%lld %lld\n",ansmax,ansmin);
return 0;
}
D、十字绣
题目描述
分析
