太空飞船
Description
环上有 N 个整数 \(l_i\)。要把环划分成 K 段，使得每段之和的方差最小。
HINT
三个部分:
- \(K=2,N\leq10^5\).
- \(K=3,N\leq3\times10^5\).
- \(K\leq20,N\leq400\).
Solution
第一部分直接枚举一个断点,另一个断点三分即可.
第二部分将环复制两遍,直接枚举一个断点,另外两个断点肯定是在总和的三分点附近.
第三部分比较麻烦.
把方差的式子展开发现,其实只需最小化每段之和的平方的和.
\(f[i][j]\) 表示前 \(j\) 个数分成 \(i\) 段的最小值.
\(f[i][j]=min\{f[i-1][k]+(s[j]-s[k])^2\}\).
撇开 \(i\) 那一维考虑一下斜率优化.
如果 \(k1>k2\) 且 \(f[j]_{k_1}<f[j]_{k_2}\) 的情况:
\(f[k_1]+(s[j]-s[k_1])^2<f[k_2]+(s[j]-s[k_2])^2\)
\(f[k_1]+s[j]^2-2\times s[j]\times s[k_1]+s[k_1]^2<f[k_2]+s[j]^2-2\times s[j]\times s[k_2]+s[k_2]^2\)
\(f[k_1]+s[k_1]^2-f[k_2]-s[k_2]^2<2\times s[j]\times(s[k_1]-s[k_2])\)
\(\frac{f[k_1]+s[k_1]^2-f[k_2]-s[k_2]^2}{s[k_1]-s[k_2]}<2\times s[j]\)
考虑队列中的情况:
如果当前比其优的,后面也一定比其优;如果当前比其劣的,后面有可能比其优.
按 \(\frac{f[k_1]+s[k_1]^2-f[k_2]-s[k_2]^2}{s[k_1]-s[k_2]}\) 维护上升序列,每次操作前弹出劣的队头,取队头为 \(k\).
#define K 21
#define M 401
#define N 600001
using namespace std;
ll f[K][M],ans,inf;
int l[N],s[N],q[N],n,k,h,t;
inline ll sqr(int x){
return 1ll*x*x;
}
inline ll g(int x){
return k*sqr(x)-2ll*s[n]*x;
}
inline ll G(int x,int i){
return f[i-1][x]+sqr(s[x]);
}
inline void Aireen(){
n=read();k=read();
for(int i=1;i<=n;++i) s[i]=l[i]=read();
for(int i=1;i<=n;++i) s[i]+=s[i-1];
if(k==2){
for(int i=1;i<k;++i) inf+=g(l[i]);
inf+=g(s[n]-s[k-1]);ans=inf;
for(int i=1;i<=n;++i) s[i+n]=l[i+n]=l[i];
for(int i=1;i<=n;++i) s[i+n]+=s[i+n-1];
int lef,rig,m1,m2;
for(int i=0;i<n;++i){
lef=i+1;rig=i+n-1;
while(lef<rig){
m2=(rig-lef+1)/3;m1=lef+m2;m2+=m1;
if(g(s[m1]-s[i])+g(s[i+n]-s[m1])<=g(s[m2]-s[i])+g(s[i+n]-s[m2])) rig=m2-1;
else lef=m1+1;
}
ans=min(g(s[lef]-s[i])+g(s[i+n]-s[lef]),ans);
}
printf("%lld\n",1ll*k*(ans+sqr(s[n])));
return;
}
if(n<=M){
for(int i=1;i<k;++i) inf+=sqr(l[i]);
inf+=sqr(s[n]-s[k-1]);ans=inf;
for(int x=1;x<=n;++x){
for(int i=1;i<=n;++i) f[1][i]=sqr(s[i]);
for(int i=2;i<=k;++i){
h=1;t=0;q[++t]=i-1;
for(int j=i;j<=n;++j){
f[i][j]=inf;
while(h<t&&(G(q[h+1],i)-G(q[h],i))<2ll*s[j]*(s[q[h+1]]-s[q[h]])) ++h;
f[i][j]=min(f[i][j],f[i-1][q[h]]+sqr(s[j]-s[q[h]]));
while(h<t&&(G(j,i)-G(q[t],i))*(s[q[t]]-s[q[t-1]])<(G(q[t],i)-G(q[t-1],i))*(s[j]-s[q[t]])) --t;
q[++t]=j;
}
}
ans=min(ans,f[k][n]);
for(int i=1;i<=n;++i)
l[i-1]=l[i];
l[n]=l[0];
for(int i=1;i<=n;++i)
s[i]=s[i-1]+l[i];
}
printf("%lld\n",ans*sqr(k)-1ll*k*sqr(s[n]));
return;
}
if(k==3){
for(int i=1;i<k;++i) inf+=sqr(l[i]);
inf+=sqr(s[n]-s[k-1]);ans=inf;
for(int i=1;i<=n;++i) s[i+n]=l[i+n]=l[i];
for(int i=1;i<=n;++i) s[i+n]+=s[i+n-1];
for(int i=0,j=1,y=1,x=s[n]/3,z,r;i<n;++i){
r=i+n;//(i,r]
while(j+2<r&&s[j]-s[i]<=x) ++j;
z=s[r]-s[j]>>1;
if(y<j) y=j;
while(y+1<r&&s[y]-s[j]<=z) ++y;
while(y-2>i&&s[y-1]-s[j]>=z) --y;
ans=min(ans,sqr(s[j]-s[i])+sqr(s[y]-s[j])+sqr(s[r]-s[y]));
if(y-1>i)ans=min(ans,sqr(s[j]-s[i])+sqr(s[y-1]-s[j])+sqr(s[r]-s[y-1]));
if(y+1<r) ans=min(ans,sqr(s[j]-s[i])+sqr(s[y+1]-s[j])+sqr(s[r]-s[y+1]));
if(j+1<r){
ans=min(ans,sqr(s[j+1]-s[i])+sqr(s[y]-s[j+1])+sqr(s[r]-s[y]));
if(y-1>i)ans=min(ans,sqr(s[j+1]-s[i])+sqr(s[y-1]-s[j+1])+sqr(s[r]-s[y-1]));
if(y<r) ans=min(ans,sqr(s[j+1]-s[i])+sqr(s[y+1]-s[j+1])+sqr(s[r]-s[y+1]));
}
if(j-1>i){
ans=min(ans,sqr(s[j-1]-s[i])+sqr(s[y]-s[j-1])+sqr(s[r]-s[y]));
if(y-1>i)ans=min(ans,sqr(s[j-1]-s[i])+sqr(s[y-1]-s[j-1])+sqr(s[r]-s[y-1]));
if(y+1<r) ans=min(ans,sqr(s[j-1]-s[i])+sqr(s[y+1]-s[j-1])+sqr(s[r]-s[y+1]));
}
}
printf("%lld\n",ans*sqr(k)-1ll*k*sqr(s[n]));
return;
}
}
神秘物质
Description
给定一个有 N 个原子的序列 \(e_i\)。
维护以下 4 种操作,共有 M 个操作:
- merge x e 当前第 x 个原子和第 x+1 个原子合并，得到能量为 e 的新原子；
- insert x e 在当前第 x 个原子和第 x+1 个原子之间插入一个能量为 e 的新原子；
- max x y 询问当前第 x 到第 y 个原子之间的任意子区间中区间极差的最大值；
- min x y 询问当前第 x 到第 y 个原子之间的任意子区间中区间极差的最小值。
其中，子区间指的是长度至少是 2 的子区间。
HINT
\(N,M\leq10^5\).
Solution
可以发现,第3种操作等价于求区间最大值-区间最小值;第3种操作等价于求区间相邻两数之差的最小值.
splay维护下标直接上.
#define N 200005
#define INF 1000000001
struct Splay{
int c[2],f,mx,mi,di,li,ri,siz,val;
}tr[N];
int e[N],n,m,rt,cnt;
inline void recnt(int u){
int lef=tr[u].c[0],rig=tr[u].c[1];
tr[u].siz=tr[lef].siz+tr[rig].siz+1;
tr[u].mx=tr[u].mi=tr[u].val;tr[u].di=INF;
if(!lef) tr[u].li=tr[u].val;
else{
tr[u].mx=max(tr[lef].mx,tr[u].mx);
tr[u].mi=min(tr[lef].mi,tr[u].mi);
tr[u].li=tr[lef].li;
tr[u].di=min(tr[lef].di,tr[u].di);
tr[u].di=min(tr[u].di,abs(tr[lef].ri-tr[u].val));
}
if(!rig) tr[u].ri=tr[u].val;
else{
tr[u].mx=max(tr[u].mx,tr[rig].mx);
tr[u].mi=min(tr[u].mi,tr[rig].mi);
tr[u].ri=tr[rig].ri;
tr[u].di=min(tr[u].di,tr[rig].di);
tr[u].di=min(tr[u].di,abs(tr[u].val-tr[rig].li));
}
}
inline void build(int l,int r,int f){
int mid=(l+r)>>1;
if(l<r){
if(l<mid) build(l,mid-1,mid);
if(mid<r) build(mid+1,r,mid);
}
else if(l==r){
tr[mid].di=INF;tr[mid].siz=1;
tr[mid].li=tr[mid].ri=tr[mid].mx=tr[mid].mi=e[mid];
}
tr[mid].val=e[mid];tr[mid].f=f;recnt(mid);
tr[f].c[mid<f?0:1]=mid;
}
inline int kth(int k){
int u=rt;
while(tr[u].siz-tr[tr[u].c[1]].siz!=k){
if(k<=tr[tr[u].c[0]].siz) u=tr[u].c[0];
else k-=tr[u].siz-tr[tr[u].c[1]].siz,u=tr[u].c[1];
}
return u;
}
inline bool son(int u){
return tr[tr[u].f].c[1]==u;
}
inline void ins_p(int f,int u,bool c){
tr[f].c[c]=u;tr[u].f=f;
}
inline void rotate(int u){
int f=tr[u].f;bool c=son(u);
if(!tr[f].f){
rt=u;tr[u].f=0;
}
else ins_p(tr[f].f,u,son(f));
ins_p(f,tr[u].c[c^1],c);
ins_p(u,f,c^1);
recnt(f);recnt(u);
}
inline void splay(int u,int f){
while(tr[u].f!=f){
if(tr[tr[u].f].f==f) rotate(u);
else if(son(u)==son(tr[u].f)){
rotate(tr[u].f);rotate(u);
}
else{
rotate(u);rotate(u);
}
}
}
inline int near(int u,bool c){
if(tr[u].c[c]){
u=tr[u].c[c];c^=1;
while(tr[u].c[c])
u=tr[u].c[c];
return u;
}
while(u&&son(u)==c) u=tr[u].f;
return tr[u].f;
}
inline int select(int u,int v){
u=kth(u);v=kth(v);
u=near(u,0);v=near(v,1);
splay(u,0);splay(v,rt);
return tr[v].c[0];
}
inline void mx(int l,int r){
int u=select(l,r);
printf("%d\n",tr[u].mx-tr[u].mi);
}
inline void mi(int l,int r){
int u=select(l,r);
printf("%d\n",tr[u].di);
}
inline void clear(int u){
tr[tr[u].f].c[son(u)]=0;
tr[u].c[0]=tr[u].c[1]=tr[u].f=tr[u].mx=tr[u].mi=tr[u].di=tr[u].li=tr[u].ri=tr[u].siz=tr[u].val=0;
}
inline void del(int u,int v){
u=select(u,v);
int f=tr[u].f;clear(u);u=f;
while(u){
recnt(u);u=tr[u].f;
}
}
inline void ins(int u,int k){
e[++cnt]=k;build(cnt,cnt,0);
int x=kth(u),y=kth(u+1);
splay(x,0);splay(y,rt);
ins_p(cnt,y,1);ins_p(x,cnt,1);
recnt(cnt);recnt(x);
}
inline void merge(int u,int k){
del(u,u+1);ins(u-1,k);
}
inline void insert(int u,int k){
ins(u,k);
}
inline void Aireen(){
n=read();m=read();
cnt=n+2;e[1]=e[cnt]=INF;
for(int i=1;i<=n;++i) e[i+1]=read();
rt=(1+cnt)>>1;build(1,cnt,0);
char c[10];int x,y;
while(m--){
scanf("%s",&c);x=read();y=read();
if(c[1]=='a')/*max*/mx(x+1,y+1);
else if(c[1]=='i')/*min*/mi(x+1,y+1);
else if(c[1]=='e')/*merge*/merge(x+1,y);
else/*insert*/insert(x+1,y);
}
}
2017-04-21 15:28:26