T1
\(f_i\) 表示以 \(i\) 为结尾的答案，然后转移为 \(f_i=\max\limits_{j=1}^{i-1}(f_j+(a_i-a_j)^2+c)\)
这样会有不合法的情况无法转移，就是两个数之间有比他俩都大的值
但是这样的值一定会比从最大值转移要劣，所以直接斜率做一下就行
Code
#include<bits/stdc++.h>
#define int long long
#define lson rt<<1
#define rson rt<<1|1
#define rint signed
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,C,ans;
int a[1000010],f[1000010];
inline int sq(int x){return x*x;}
struct node{
int k,b;
inline int calc(int x){return k*x+b;}
}st[1000010*4];
inline bool cover(node a,node b,int x){return b.calc(x)>=a.calc(x);}
void build(int rt,int l,int r){
st[rt].k=0,st[rt].b=-inf;
if(l==r) return ;
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
}
void ins(int rt,int l,int r,node k){
if(cover(st[rt],k,l)&&cover(st[rt],k,r)) return st[rt]=k,void();
if(l==r) return ;
int mid=(l+r)>>1;
if(cover(st[rt],k,mid)) swap(st[rt],k);
if(cover(st[rt],k,l)) ins(lson,l,mid,k);
if(cover(st[rt],k,r)) ins(rson,mid+1,r,k);
}
int query(int rt,int l,int r,int pos){
if(l==r) return st[rt].calc(pos);
int mid=(l+r)>>1,res=st[rt].calc(pos);
if(pos<=mid) res=max(res,query(lson,l,mid,pos));
else res=max(res,query(rson,mid+1,r,pos));
return res;
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
freopen("array.in","r",stdin);
freopen("array.out","w",stdout);
n=read(),C=read();
for(int i=1;i<=n;i++) a[i]=read();
build(1,1,1000000);
ins(1,1,1000000,(node){-2*a[1],f[1]+a[1]*a[1]});
for(int i=2;i<=n;i++){
f[i]=query(1,1,1000000,a[i])+C+a[i]*a[i];
ins(1,1,1000000,(node){-2*a[i],f[i]+a[i]*a[i]});
}
printf("%lld\n",f[n]);
return 0;
}
T2
先询问出全局的最大差值，然后二分一个位置找到任意一个极值的位置
因为每个数都不一样，于是与极值作差的结果也都不一样
再按二进制位拆分，每个差值都会在是二进制下是 \(1\) 的那一位出现一次
于是就能找出每个位置与极值的差，然后再找出最大的那个位置
询问一下，看看一开始的值是最大值还是最小值然后就能知道出所有数的值了
Code
#include "difference.h"
#include<bits/stdc++.h>
using namespace std;
namespace TTT{
void find(int n, int M1, int M2){
int pos,cpos,l,r,mx=-1,v,vc;
vector<int>vec,s,c,anss;
map<int,int>mp[20],t;
vec.resize(n);c.resize(n);anss.resize(n);
for(int i=0;i<n;i++) vec[i]=i;
s=qry2(vec);for(auto L:s) mx=max(mx,L);
l=0,r=n-1;
while(l<=r){
int mid=(l+r)>>1,tmx=-1;
vec.resize(mid+1);for(int i=0;i<=mid;i++) vec[i]=i;
s=qry2(vec);for(auto L:s) tmx=max(tmx,L);
if(tmx==mx) r=mid-1,pos=mid;
else l=mid+1;
}
for(int i=0;(1<<i)<=n;i++){
pos+1>>i&1;
vec.clear();
for(int j=1;j<=n;j++) if((j>>i)&1) if(j-1!=pos) vec.emplace_back(j-1);
s=qry2(vec);for(auto L:s) mp[i][L]--;
vec.clear();
for(int j=1;j<=n;j++) if((j>>i)&1) if(j-1!=pos) vec.emplace_back(j-1);
vec.emplace_back(pos);
s=qry2(vec);for(auto L:s) mp[i][L]++;
}
for(int i=0,sum;i<n;i++) if(i!=pos){
t.clear();sum=0;
for(int j=0;(1<<j)<=n;j++) if(((i+1)>>j)&1){
sum++;
for(auto L:mp[j]) if(L.second!=0) t[L.first]++;
}else for(auto L:mp[j]) if(L.second!=0) t[L.first]+=1000;
for(auto L:t) if(L.second==sum) c[i]=L.first;
}
for(int i=0,tmx=-1;i<n;i++){tmx=max(tmx,c[i]);if(tmx==c[i]) cpos=i;}
v=qry1(pos);vc=qry1(cpos);
if(v<vc) for(int i=0;i<n;i++) anss[i]=c[i]+v;
else for(int i=0;i<n;i++) anss[i]=v-c[i];
return answer(anss),void();
}}
void find(int n, int M1, int M2){TTT::find(n,M1,M2);}
T3
咕咕咕