GJOI 5.15 题解

1.喷泉

题意

一排喷泉有 $n$ 个喷头，初始时全部处于“开启”状态。每次操作可以改变连续 $k$ 个喷头的状态（开启变关闭，关闭变开启）。经过若干次操作后，最多能形成多少种不同的喷泉状态？由于答案可能很大，请对 $10^9+7$ 取模。

$1\le k\le n\le 10^5$。

思路

打表即可。不难发现答案为 $2^{n-k+1}$。至于证明，我们可以分别考虑 $(n-1,k)$ 和 $(n,k-1)$ 如何转移到 $(n,k)$，从略。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+9,mod=1e9+7;
ll n,k;
ll qpow(ll x,ll k)
{ll ret=1;while(k){if(k&1)ret=ret*x%mod;x=x*x%mod;k>>=1;}return ret;
}
int main()
{scanf("%lld%lld",&n,&k);printf("%lld",qpow(2,n-k+1));return 0;
}

2.AT_abc298_f Rook Score

题意

$1\le n\le 2\times 10^5$，$1\le r,c,v\le 10^9$。

思路

先离散化。设 $han{g}_i$、$li{e}_i$ 分别表示离散化后每一行每一列的数值总和，$x.x$、$x.y$ 分别表示离散化后点 $x$ 的行和列，$x.v$ 表示 $x$ 的数值。

我们可以枚举每一行，然后我们查询每一列出去当前行的交叉点值的最大值。我们存下每一行每一个有数值的点，然后枚举第 $i$ 行——怎么修改数据呢？

其实我们可以把所有 $li{e}_i$ 扔上平衡树，在枚举 $i$ 行上的（有数值的）点编号 $x$ 时，暴力删除 $li{e}_{x.y}$，然后扔 $li{e}_{x.y}-x.v$ 上去。查询最大的列贡献加上 $han{g}_i$，对所有贡献取最大值即可。记得复原更新的数据。

枚举 $x$ 均摊复杂度来到 $\Theta (n)$，平衡树修改和查询就 $\Theta (\log n)$，离散化用了map（不过快排更快）。用 FHQ-Treap 实现平衡树在 $2\times 10^5$ 的极限数据下跑了 $\text{2.2s}$。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+9;
ll n;
ll rt,cnt;
struct Node
{ll ls,rs;ll val,pri;//键值 随机优先级 ll siz;//子树大小 
}T[N];
void newNode(ll x)
{cnt++;T[cnt].siz=1;T[cnt].ls=T[cnt].rs=0;T[cnt].val=x;T[cnt].pri=rand();
}
void pushup(ll u)
{T[u].siz=T[T[u].ls].siz+T[T[u].rs].siz+1;
}
void split(ll u,ll k,ll &L,ll &R)//分裂操作 
{if(u==0){L=R=0;return;}if(T[u].val<=k){L=u;split(T[u].rs,k,T[u].rs,R);}else {R=u;split(T[u].ls,k,L,T[u].ls);}pushup(u);
}
ll merge(ll L,ll R)//合并两棵根为L和R的树，返回树根 
{if(!L||!R)return L|R;if(T[L].pri>T[R].pri){T[L].rs=merge(T[L].rs,R);pushup(L);return L;}else {T[R].ls=merge(L,T[R].ls);pushup(R);return R;}
}
void insert(ll x)//插入一个数x 
{ll L,R;split(rt,x,L,R);newNode(x);rt=merge(merge(L,cnt),R);
}
void del(ll x)//删除一个数x
{ll L,R,u;split(rt,x,L,R);//<=x的树和>x的树 split(L,x-1,L,u);//<x的树和=x的树 u=merge(T[u].ls,T[u].rs);//合并<x和>x的树，就删除了x rt=merge(merge(L,u),R);
}
ll kth(ll u,ll k)//排名为k的节点编号 
{if(k==T[T[u].ls].siz+1)return u;if(k<=T[T[u].ls].siz)return kth(T[u].ls,k);//目标在左return kth(T[u].rs,k-T[T[u].ls].siz-1);//目标在右
}
struct point
{ll x,y,v;
}a[N];
ll cx,cy;
ll hang[N],lie[N];
vector<ll>vec[N]; 
map<ll,ll>mpx,mpy;
int main()
{srand(time(0));scanf("%lld",&n);for(int i=1;i<=n;i++){ll x,y,v;scanf("%lld%lld%lld",&x,&y,&v);if(!mpx[x])mpx[x]=++cx;if(!mpy[y])mpy[y]=++cy;a[i]=(point){mpx[x],mpy[y],v};}ll ans=0;for(int i=1;i<=n;i++){hang[a[i].x]+=a[i].v;lie[a[i].y]+=a[i].v;vec[a[i].x].push_back(i);}for(int i=1;i<=cx;i++)ans=max(ans,hang[i]);for(int i=1;i<=cy;i++)ans=max(ans,lie[i]);for(int i=1;i<=cy;i++)insert(lie[i]);for(int i=1;i<=cx;i++){for(auto x:vec[i]){del(lie[a[x].y]);insert(lie[a[x].y]-a[x].v);}ans=max(ans,T[kth(rt,cy)].val+hang[i]);for(auto x:vec[i]){del(lie[a[x].y]-a[x].v);insert(lie[a[x].y]);}}printf("%lld",ans);return 0;
}

3.AT_abc298_h Sum of Min of Length

题意

$1\le n,m\le 2\times 10^5$，$1\le l,r\le n$。

思路

有个 $\min$ 很麻烦，如果直接做就要枚举 $\Theta (n^2\log n)$，所以我们考虑对 $\min$ 做处理，我们考虑哪些点离 $L$ 更近，离 $R$ 更近。

我们钦定 $L$ 更浅 $R$ 更深，找一个路径中点 $Mid$，我们就可以知道哪些点必然离 $L$ 近，必然离 $R$ 近。举个例子更直观：

我们钦定 $R$ 更深，那么 $Mid$ 肯定会在 $\text{lca}(L,R)$ 到 $R$ 的链上。（待会再讨论刚好在 $\text{lca}(L,R)$ 的情况）

我们规定几个数组：$si{z}_u$ 表示子树 $u$ 的大小，$su{m}_u$ 表示以 $1$ 为根时 $u$ 到子树内每个点的距离总和，$s{d}_u$ 表示 $u$ 为整棵树的根时到每个节点的距离总和，$\text{dis}(u,v)$ 表示树上 $u$ 到 $v$ 的距离。这些都可以 dfs 和倍增求 lca 得到。

对于离 $L$ 更近的蓝色部分，我们用 $s{d}_L$ 减去 $Mid$ 子树内所有点到 $L$ 的距离：$Mid$ 子树内的所有点先全部走到 $Mid$（$su{m}_{Mid}$），然后 $si{z}_{Mid}$ 个点一起从 $Mid$ 走到 $L$（$si{z}_{Mid}\times \text{dis}(L,Mid)$）。
$$an{s}_L=s{d}_L-(su{m}_{Mid}+\text{dis}(L,Mid)\times si{z}_{Mid})$$

对于离 $R$ 更近的红色部分，我们用 $s{d}_R$ 减去 $Mid$ 子树之外的所有点到 $R$ 的距离，两个部分反过来：
$$an{s}_R=s{d}_R-[(s{d}_{Mid}-su{m}_{Mid})+\text{dis}(R,Mid)\times (n-si{z}_{Mid})]$$

我们要从 $R$ 跳到 $Mid$，理应是路径的中点 $\frac{\text{dis}(L,R)}{2}$，但是如果 $Mid$ 刚好在 $\text{lca}(L,R)$ 上，根据上面推的式子，$s{d}_{Mid}-su{m}_{Mid}$ 直接归零，并不包含我们想要的 $Mid$ 到 $L$ 的路径和。因此我们考虑靠近 $R$ 推一位，我们取 $Mid=\lfloor \frac{\text{dis}(L,R)-1}{2}\rfloor$。

代码

#include<bits/stdc++.h>
#pragma GCC optimise(2)
#pragma GCC optimise(3,"Ofast","inline")
using namespace std;
#define ll long long
const ll N=1e5+9,mod=1e9+7;
ll n,m;
ll idx,head[N];
struct edge
{ll to,next;
}e[N<<1];
void addedge(ll u,ll v)
{idx++;e[idx].to=v;e[idx].next=head[u];head[u]=idx;
}
ll dep[N],f[N][19];
ll siz[N],sum[N],sd[N];
//子树大小 1为根i到子树所有节点距离和 i为根到所有节点的距离和 
void dfs(ll u,ll fa)
{dep[u]=dep[fa]+1;siz[u]=1;f[u][0]=fa;for(int i=1;(1<<i)<=dep[u];i++)f[u][i]=f[f[u][i-1]][i-1];for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;dfs(v,u);siz[u]+=siz[v];sum[u]+=sum[v]+siz[v];}
}
void dfs2(ll u,ll fa)
{for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;sd[v]=sd[u]+(n-siz[v])-siz[v];//把v提到根节点 dfs2(v,u);}
}
ll lca(ll x,ll y)
{if(dep[x]<dep[y])swap(x,y);for(int i=18;i>=0;i--)if(dep[x]-(1<<i)>=dep[y])x=f[x][i];if(x==y)return x;for(int i=18;i>=0;i--){if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}}return f[x][0];
}
ll dis(ll u,ll v)
{return dep[u]+dep[v]-2*dep[lca(u,v)];
}
ll jump(ll u,ll k)
{ll j=0;while(k){if(k&1)u=f[u][j];k>>=1;j++;}return u;
}
int main()
{scanf("%lld",&n);for(int i=1;i<n;i++){ll u,v;scanf("%lld%lld",&u,&v);addedge(u,v);addedge(v,u);}dfs(1,0);sd[1]=sum[1];dfs2(1,0);scanf("%lld",&m);for(int i=1;i<=m;i++){ll L,R;scanf("%lld%lld",&L,&R);if(L==R){printf("%lld\n",sd[L]);continue;}if(dep[L]>dep[R])swap(L,R);//L浅R深 R开始跳 ll Dis=dis(L,R),Mid=jump(R,(Dis-1)/2);//跳到中点Mid lca(L,mid)就是通往1的路径交汇点 ll ans1=sd[L]-sum[Mid]-dis(L,Mid)*siz[Mid];ll ans2=sd[R]-(sd[Mid]-sum[Mid])-dis(R,Mid)*(n-siz[Mid]);printf("%lld\n",ans1+ans2);}return 0;
}