T1

设 \(f_i\) 表示以 \(i\) 结尾的最大答案

发现只考虑当 \(a_i\) 是最大值时的转移也是正确的

即 \(f_i=\max_{j=1}^{i-1} \{ (b_j-b_i)^2+c+f_j \}\)

因为若中间夹着个比 \(a_i,a_j\) 值都大的值的话肯定不会优

然后李超树维护就行

T2

首先，如果知道了序列的最大值 \(mx\)，设询问的集合为 \(S\)，并且询问 \(S\bigcup {mx}\)，就可以知道集合所有元素与最大值的差

先考虑找到最大值，首先全体询问得到极差 \(k\)，然后二分前缀得到 \(k\) 第一次出现的位置，即为最大值或最小值，设为 \(x\)

然后设 \(S_i\) 表示第 \(i\) 个二进制位为 \(1\) 的数的集合，询问 \(S_i\) 和 \(S\bigcup {x}\) 得到与 \(x\) 的差

然后就能得到 \(a_i\)与 \(x\) 的差

\(qry1\) 询问差最大的那个数并与 \(x\) 比较，就能确定 \(x\) 是最大还是最小

代码

T1

#include<cstdio>
#include<iostream>
using namespace std;
#define il inline
#define int long long
const int N=1e6+11;
const int inf=1e18;
struct seg_{
	int k,val;seg_(){}
	seg_(int k_,int val_){k=k_,val=val_;}
};
struct tree{bool jd;seg_ x;}tre[N*4];
int n,c;
int a[N];
il int pd(int x){return x*x;}
il int max_(int x,int y){return x>y?x:y;}
int get_ans(seg_ a,int x){return a.k*x+a.val;}
bool check(seg_ a,seg_ b,int x){return get_ans(a,x)<get_ans(b,x);}
il int read(){
	int s=0;char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s;
}
void ins(int i,int l,int r,seg_ x){
	int mid=(l+r)>>1;
	if(!tre[i].jd){tre[i].jd=1;tre[i].x=x;return;}
	if(check(tre[i].x,x,mid))swap(tre[i].x,x);
	if(l==r)return;
	if(check(tre[i].x,x,r))ins(i<<1|1,mid+1,r,x);
	if(check(tre[i].x,x,l))ins(i<<1,l,mid,x);
}
int qry(int i,int l,int r,int x){
	if(!tre[i].jd)return -inf;
	if(l==r)return get_ans(tre[i].x,x);
	int mid=(l+r)>>1;
	int ans=tre[i].jd?get_ans(tre[i].x,x):-inf;
	if(x<=mid) return max_(ans,qry(i<<1,l,mid,x));
	else return max_(ans,qry(i<<1|1,mid+1,r,x));
}
signed main(){
	freopen("array.in","r",stdin),freopen("array.out","w",stdout);
	n=read();c=read();
	for(int i=1;i<=n;++i)a[i]=read();
	ins(1,1,1e6,seg_(-2*a[1],pd(a[1])));
	for(int x,i=2;i<=n;++i){
		x=qry(1,1,1e6,a[i])+pd(a[i])+c;
		if(i==n)cout<<x<<endl;
		ins(1,1,1e6,seg_(-2*a[i],x+pd(a[i])));
	}
}

T2

#include "difference.h"
#include<set>
#include<vector>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define il inline
const int N=250+11;
const int M=N*N;
set<int> mrg(set<int> a,set<int> b){
	if(!a.size())return b;
	set<int> x;x.clear();
	for(set<int>::iterator it=a.begin();it!=a.end();++it){
		if(b.find(*it)!=b.end()){
			x.insert(*it);
			b.erase(*it);
		}
	}return x;
}
set<int> pop(set<int> a,set<int> b){
	for(set<int>::iterator it=b.begin();it!=b.end();++it){
		if(a.find(*it)!=a.end())a.erase(*it);
	}return a;
}
void find(int n,int m1,int m2){
	set<int> s[10];
	vector<int> a,b,ans;
	unordered_map<int,int>mp;

	for(int i=0;i<n;++i)a.push_back(i);
	b=qry2(a);sort(b.begin(),b.end());
	int mx_cz=b[b.size()-1];
	int l=1,r=n-1,mid,loc=0;
	while(l<=r){
		mid=(l+r)>>1;a.clear();
		for(int i=0;i<=mid;++i)a.push_back(i);
		b=qry2(a);sort(b.begin(),b.end());
		if(b[b.size()-1]==mx_cz)loc=mid,r=mid-1;
		else l=mid+1;
	}

	for(int i=0;i<8;++i){
		a.clear();
		for(int j=0;j<n;++j){
			if(j==loc)continue;
			if((1<<i)&j)a.push_back(j);
		}b=qry2(a);mp.clear();
		for(int j=0;j<b.size();++j)++mp[b[j]];
		a.push_back(loc);b=qry2(a);
		for(int j=0;j<b.size();++j){
			if(mp[b[j]])--mp[b[j]];
			else s[i].insert(b[j]);
		}
	}//for(int j : s[2])cout<<j<<" fdafd"<<endl;

	int jd=1;int k=0;
	for(int i=0;i<n;++i)ans.push_back(0);
	ans[loc]=qry1(loc);
	for(int x,i=0;i<n;++i){
		s[8].clear();
		if(i==loc)continue;
		for(int j=0;j<8;++j)if((1<<j)&i)s[8]=mrg(s[8],s[j]);
		for(int j=0;j<8;++j)if(!((1<<j)&i))s[8]=pop(s[8],s[j]);
		if(s[8].size())x=*s[8].begin();
		a.clear();a.push_back(i),a.push_back(loc);
		ans[i]=i?x:qry2(a)[0];
		if(ans[i]==mx_cz){
			k=i;ans[i]=qry1(i);
			if(ans[i]>ans[loc])jd=1;
			else jd=-1;
		}
	}
	for(int i=0;i<n;++i){
		if(i==k||i==loc)continue;
		ans[i]=ans[loc]+jd*ans[i];
	}answer(ans);
}