【DS】CF765F Souvenirs

想了 2 天好像还是只会带 log 的。

一上来，这不就是 #246. 【UER #7】套路，但第二个做法不是很好做。由于第一个做法是 \(O(n^2)\) 的，那就分块（块长为 \(T\)）。整块的贡献很好做，对于每个块维护个值域前后驱就可以合并，大致就是记 \(f[l][r]\) 为块 l 与块 r 间的贡献，然后 \(f[l][r]=\min(f[l+1][r],f[l][r-1],cal(l,r))\)，其中 \(cal(l,r)\) 可以 \(O(T)\) 求。但散块不是很好维护。

然后我就弃了，冲了 2 个做法，回滚莫队+set，分块+主席树。带 log 显然冲不过。

滚回来继续想，发现贡献可以再拆。拆成 2 个散块分别与整块的贡献以及 2 个散块合并起来的贡献。前者也是可以通过类整块的思路维护，合并的话就只需要计算单点与一个整块的贡献（可以通过维护每个块的值域链表 \(O(1)\) 求出），但是这个东西写起来很烦！细节多的要死。散块间相互的贡献怎么办？把其当成一个块暴力排序的话就要带 log，假如用链表形式的话离散化后就是 \(O(n)\) 的。二者显然不行。考虑假如能够不排序，而是变成直接合并，那就是 \(O(T)\) 的。那么我们直接对于原来的块排序之后再类归并排序维护好像就行了，想到这转念一想前面的 cal，发现根本不用链表形式维护，也只需要类归并即可。排序复杂度 \(O(\dfrac{n}{T}T\log T)\)，即 \(O(n\log n)\)。

复杂度 \(O(n\log n+(\dfrac{n}{T})^2T+mT)\)，\(T\) 取根号即可。

AC Code

//qwq
#include 
using namespace std;
int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}
void pr(int x) {
	int f=1,tot=0; static int st[30];
	if(x<0) x=-x,f=-1;
	while(x) st[++tot]=x%10,x/=10;
	if(!tot) putchar('0');
	else for(int i=tot;i>=1;i--) putchar(st[i]+'0');
}
#define N (int)(1e5+5)
#define M 320
#define inf (int)(2e9)
vectorvec[M],tmp,tmp2,tmp3;
int n,m,bl,b[N],lsh[N],cnt[N],LLas[M][N],NNex[M][N],
a[N],id[N],L[M],R[M],f[M][M],ff[N][M],fff[M][N],tf[M][M],g[M];

bool cmp(const int &x,const int &y) {
	return a[x]=1;i--) {
		if(cnt[i]) qwq=i;
		NNex[x][i]=qwq;
	}
	vec[x].clear();
	for(int i=L[x];i<=R[x];i++) vec[x].push_back(i);
	sort(vec[x].begin(),vec[x].end(),cmp); 
	g[x]=inf;
	for(int i=L[x];i<=R[x];i++)
		for(int j=i+1;j<=R[x];j++)
			g[x]=min(g[x],abs(a[i]-a[j]));
}

int ssolve(int x,int y) {
	int res=inf;
	if(LLas[y][b[x]]!=-1) res=abs(a[x]-lsh[LLas[y][b[x]]]);
	if(NNex[y][b[x]]!=n+1) res=min(res,abs(lsh[NNex[y][b[x]]]-a[x]));
//	printf("%d %d %d %d %d\n",x,y,L[y],R[y],res);
	return res;
}

int solve(const vector&x,const vector&y) {
	if(!x.size()||!y.size()) return inf;
	tmp.clear();
	int nw1=0,nw2=0,res=inf;
	while(1) {
		if(a[x[nw1]]=x.size()||nw2>=y.size()) break;
	}
	while(nw1=x) tmp2.push_back(vec[id[x]][i]);
	//	puts("");
		for(int i=0;i=1;i--) {
		memset(tf,0x3f,sizeof(tf));
		int qwq=R[i]-L[i]+1;
		for(int j=1;j=L[i];j--) ff[j][i+1]=min(ff[j+1][i+1],min(tf[j-L[i]+1][R[i]-L[i]+1],ssolve(j,i+1)));
		for(int j=i+2;j<=id[n];j++) {
			for(int k=R[i];k>=L[i];k--) {
				ff[k][j]=min(ff[k+1][j],min(ff[k][j-1],ssolve(k,j)));
			}
		} 
	}
	// fff[i][j]:[L[i],j] 块到点 
	for(int i=id[n]-1;i>=1;i--) {
		memset(tf,0x3f,sizeof(tf));
		int qwq=R[i]-L[i]+1;
		for(int j=1;j