题解 CF1039E 【Summer Oenothera Exhibition】
command_block
·
·
题解
题意 : (和原题面本质相同)
给定一个长度为 n 的序列。
接下来 q 组询问，每次给出一个常数 k。
求最少把序列分为多少段使得每段序列中数的极差不超过 k。
允许离线。
------------
首先不难针对单组询问想到暴力 : 每次贪心划分，能不分就不分。正确性较为显然。
似乎难以得出更强的性质，考虑优化这个过程。
设 $t[i]$ 为第 $i$ 个位置分出一段，最远能到达哪里。
这样，若在 $(i,t[i])$ 之间连边，$dis(1,n+1)$ 就是答案。
这些边会新成一棵树，不难想到使用 $\rm LCT$ 来维护。
接下来，将询问离线，按极差约束从小到大来回答。
显然 $t[i]$ 会逐渐变大，但是总变化次数可能高达 $O(n^2)$，不能承受。
考虑根号分治。
若 $t[i]\leq \sqrt{n}$ 才使用 $\rm LCT$ 维护。
由于 $t$ 只会增加，这部分的总变化次数为 $O(n\sqrt{n})$。
这样会形成森林而非单棵树，可以发现，由于超过 $\sqrt{n}$ 的边才会导致断开，森林中树的总数不超过 $O(\sqrt{n})$。
我们利用 $\rm LCT$ 每次跳过一棵树。
接下来，就是 $O(n\sqrt{n})$ 个单点求解 $t$ 的询问。
这里使用 $\rm ST$ 表配合二分，写成倍增常数会小一些。
总复杂度 $O(n\sqrt{n}\log n)$。
下面是实现细节 :
- $t[i]\leq \sqrt{n}$ 的 $O(n\sqrt{n})$ 次变化如何找到。
每次 $t[i]$ 变化后，二分出下一次变化所需的极差,然后用 `vector` 来分配给每个询问。
- 怎么用 $\rm LCT$ 每次跳过一棵树。
$\rm LCT$ 中编号大的点总是为父亲，这样 $\access$ 一下就得到我们想要的路径了。
```cpp
#include<algorithm>
#include<vector>
#include<cstdio>
#define pb push_back
#define ll long long
#define MaxN 101000
using namespace std;
int read(){
int X=0;char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
struct LCT{
struct Node{int l,r,f,c;}a[MaxN];
void Init(int n)
{for (int i=1;i<=n;i++)a[i].c=1;}
inline bool nrt(int u)
{return a[a[u].f].l==u||a[a[u].f].r==u;}
inline void up(int u)
{a[u].c=a[a[u].l].c+a[a[u].r].c+1;}
void rot(int u)
{
int fa=a[u].f,gf=a[fa].f;
if (a[gf].l==fa)a[gf].l=u;
if (a[gf].r==fa)a[gf].r=u;
a[a[fa].f=u].f=gf;
if (a[fa].l==u){
a[a[fa].l=a[u].r].f=fa;
a[u].r=fa;
}else {
a[a[fa].r=a[u].l].f=fa;
a[u].l=fa;
}up(fa);up(u);
}
void splay(int u){
while(nrt(u)){
int fa=a[u].f,gf=a[fa].f;
if (nrt(fa)&&(a[fa].l==u)==(a[gf].l==fa))
rot(fa);
rot(u);
}
}
void access(int u){
int sav=u;
for (int v=0;u;u=a[v=u].f)
{splay(u);a[u].r=v;up(u);}
splay(sav);
}
int findrt(int u){
access(u);
while(a[u].l)u=a[u].l;
splay(u);return u;
}
void link(int u,int v)
{access(u);a[u].f=v;}
void cut(int u,int v){
access(u);splay(v);
a[u].f=a[v].r=0;up(v);
}
}T;
const int INF=2100000000;
int x[MaxN];
struct ST
{
int t0[20][MaxN],t1[20][MaxN],lg2[MaxN];
void Init(int n,int *x){
for (int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
reverse(lg2+1,lg2+n+1);
for (int i=1;i<=n;i++)
t0[0][i]=t1[0][i]=x[i];
for (int j=0;(1<<j+1)<=n;j++)
for (int i=1;i+(1<<j+1)-1<=n;i++){
t0[j+1][i]=min(t0[j][i],t0[j][i+(1<<j)]);
t1[j+1][i]=max(t1[j][i],t1[j][i+(1<<j)]);
}
}
int qry(int u,int lim,int &l,int &r){
l=INF;r=0;
for (int k=lg2[u];~k;k--)
if (k<=lg2[u]&&max(r,t1[k][u])-min(l,t0[k][u])<=lim){
r=max(r,t1[k][u]);
l=min(l,t0[k][u]);
u+=(1<<k);
}
return u;
}
int qry2(int u,int lim){
int l,r;
return qry(u,lim,l,r);
}
}S;
struct Qry{int l,p;}sq[MaxN];
bool cmpQ(const Qry &A,const Qry &B)
{return A.l<B.l;}
vector<int> tb[MaxN];
int n,BS,q,t[MaxN];
void upd(int u,int lim)
{
if (t[u])T.cut(u,t[u]);
int l,r,sav=S.qry(u,lim,l,r);
t[u]=sav;
if (t[u]-u<=BS){
T.link(u,t[u]);
if (t[u]<=n){
int nxt=max(r,x[t[u]])-min(l,x[t[u]]),
tim=lower_bound(sq+1,sq+q+1,(Qry){nxt,0},cmpQ)-sq;
if (tim<=q)tb[tim].pb(u);
}
}
}
int solve(int i,vector<int> &b)
{
int lim=sq[i].l;
for (int i=0;i<b.size();i++)
upd(b[i],lim);
b.clear();
int ret=0;
for (int p=1;p<=n;){
int rt=T.findrt(p);
ret+=T.a[rt].c-1;
if (rt>n)break;
p=S.qry2(rt,lim);ret++;
}return ret;
}
int w,ans[MaxN];
int main()
{
n=read();w=read();q=read();
while(BS*BS<n)BS++;
for (int i=1;i<=n;i++)x[i]=read();
x[n+1]=INF;S.Init(n+1,x);
for (int i=1;i<=q;i++){
sq[i].l=w-read();
sq[i].p=i;
}sort(sq+1,sq+q+1,cmpQ);
T.Init(n+1);
for (int i=1;i<=n;i++)tb[1].pb(i);
for (int i=1;i<=q;i++)
ans[sq[i].p]=solve(i,tb[i]);
for (int i=1;i<=q;i++)
printf("%d\n",ans[i]-1);
return 0;
}
```
听说还有 $O(n^{5/3}+n^{4/3}\log n)$ 的做法? Orz