专项测试 数据结构2
T1 5a2m5Yab6aKY
还不会
T2 Q0Y1NzFE
一种在线做法
两个集合分别启发式合并
每个1集合记录操作权值的前缀和和操作时间，2集合记录操作时间
每个下标只会在O(log)个集合里存在过，按照时间顺序记下这些集合
询问下标 i 时，按时间扫 i 在过的2集合，倒序找到第一个集合k，满足k最后一次操作时 i 在k中，记下这次操作的时间 t
然后扫 1 集合，加上每个集合在 t 之后的对 i 的贡献
时间复杂度\(O(m \log^2n)\)，因为扫1集合算贡献时每个集合要二分操作，找出并减去 i 加进这个集合之前的操作的前缀和
当然在 i 加入这个集合时记一下当前前缀和，就可以不用二分了
时间复杂度\(O(m\log n)\)，空间复杂度\(O(n\log n)\)
T3 U1BPSiBDT1Q2
f[i] 表示 i 的子树 链剖分完的最小权值和
暴力 ：记 v 的父亲为 u，当 v -> u 时，dfs 子树u，到x时维护u->x这条链的权值，以及链上的点的不在链上的儿子的 f 的和sum，每次取min
这个复杂度是size的和，也就是祖先的数量，可惜数据不是随的
正解 ：还是这个暴力，考虑用一个式子表示一下
val[i] 表示 i 到根的点权和，sum还是那个 f 和
\[f_x=\min((val_v-val_{fa_x})^2+sum) \]v在x的子树内，这个贡献记为 w，拆开，交换一下
\[val_v^2+val_{fa_x}^2-2* val_v* val_{fa_x}+sum=w \]\[2* val_v* val_{fa_x}+(w-val^2_{fa_x})=val^2_v+sum \]是斜率优化的形式，\((val_v，val^2_v+sum)\)是(x,y)，要使截距\(b=w-val^2_{fa_x}\)最小
斜率\(2* val_{fa_x}\)有正负，维护下凸包
set维护每个子树的凸包，子树合并时启发式合并，动态在最大的凸包上加点
时间复杂度\(O(n \log^2n)\)
代码
T2
#include
using namespace std;
#define int long long
const int N=1e5+11;
struct opt_{int t,val;};
int n,m,t;
int p[2][N];
int f[2][20][N],tim[2][20][N],top[2][N];
vector vct[2][N];
vector opt[2][N];
inline int max_(int x,int y){return x>y?x:y;}
inline 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;
}
inline char readc()
{
char ch=getchar();
while(ch>'Z'||ch<'A') ch=getchar();
return ch;
}
void join(int x,int y,bool jd)
{
x=f[jd][top[jd][x]][x];
y=f[jd][top[jd][y]][y];
if(x==y) return;
if(vct[jd][p[jd][x]].size()>1;
if(opt[0][x][mid].ttim[1][i][x]) {tt=opt[1][v][opt[1][v].size()-1].t;break;}
}
for(int v,i=top[0][x];i;--i)
{
ans+=two(f[0][i][x],max_(tt,tim[0][i][x]));
if(tim[0][i][x] T3
#include
using namespace std;
#define int long long
#define fi first
#define se second
#define pll pair
#define mkp make_pair
#define il inline
const int inf=0x7fffffffffffffff;
const int N=1e6+11;
int n;
int w[N],fa[N];
int f[N],del[N];
set st[N];
set::iterator L,M,R,ans;
vector vct[N];
il int pd(int x){return x*x;}
il int max_(int x,int y){return x>y?x:y;}
il int min_(int x,int y){return x>y?y:x;}
il double get_xl(pll a,pll b){return 1.0*(a.se-b.se)/(a.fi-b.fi);}
il bool cmp(pll a,pll b,pll c){return get_xl(a,b)'9'||ch<'0') {if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s*w;
}
void insert(int i,pll p)
{
p.se-=del[i];
M=st[i].lower_bound(p);
if(M!=st[i].end()&&M->fi==p.fi) st[i].erase(M),M=st[i].lower_bound(p);
if(M!=st[i].begin()&&(--M)->fi==p.fi) return;
while(st[i].size())
{
M=st[i].lower_bound(p);
if(M==st[i].begin()) break;
--M;
if(M==st[i].begin()) break;
--(L=M);
if(!cmp(*L,*M,p)) st[i].erase(M);
else break;
}
while(st[i].size())
{
M=st[i].lower_bound(p);
if(M==st[i].end()) break;
++(R=M);
if(R==st[i].end()) break;
if(!cmp(p,*M,*R)) st[i].erase(M);
else break;
}
R=st[i].lower_bound(p);
if(R==st[i].end()||R==st[i].begin()) {st[i].insert(p);return;}
--(L=R);
if(!cmp(*L,p,*R)) return;
st[i].insert(p);
return;
}
int get_ans(int x)
{
if(st[x].size()==0) return inf;
int l=(*st[x].begin()).fi,r=(*st[x].rbegin()).fi,mid;
double xl=2*w[fa[x]];
ans=st[x].begin();
while(l<=r)
{
mid=(l+r)>>1;
M=st[x].lower_bound({mid,-inf});
if(M==st[x].begin()) {l=mid+1;continue;}
--(L=M);
if(get_xl(*L,*M)se-2*ans->fi*w[fa[x]];
if(ans!=st[x].begin()) --ans,sum=min_(sum,ans->se-2*ans->fi*w[fa[x]]);
++ans,++ans;
if(ans!=st[x].end()) sum=min_(sum,ans->se-2*ans->fi*w[fa[x]]);
return sum+del[x]+pd(w[fa[x]]);
}
void dfs(int x)
{
w[x]+=w[fa[x]];
int sum=0,son=0;
for(int v : vct[x])
{
dfs(v);
sum+=f[v];
if(st[son].size()