正題

P5044

---

題目大意

給出一個序列a，設 $dist(x,y)={\max }_{i=x}^y{a}_i$，有m個詢問，對于每個詢問，給出 l,r，讓你找一個點x$(l\le x\le r)$，使得 ${\sum }_{i=l}^{r}dist(i,x)$ 最小

---

解題思路

設 $f_{i,j}$ 為區間 [l,r] 的答案，那么得到區間最大值x后，可以按如下轉移

$$f_{l,r}=\min (f_{l,x?1}+a_x\times (r?x+1),f_{x+1,r}+a_x\times (x?l+1))$$

考慮如何優化

考慮對該數列建立笛卡爾樹

對于一個查詢 [l,r] ，求出最大點x，那么可以把當前詢問拆成 [l,x-1] 和 [x+1,r]

那么對于笛卡爾樹上的一個點x（子樹范圍為 [l,r]），只需維護 [l,x-1],[l+1,x-1]…[x-1,x-1] 和 [x+1,r],[x+1,r-1]…[x+1,x+1] 這些狀態

那么可以用兩個線段樹，分別維護遍歷到當前點時每個點到子樹最左/右端的答案

對于左子樹的點，考慮從左子樹選還是從右子樹選，可以把右子樹選的貢獻差分一下，然后線段樹上二分找分界點修改決策（即哪些點選左子樹，哪些點選右子樹，單調性易證），右子樹同理

遍歷完笛卡爾樹中左右子樹后，計算最大點為當前點的詢問，記下答案后再往回走

時間復雜度 $O((n+q)logn)$

---

code

#include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 750100 #define mp make_pair #define fs first #define sn second using namespace std; ll n,t,l,r,lg[N],h[N],f[N][25],ans[N]; vector<pair<pair<ll,ll>,ll> >q[N]; struct Tree {#define ls x*2#define rs x*2+1ll lazy[N<<2],b[N<<2],k[N<<2],lm[N<<2],rm[N<<2];void push_up(ll x){lm[x]=lm[ls];rm[x]=rm[rs];return;}void get(ll x,ll l,ll r,ll bb,ll kk){b[x]+=bb;k[x]+=kk;lm[x]+=bb+kk*l;rm[x]+=bb+kk*r;return;}void clr(ll x){lazy[x]=1;k[x]=b[x]=lm[x]=rm[x]=0;return;}void push_down(ll x,ll l,ll r){if(lazy[x]){clr(ls);clr(rs);lazy[x]=0;}ll mid=l+r>>1;get(ls,l,mid,b[x],k[x]);get(rs,mid+1,r,b[x],k[x]);b[x]=k[x]=0;return;}void add(ll x,ll L,ll R,ll l,ll r,ll y){if(L==l&&R==r){get(x,l,r,y,0);return;}push_down(x,L,R);ll mid=L+R>>1;if(r<=mid)add(ls,L,mid,l,r,y);else if(l>mid)add(rs,mid+1,R,l,r,y);else add(ls,L,mid,l,mid,y),add(rs,mid+1,R,mid+1,r,y);push_up(x);return;}void change(ll x,ll L,ll R,ll l,ll r,ll y,ll z){if(L==l&&R==r){ll gl=y+z*l,gr=y+z*r;if(gl>=lm[x]&&gr>=rm[x])return;//分界點在中間就二分下去else if(gl<=lm[x]&&gr<=rm[x]){clr(x);get(x,l,r,y,z);return;}}push_down(x,L,R);ll mid=L+R>>1;if(r<=mid)change(ls,L,mid,l,r,y,z);else if(l>mid)change(rs,mid+1,R,l,r,y,z);else change(ls,L,mid,l,mid,y,z),change(rs,mid+1,R,mid+1,r,y,z);push_up(x);return;}ll ask(ll x,ll l,ll r,ll y){if(l==r)return lm[x];push_down(x,l,r);ll mid=l+r>>1;if(y<=mid)return ask(ls,l,mid,y);else return ask(rs,mid+1,r,y);} }TL,TR; ll get(ll l,ll r) {ll g=lg[r-l+1];if(h[f[l][g]]>=h[f[r-(1<<g)+1][g]])return f[l][g];else return f[r-(1<<g)+1][g]; } void solve(ll l,ll r) {ll x=get(l,r);if(l<x)solve(l,x-1);if(x<r)solve(x+1,r);for(ll i=0;i<q[x].size();++i){ll lans=0,rans=0,L=q[x][i].fs.fs,R=q[x][i].fs.sn;if(L<x)lans=TR.ask(1,1,n,L);if(x<R)rans=TL.ask(1,1,n,R);ans[q[x][i].sn]=min(lans+h[x]*(R-x+1),rans+h[x]*(x-L+1));}ll gl=h[x],gr=h[x];if(l<x)gl+=TL.ask(1,1,n,x-1);if(x<r)gr+=TR.ask(1,1,n,x+1);TL.add(1,1,n,x,x,gl);TR.add(1,1,n,x,x,gr);if(l<x){TR.add(1,1,n,l,x-1,h[x]*(r-x+1));//加上右子樹的點走到左邊的貢獻TR.change(1,1,n,l,x-1,gr+h[x]*x,-h[x]);//在右邊選的貢獻}if(x<r){TL.add(1,1,n,x+1,r,h[x]*(x-l+1));TL.change(1,1,n,x+1,r,gl-h[x]*x,h[x]);}return; } int main() {scanf("%lld%lld",&n,&t);for(ll i=1;i<=n;++i){scanf("%lld",&h[i]);f[i][0]=i;}for(ll i=2;i<=n;++i)lg[i]=lg[i>>1]+1;for(ll j=1;j<=20;++j)for(ll i=1;i<=n-(1<<j)+1;++i)if(h[f[i][j-1]]>=h[f[i+(1<<j-1)][j-1]])f[i][j]=f[i][j-1];else f[i][j]=f[i+(1<<j-1)][j-1];for(ll i=1;i<=t;++i){scanf("%lld%lld",&l,&r);l++;r++;q[get(l,r)].push_back(mp(mp(l,r),i));}solve(1,n);for(ll i=1;i<=t;++i)printf("%lld\n",ans[i]);return 0; }

總結

以上是生活随笔為你收集整理的【笛卡尔树】【线段树】meetings 会议（P5044）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。