BZOJ 1099([POI2007]树Drz-9次线段树&分类讨论+线段树与插入顺序维护2个参数)

时间：2022-10-24 15:50:01

1099: [POI2007]树Drz

Time Limit: 15 Sec   Memory Limit: 162 MB
Submit: 142   Solved: 55
[ Submit][ Status]

Description

CDQZ是一个偏远的小学校，FGD在学校里中了一排树。他却不喜欢这些树的顺序，因为他们高高矮矮显得那么参差不齐。 FGD定义这些树的不整齐程度为相邻两树的高度差的和。设树高分别为h1,h2,h3,…,hn。那么不整齐程度定义为：|h1-h2|+|h2-h3|+……+|hn-1-hn|。不过，重新栽种这些树是一件麻烦的事情，所以FGD最多只想交换其中两个树的位置。现在请你帮助他，他应该怎么交换使得整个一排树的不整齐程度最小。

Input

第一行包含一个整数n(2<=n<= 50000)，接下来第二行包含n个正整数h1,h2,h3,…,hn，分别表示树的高度。（1<=hi<=100000000）

Output

应该包含n行，每行一个整数，第i行表示若交换的其中一棵树编号为i，则能获得的最小不整齐程度为多少。

Sample Input

样例输入1
5
7 4 5 2 5

样例输入2
5
1 2 3 4 5

Sample Output

样例输出1
7
7
8
7
7

样例输出2
4
4
4
4
4

HINT

Source
[ Submit][ Status]



本题是丧心病狂的分类讨论

显然如果考虑换hi时，最优解是与hj换

那么hi有最小，次小，最大（相对i两侧的树）3种情况，hj也有（相对j两侧）

故可分为3*3种情况

线段树的插入顺序维护hj的情况，符合条件扔进线段树中。

至于hi当然直接在线段树上找。

列交换代价差值公式，分别分析9种情况。

特：

注意先把hi，hi左右2侧最大值，左右2侧最小值排序离散化插入树中，因为插入树中时按的是hi的值



#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
#include<vector>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (50000+10)
#define MAXH (100000000+10) 
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a+b)%F;}
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}
typedef long long ll;
int n,pos[MAXN],lpos[MAXN],rpos[MAXN],himinpos[MAXN],himaxpos[MAXN];
ll h[MAXN],himax[MAXN],himin[MAXN],ans[MAXN],v[MAXN];
pair<ll,int> h2[MAXN];
class SegmentTree
{
ll a[MAXN*4],minv[MAXN*4];
int n;
public:
SegmentTree(){MEM(a) MEM(minv) }
SegmentTree(int _n):n(_n){MEM(a) MEM(minv) }
void mem(int _n)
{
n=_n;
MEMI(a) MEMI(minv)
}
int p,v; //set a[p]=v
void set(int p,int v)
{
this->p=p,this->v=v;
_set(1,1,n);
}
void _set(int x,int L,int R)
{
int M=(L+R)>>1;
if (L==R) {a[x]=minv[x]=v;return;}
else
{
if (p<=M) _set(Lson,L,M);
else _set(Rson,M+1,R);
} 
minv[x]=min(minv[Lson],minv[Rson]);
}


int ql,qr;
ll query_min(int ql,int qr)
{
this->ql=ql,this->qr=qr;
if (ql>qr) return INF;
return _query_min(1,1,n); 
}

ll _query_min(int x,int L,int R)
{
if (ql<=L&&R<=qr) return minv[x];
ll ans=INF,M=(L+R)>>1;
if (ql<=M) ans=min(ans,_query_min(Lson,L,M));
if (M< qr) ans=min(ans,_query_min(Rson,M+1,R));
return ans;
}

}S;
int t_n;
ll dis(int i,int j)
{
return abs(h[i]-h[j]);
}
void pre_work()
{
MEM(ans)
// 一个在首尾，另一个在非首尾，不相邻 
Fork(i,3,n-1) 
{
ll tmp=-dis(1,2)+dis(i,2)-v[i]+dis(1,i-1)+dis(1,i+1);
ans[1]=min(ans[1],tmp);
ans[i]=min(ans[i],tmp);
}
Fork(i,2,n-2) 
{
ll tmp=-dis(n,n-1)+dis(i,n-1)-v[i]+dis(n,i-1)+dis(n,i+1);
ans[n]=min(ans[n],tmp);
ans[i]=min(ans[i],tmp);
}
// 无首尾，相邻 
Fork(i,2,n-2)
{
ll tmp=-dis(i,i-1)-dis(i+1,i+2)+dis(i+1,i-1)+dis(i,i+2); 
ans[i]=min(ans[i],tmp);
ans[i+1]=min(ans[i+1],tmp);
}
//一个在首尾，另一个在非首尾，相邻 1и2 or (n-1) иn 
ll tmp=-dis(2,3)+dis(1,3);
ans[1]=min(ans[1],tmp);
ans[2]=min(ans[2],tmp);

tmp=-dis(n-2,n-1)+dis(n-2,n);
ans[n]=min(ans[n],tmp);
ans[n-1]=min(ans[n-1],tmp);

//首尾，不相邻
tmp=-dis(1,2)-dis(n-1,n)+dis(n,2)+dis(1,n-1);
ans[1]=min(ans[1],tmp);
ans[n]=min(ans[n],tmp);
}
struct node
{
int i,flag;
ll a;
node(){}
node(int _i,int _flag,ll _a):i(_i),flag(_flag),a(_a){}
void print(){cout<<i<<':'<<flag<<' '<<a<<endl; 
} 
}a[3*MAXN];
int m;
int cmp1(const void* a,const void *b)// -1,0,1
{
node _a=*(node*)a,_b=*(node*)b;
if (_a.a^_b.a) return _a.a-_b.a;
else return _a.flag-_b.flag;
} 
int cmp2(const void* a,const void *b)// case#1:0,-1  case#3:1,0  
{
node _a=*(node*)a,_b=*(node*)b;
if (_a.a^_b.a) return _a.a-_b.a;
else return _b.flag-_a.flag;

} 
int fee_u[4][4]={{},{0,1,1,-2},{0,-1,1,0},{0,-1,-1,2}};
void fee(int i,int j,int flagj,int flagi,ll &tmp,ll &add)
{
tmp=-v[i]+fee_u[flagj+2][1]*himin[i]+fee_u[flagj+2][2]*himax[i]+fee_u[flagi+2][3]*h[i];
add=-v[j]+fee_u[flagj+2][3]*h[j]+fee_u[flagi+2][1]*himin[j]+fee_u[flagi+2][2]*himax[j];
}
ll fee_tmp(int i,int flagj,int flagi)
{
return -v[i]+fee_u[flagj+2][1]*himin[i]+fee_u[flagj+2][2]*himax[i]+fee_u[flagi+2][3]*h[i];
}
ll fee_add(int j,int flagj,int flagi)
{
return -v[j]+fee_u[flagj+2][3]*h[j]+fee_u[flagi+2][1]*himin[j]+fee_u[flagi+2][2]*himax[j];
}
bool b[MAXN];
void work1(const int flagj) // (-1,flagj)
{
//cout<<"--------------------------\n";
MEM(b)
const int flagi=-1; 
qsort(a+1,m,sizeof(node),cmp2);
S.mem(t_n);

ForD(i,m)
{
node now=a[i];
if (now.flag==-1) 
{
S.set(pos[now.i],fee_add(now.i,flagj,flagi)),b[pos[now.i]]=1;
//cout<<"add:"<<pos[now.i]<<' '<<fee_add(now.i,flagj,flagi)<<endl; 
}
else if (now.flag==0)
{
ll tmp=fee_tmp(now.i,flagj,flagi),add;
bool b1=0,b2=0;ll t1=0,t2=0;
if (b[pos[now.i-1]])
{
b1=1;S.set(pos[now.i-1],INF);
//cout<<"1del:"<<pos[now.i-1]<<endl; 
}
if (b[pos[now.i+1]])
{
b2=1;S.set(pos[now.i+1],INF);
//cout<<"1del:"<<pos[now.i+1]<<endl; 
}
if (flagj==-1) add=S.query_min(1,rpos[himinpos[now.i]]);
else if (flagj==0) add=S.query_min(lpos[himinpos[now.i]],rpos[himaxpos[now.i]]);
else add=S.query_min(lpos[himaxpos[now.i]],t_n);

//cout<<now.i<<' '<<flagj<<' '<<lpos[himaxpos[now.i]]<<' '<<tmp<<' '<<add<<endl; 
ans[now.i]=min(ans[now.i],tmp+add); 
if (b1)
{
S.set(pos[now.i-1],fee_add(now.i-1,flagj,flagi));
//cout<<"1add:"<<pos[now.i-1]<<endl; 
}
if (b2)
{
S.set(pos[now.i+1],fee_add(now.i+1,flagj,flagi));
//cout<<"1add:"<<pos[now.i+1]<<endl; 
}
}
} 
}
void work2(const int flagj) // (0,flagj)
{
//cout<<"--------------------------\n";
MEM(b)
const int flagi=0; 
qsort(a+1,m,sizeof(node),cmp1);
S.mem(t_n);

ForD(i,m)
{
node now=a[i];
if (now.flag==1) 
{
S.set(pos[now.i],fee_add(now.i,flagj,flagi)),b[pos[now.i]]=1;
//cout<<"add:"<<pos[now.i]<<' '<<fee_add(now.i,flagj,flagi)<<endl; 
}
else if (now.flag==-1) 
{
S.set(pos[now.i],INF),b[pos[now.i]]=0;
//cout<<"del:"<<pos[now.i]<<endl; 
}
else if (now.flag==0)
{
ll tmp=fee_tmp(now.i,flagj,flagi),add;
bool b1=0,b2=0;ll t1=0,t2=0;
if (b[pos[now.i-1]])
{
b1=1;S.set(pos[now.i-1],INF);
//cout<<"1del:"<<pos[now.i-1]<<endl; 
}
if (b[pos[now.i+1]])
{
b2=1;S.set(pos[now.i+1],INF);
//cout<<"1del:"<<pos[now.i+1]<<endl; 
}
if (flagj==-1) add=S.query_min(1,rpos[himinpos[now.i]]);
else if (flagj==0) add=S.query_min(lpos[himinpos[now.i]],rpos[himaxpos[now.i]]);
else add=S.query_min(lpos[himaxpos[now.i]],t_n);
//For(pi,n) cout<<S.query_min(pi,pi)<<' ';cout<<" Test"<<endl;
ans[now.i]=min(ans[now.i],tmp+add); 
if (b1)
{
S.set(pos[now.i-1],fee_add(now.i-1,flagj,flagi));
//cout<<"1add:"<<pos[now.i-1]<<endl; 
}
if (b2)
{
S.set(pos[now.i+1],fee_add(now.i+1,flagj,flagi));
//cout<<"1add:"<<pos[now.i+1]<<endl; 
}
}
} 
}
void work3(const int flagj) // (1,flagj)
{
//cout<<"--------------------------\n";
MEM(b)
const int flagi=1; 
qsort(a+1,m,sizeof(node),cmp2);

S.mem(t_n);

Fork(i,2,t_n-1)
S.set(pos[i],fee_add(i,flagj,flagi)),b[pos[i]]=1;
ForD(i,m)
{
node now=a[i];
//now.print(); 
if (now.flag==1) 
{
S.set(pos[now.i],INF),b[pos[now.i]]=0;
//cout<<"del:"<<pos[now.i]<<endl; 
}
else if (now.flag==0)
{
ll tmp=fee_tmp(now.i,flagj,flagi),add;
bool b1=0,b2=0;ll t1=0,t2=0;
if (b[pos[now.i-1]])
{
b1=1;S.set(pos[now.i-1],INF);
//cout<<"1del:"<<pos[now.i-1]<<endl; 
}
if (b[pos[now.i+1]])
{
b2=1;S.set(pos[now.i+1],INF);
 //cout<<"1del:"<<pos[now.i+1]<<endl; 
}
if (flagj==-1) add=S.query_min(1,rpos[himinpos[now.i]]);
else if (flagj==0) add=S.query_min(lpos[himinpos[now.i]],rpos[himaxpos[now.i]]);
else add=S.query_min(lpos[himaxpos[now.i]],t_n);
//For(pi,n) cout<<S.query_min(pi,pi)<<' ';cout<<" Test"<<endl;
//cout<<now.i<<' '<<flagj<<' '<<lpos[himinpos[now.i]]<<' '<<himaxpos[now.i]<<' '<<tmp<<' '<<add<<endl; 

ans[now.i]=min(ans[now.i],tmp+add); 
if (b1)
{
S.set(pos[now.i-1],fee_add(now.i-1,flagj,flagi));
 //cout<<"1add:"<<pos[now.i-1]<<endl; 
}
if (b2)
{
S.set(pos[now.i+1],fee_add(now.i+1,flagj,flagi));
//cout<<"1add:"<<pos[now.i+1]<<endl; 
}
}
} 
}
void solve() //无首尾，不相邻 
{
for(int i=-1;i<=1;i++)
{
work1(i);work2(i);work3(i);
}
}

int main()
{
//freopen("bzoj1099.in","r",stdin);
//freopen("bzoj1099.out","w",stdout);
scanf("%d",&n);
For(i,n) scanf("%lld",&h[i]);
Fork(i,2,n-1) 
{
himax[i]=max(h[i-1],h[i+1]),himin[i]=min(h[i-1],h[i+1]),v[i]=dis(i,i-1)+dis(i,i+1);
if (h[i-1]<h[i+1]) himinpos[i]=i-1,himaxpos[i]=i+1;
else himinpos[i]=i+1,himaxpos[i]=i-1;
}

m=0;
Fork(i,2,n-1)
{
a[++m]=node(i,-1,himin[i]);
a[++m]=node(i,0,h[i]);
a[++m]=node(i,1,himax[i]);
}

//hash table
t_n=n;
For(i,n) h2[i]=make_pair(h[i],i);
sort(h2+1,h2+1+n);
For(i,n) pos[h2[i].second]=i;

//For(i,n) cout<<h2[i].first<<' '<<h2[i].second<<endl;
// 区间框定 
lpos[h2[1].second]=1;
Fork(i,2,t_n)
lpos[h2[i].second]=(h2[i].first==h2[i-1].first)?lpos[h2[i-1].second]:i;


rpos[h2[t_n].second]=t_n;
ForD(i,t_n-1)
rpos[h2[i].second]=(h2[i].first==h2[i+1].first)?rpos[h2[i+1].second]:i;

//For(i,n) cout<<lpos[i]<<' '<<rpos[i]<<' '<<pos[i]<<endl;


ll res=0;
For(i,n-1) res+=dis(i,i+1);
if (n==2) //首尾，相邻 
{
printf("%lld\n%lld\n",res,res);
return 0;
} 

pre_work();
solve();
For(i,n) printf("%lld\n",res+ans[i]);

return 0;
}





标签：

相关文章