冲刺省选2月8日第十二场
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
#include
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)'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<
T2
#include "difference.h"
#include
#include
#include
#include
#include
#include
using namespace std;
#define il inline
const int N=250+11;
const int M=N*N;
set mrg(set a,set b){
if(!a.size())return b;
set x;x.clear();
for(set::iterator it=a.begin();it!=a.end();++it){
if(b.find(*it)!=b.end()){
x.insert(*it);
b.erase(*it);
}
}return x;
}
set pop(set a,set b){
for(set::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 s[10];
vector a,b,ans;
unordered_mapmp;
for(int i=0;i>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;jans[loc])jd=1;
else jd=-1;
}
}
for(int i=0;i