【可持久化线段树】2019雅礼集训 permutation

题目：

分析：

比较恶心的一道题。
首先，将式子转化一下，变成
$\sum A_{P_i}?(n?i+1)$
这里应该很好理解，无非就是把当前排列倒序，然后计算贡献而已。

但是只有这么写才比较容易看出下一步的性质：
显然，题目的最小值，必然是当$P_i$为升序时（否则可以通过交换一对来得到更小的答案）

然后对某个排列，转移到任意其他排列，可以通过这种方式：
将目标排列的第一个数，从当前排列中移动到第一位，再讲目标排列的第二个数，从当前排列中移动到第二位……

显然，每次这样做会使得答案不减。（每次操作后的贡献为${\sum }_j^{i?1}(A_i?A_j),又A_i>A_j$）

所以，可以把这看做是转移的方式。

定义$g(u,len)$表示在当前状态下，把u向前移动len的贡献。

由于$g(u,len)$随len单调，所以初始状态下可以选择的转移必然为：$g(2,1),g(3,1),g(4,1)\dots \dots g(n,1)$

现在考虑当使用一次转移后，能得到哪些新的转移。
假设当前使用了$g(u,len)$

首先，肯定能转移到$g(u,len+1)$，其含义为：在原序列中，将u移动len+1位。
然后，还能转移到$g(u_i,le{n}_i)$，其中$(i\in [u?len+1,n])$，其含义为：在移动了u后，再移动其余位置的转移。

第一种转移很好操作，直接线段树上更改就好了。

问题是第二种怎么搞。

观察到，第二种转移方式，无非就只有$u?len$及以前的被删掉了，然后$u$的位置被更改了。其余部分和原线段树没有任何更改。所以就可以用可持久化线段树实现这一过程。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define SF scanf
#define PF printf
#define MAXN 300010
#define INF 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<ll,int> PLI;
struct node{
    int u,len,s;ll g;	node *ch[2];void pushup(){
    s=ch[0]->s+ch[1]->s;if(ch[0]->g < ch[1]->g)u=ch[0]->u,len=ch[0]->len,g=ch[0]->g;elseu=ch[0]->s+ch[1]->u,len=ch[1]->len,g=ch[1]->g;}
}tree[MAXN*40];
node *ncnt=tree,*NIL;
struct Tree{
    node *ori,*now;ll sum;
}Root[MAXN*40];
int cnt;
priority_queue<PLI,vector<PLI>,greater<PLI> >que;
ll a[MAXN];
void init(){
    NIL=ncnt=tree;NIL->ch[0]=NIL->ch[1]=NIL;NIL->u=NIL->len=NIL->s=0;NIL->g=INF;
}
node *Newnode(){
    ++ncnt;ncnt->ch[0]=ncnt->ch[1]=NIL;ncnt->u=ncnt->len=ncnt->s=0;ncnt->g=INF;return ncnt;	
}
void build(int l,int r,node *&x){
    x=Newnode();if(l==r){
    x->u=x->s=x->len=1;	if(l>1) x->g=a[l]-a[l-1];else x->g=INF;return ;}int mid=(l+r)>>1;build(l,mid,x->ch[0]);build(mid+1,r,x->ch[1]);x->pushup();
}
ll query(node *x,int l,int r,int pos){
    if(l==r)return a[l];int mid=(l+r)>>1;if(pos<=x->ch[0]->s)return query(x->ch[0],l,mid,pos);elsereturn query(x->ch[1],mid+1,r,pos - x->ch[0]->s);
}
bool flag;
void ChangePoint(node *&x,int l,int r,int pos,ll newg,int news){
    node *y=Newnode();*y=*x;x=y;if(l==r){
    if(flag==1)x->g+=newg;elsex->g=newg,x->s=news;return ;}int mid=(l+r)>>1;if(pos<=x->ch[0]->s)ChangePoint(x->ch[0],l,mid,pos,newg,news);elseChangePoint(x->ch[1],mid+1,r,pos - x->ch[0]->s,newg,news);x->pushup();
}
void Delete(node *&x,int l,int r,int len){
    if(len==0)return ;int mid=(l+r)>>1;node *y=++ncnt;*y=*x;x=y;if(x->ch[0]->s > len)Delete(x->ch[0],l,mid,len);elseDelete(x->ch[1],mid+1,r,len - x->ch[0]->s),x->ch[0]=NIL;x->pushup();
}
int n,k;
void Extend(int px){
    int newid=++cnt;int u=Root[px].now->u,len=Root[px].now->len;int l=u-len;
// PF("[%d %d]",u,len);Root[newid].sum=Root[px].sum+Root[px].now->g;Root[newid].ori=Root[px].ori;ChangePoint(Root[newid].ori,1,n,u,INF,0);Delete(Root[newid].ori,1,n,l-1);if(len+1<=Root[newid].ori->s){
    ll newval=query(Root[newid].ori,1,n,len+1)-query(Root[newid].ori,1,n,len);ChangePoint(Root[newid].ori,1,n,len+1,newval,1);	}ChangePoint(Root[newid].ori,1,n,1,INF,1);Root[newid].now=Root[newid].ori;
// PF("{%lld+%lld %d}\n",Root[newid].now->g,Root[newid].sum,newid);que.push(make_pair(Root[newid].now->g+Root[newid].sum,newid));if(l>1){
    ll newval=query(Root[px].now,1,n,u)-query(Root[px].now,1,n,l-1);flag=1;ChangePoint(Root[px].now,1,n,u,newval,1);	flag=0;}elseChangePoint(Root[px].now,1,n,u,INF,1);que.push(make_pair(Root[px].now->g+Root[px].sum,px));
// PF("{%lld+%lld %d}\n",Root[px].now->g,Root[px].sum,px);
}
int main(){
    init();SF("%d%d",&n,&k);for(int i=1;i<=n;i++)SF("%lld",&a[i]);sort(a+1,a+1+n);build(1,n,Root[0].ori);for(int i=1;i<=n;i++)Root[0].sum+=a[i]*(n-i+1);PF("%lld\n",Root[0].sum);Root[0].now=Root[0].ori;que.push(make_pair(Root[0].now->g+Root[0].sum,0));while(--k){
    PLI tp=que.top();que.pop();PF("%lld\n",tp.first);Extend(tp.second);}
}