1484 种树 此版本是线性的，那么根据链表维护即可；

构建新点，点的左右分别是原整个区间的前驱及后继，再正常维护即可

注意两个版本的维护有所不同

第二个版本的维护直接将左右两点删除

1792 种树2  此版本是环

1484

#include
     
      #define ll long long using namespace std;const int N=500010;struct node{    ll v;int id;    bool operator <(node a)const{    return v
      
        q;int n,k;int main(){    n=read();k=read();    for(int i=1;i<=n;i++){        a[i]=read();        q.push((node){a[i],i});        l[i]=i-1;r[i]=i+1;    }int len=n;    for(int i=1;i<=k;i++){        while(!q.empty()&&vis[q.top().id]) q.pop();        if(q.empty()||q.top().v<0)            break;        node u=q.top();q.pop();        ans+=u.v;        vis[u.id]=vis[l[u.id]]=vis[r[u.id]]=1;        a[++len]=a[l[u.id]]+a[r[u.id]]-a[u.id];        l[len]=l[l[u.id]],r[len]=r[r[u.id]];        r[l[len]]=len;l[r[len]]=len;        q.push((node){a[len],len});    }printf("%lld\n",ans);    return 0;}
      
     

 

1792

#include
     
      #define M 200050#define rep(i,x,y) for(register int i=x;i<=y;i++)using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(!isdigit(ch)){
   if(ch=='-')f=-1;ch=getchar();}    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}    return x*f;}struct node{    int v,id;    friend bool operator < (node x,node y){        return x.v < y.v;}};priority_queue
      
        q;int n,m,ans,chose,r[M],l[M],a[M];bool vis[M];void change(int x){    vis[x]=1;    r[l[x]]=r[x];    l[r[x]]=l[x];    r[x]=0;l[x]=0;}int main(){    n=read(),m=read();    rep(i,1,n) a[i]=read();    if((n>>1)