THUPC2024 古明地枣的袜子

古明地枣是谁？

题意

有一个长度为 $n$ 的序列。

给出 $n$ 个操作 $(x_i,y_i)$，每个操作为将 $a_1,a_2,\cdots,a_{x_i}$ 全部加上 $y_i$。

有 $m$ 次相互独立的询问，询问若 $a$ 初始全为 $0$，则做完操作 $(x_l,y_l),(x_{l+1},y_{l+1}),\cdots,(x_r,y_r)$ 后全局最大值为多少。

数据范围：$n,m\le 5\times 10^5$，时限 10s。

题解

（下面在计算时间复杂度时认为 $n,m$ 同级。）

zz 神仙讲的，虽然我没听。

观察数据范围和时限，首先排除单双 $\log$，因为这俩最多 2s。

猜测是个根号算法，那我们需要想办法分块。

下设块长为 $B$。

常见的分块要么对 $a$ 分，要么对操作分。

我们单纯对 $a$ 分会出现一堆操作挤在一个块内的情况，而对操作分块又可能出现块内操作太过分散的问题。

于是人类智慧地，把两者结合到一起，先将操作按 $x$ 排序后再分块，同时记录操作的时间戳。

这样子可以规避上面两种可能导致复杂度退化的情况，看上去就要优秀一些。

有了分块，接下来考虑怎么维护。

注意到我们询问是全局的，如果考虑每个块统计，那么想要做到一个根号就必须 $\mathcal{O}(1)$ 处理每个块的询问。

这样我们不得不进行预处理，设预处理出块 $b$ 在询问 $[l,r]$ 时的最大值为 $f_{b,l,r}$。

直接处理会发现我们连数组都存不下，肯定爆炸了。

但是注意到对于某个块内，有大量的询问是本质相同的，实际上一个块内最多只有 $\dfrac{B(B-1)}{2}$ 种本质不同的询问。

这样我们可以把 $l,r$ 离散化为块内对应的操作按照时间戳排序后的排名，空间复杂度就降下来可以存储了。

不过即使如此，怎么算出 $f$ 也是个关键的问题。

如果你想，你可以暴力套一个 $\log$，用线段树等 DS 简单维护一下，然后把 $B$ 平衡一下取到 $\mathcal{O}(n\sqrt{n\log n})$ 的时间复杂度。

但是，太烂了，我们需要严格根号算法。

注意到我们需要把操作排序之后才能够解决一个块内的答案。

这个时候人类智慧地意识到我们可以使用 归并排序。

在归并排序的分治过程中处理答案，看看怎么分治。

对于一个分治区间 $[l,r]$，它表示我们处理按照 $x$ 排序后的操作 $l$ 到 $r$。

此时我们能够得到两个更小区间里的 $f$，此时 $f_{i,j}$ 表示区间内时间戳排名为 $i$ 到 $j$ 操作做完后的最大值。

现在我们枚举 $f_{i,j}$，计算当前这个区间的答案。

分类讨论如何转移：

• 如果之前的最大值位于右半区间，此时它的所有贡献已经被算完，左边的其它操作无法对其产生贡献，直接令 $f_{i,j}$ 和右半最大值取 $\max$ 即可。
• 如果之前的最大值位于左半区间，此时右半区间的操作可以对其产生贡献，利用前缀和可以简单计算出贡献，令 $f_{i,j}$ 和加上贡献的左半最大值取 $\max$ 即可。

对于一个 $i,j$，我们意识到其对应的左右区间的情况是不同的。

详细来说，我们可以设在时间戳排名为 $[i,j]$ 的操作中，原本位于左半区间的为左半区间排名为 $[il,jl]$，同理设右半区间为 $[ir,jr]$，这个可以在归并排序时计算。

然后我们就可以利用 $il,jl,ir,jr$ 来转移 $f_{i,j}$ 了。

分析分治的时间复杂度会发现 $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n^2)=\mathcal{O}(n^2)$，而我们对每个块做此操作，总时间复杂度为 $\mathcal{O}(nB)$。

结合询问的总时间复杂度 $\mathcal{O}(\dfrac{n^2}{B})$，取 $B=\sqrt{n}$ 时最优，为 $\mathcal{O}(n\sqrt{n})$。

然后就是细节了：

• 注意到对于一个区间 $[l,r]$，如果一整个区间的操作的 $x$ 均相同，那么我们不能够直接用其信息转移更大的区间，因为更大的区间可能包含更多操作。

考虑下面一个例子：

在分治时左半区间有操作 $1,2$ 对 $a_1$ 进行修改，而右半区间有操作 $3$ 同样对 $a_1$ 进行修改。

在合并求解区间 $[1,3]$ 时，不能够取 $[3,3]$ 的最大值来转移，因为此时三个操作都被执行了，需要直接得到 $a_1$ 的最终结果。

假设操作 $3$ 令 $a_1$ 变得很大，此时我们的 $f$ 可能直接取到仅操作操作 $3$ 后 $a_1$ 的值，导致答案错误。

这个东西实现的时候稍微小心一点即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int N=500010,B=666,INF=1e9;
struct operation
{
	int x,y,t;
	bool operator < (operation oth) {return x<oth.x;}
}op[N],sorted[N];
ll f[B+10][B+10],tmp[B+10][B+10];/*预处理答案*/
ll s[N];/*操作的y的前缀和，分治时需要动态处理*/
int now;
int pl[N],pr[N];
template<typename Type>inline void chkmax(Type &a,Type b){if(a<b)a=b;return;}
int change[N],cs[N];/*见正文细节部分*/
void solve(int l,int r)
{
	if(l==r)
	{
		f[l-now][l-now]=change[l]?op[l].y:-INF;
		return;
	}
	int mid=(l+r)>>1;
	solve(l,mid),solve(mid+1,r);
	s[mid]=0;
	for(int i=mid+1;i<=r;i++)s[i]=s[i-1]+op[i].y;
	pl[l-1]=l-1,pr[l-1]=mid;
	for(int i=l,j=mid+1,k=l;i<=mid||j<=r;k++)
	{
		if(j>r||(i<=mid&&op[i].t<op[j].t))sorted[k]=op[i],i++;
		else sorted[k]=op[j],j++;
		pl[k]=i-1,pr[k]=j-1;
	}
	for(int i=l;i<=r;i++)op[i]=sorted[i];
	for(int i=l;i<=mid;i++)for(int j=i;j<=mid;j++)tmp[i-now][j-now]=f[i-now][j-now];
	for(int i=mid+1;i<=r;i++)for(int j=i;j<=r;j++)tmp[i-now][j-now]=f[i-now][j-now];
	for(int i=l;i<=r;i++)
	{
		for(int j=i;j<=r;j++)
		{
			/*计算f[i][j]*/
			f[i-now][j-now]=-INF;
			int il=pl[i-1]+1,ir=pr[i-1]+1,jl=pl[j],jr=pr[j];
			if(cs[mid]-cs[l-1])chkmax(f[i-now][j-now],tmp[il-now][jl-now]+s[jr]-s[ir-1]);
			if(cs[r]-cs[mid])chkmax(f[i-now][j-now],tmp[ir-now][jr-now]);
		}
	}
	return;
}
struct question{int l,r;ll ans=-INF;}q[N];
int n,m;
ll suf[N];/*后缀和*/
int rt[N];/*t为i的op的编号*/
int rk[N];/*对应在此块内的排名*/
inline void Calc_Block(int l,int r)
{
	now=l-1;
	for(int i=l;i<=r;i++)for(int j=i;j<=r;j++)f[i-now][j-now]=-INF;
	solve(l,r);
	suf[0]=0;
	for(int i=1;i<=n;i++)suf[i]=suf[i-1]+(rt[i]>r?op[rt[i]].y:0);/*把后面的块的操作预处理*/
	rk[1]=1;
	for(int i=1,j=l;i<=n;i++)
	{
		if(i==op[j].t)j++,rk[i+1]=rk[i]+1;
		else rk[i+1]=rk[i];
	}
	for(int i=1;i<=m;i++)if(cs[r]-cs[l-1])chkmax(q[i].ans,f[rk[q[i].l]][rk[q[i].r+1]-1]+suf[q[i].r]-suf[q[i].l-1]);
	return;
}
template<typename Type>inline void r(Type &x)
{
	x=0;
	char c=getchar();
	bool f=c=='-';
	while(c<'0'||c>'9')c=getchar(),f|=c=='-';
	while(c>='0'&&c<='9')x*=10,x+=c-'0',c=getchar();
	if(f)x=-x;
	return;
}
int main()
{
	r(n),r(m);
	for(int i=1;i<=n;i++)r(op[i].x),r(op[i].y),op[i].t=i;
	for(int i=1;i<=m;i++)r(q[i].l),r(q[i].r);
	sort(op+1,op+n+1);
	n++,op[n]={n,0,n+1};//UKE
	for(int i=1;i<=n;i++)change[i]=op[i-1].x!=op[i].x,cs[i]=cs[i-1]+change[i];
	for(int i=1;i<=n;i++)rt[op[i].t]=i;
	for(int i=1,j=B;i<=n;i+=B,j+=B)Calc_Block(i,min(j,n));
	for(int i=1;i<=m;i++)printf("%lld\n",q[i].ans);
	return 0;
}

鸣谢

参考文章：https://www.cnblogs.com/peiwenjun/p/18257226 ，膜拜 peiwenjun 佬。

代码实现是我自己敲的，但是对着佬的代码看了半天所以敲得都一样了。

本题解并非正解的分块+分治，学习正解请看其他题解。

双倍经验

P13827 P10540 题目一模一样，后者数据较水。

题意

给定 $n$ 个操作，每次询问求在执行 $l\sim r$ 的操作后全局最大值，操作为将 $a_1\sim a_x$ 加 $y$，可为负数。

做法

很容易想到 $O(n \sqrt n\log n)$ 的莫队加线段树做法，理论复杂度只可以过这题的，但是由于线段树的超大常数，直接 T 飞了。

原本还想尝试分块代替线段树，可以做到 $O(n^{\frac{7}{4}})$，但是感觉这题不会这么简单，没有去试，直接去学正解了，结果写完发现有人写莫队过了，于是又想了一下分块，发现普通分块确实不行，但是分块 plus 好像可行。

分块 plus 就是可以做到 $O(n^{\frac{1}{3}})$ 修改和查询的分块，线段树1的板题写这个比大部分线段树都快，具体可以看这篇文章，这里我简单讲一下。普通分块是直接讲序列分块，但我们其实可以把每一块再次分块（理论上可以一直分下去，但常数会越来越大），每次更新修改所在小块和大块的贡献，查询直接查大块，假设小块块长为 $b$，大块块长为 $B$，则这个分块的复杂度为 $O(\frac{n}{B}+\frac{B}{b}+b)$ 取 $B=b=n^{\frac{1}{3}}$ 时复杂度最优。

接下来看这道题，注意到前缀加只会改变 $x$ 所在块的最大值位置，其余只要在这个块上打一个 tag，然后查询时从后往前扫累加上每个块的 tag 即可。

设小块块长为 $B$，大块块长为 $B^2$，则复杂度为 $O(nB\sqrt n+\frac{n^2}{B^2})$，考虑到除法操作较慢， $B$ 取 $2$ 的幂次时可用位运算代替除法操作，综合考虑 $B$ 取 $8$ 最优。但这样任然无法通过，所以直接循环展开，最终代码跑得飞快，优于大部分正解。

但到这里交上去还是会WA，原因是在处理最后面的散块时会统计到 $n$ 以外的数，如果答案小于 $0$ 就会输出 $0$ 。我们将全局的操作单独拎出来，这样若答案小于 $0$ ，则我们可以取第 $n$ 个数使得答案为 $0$ ，最后加上全局的操作即可。

这样我们终于用暴力通过了这题，并且因为正解的超大常数，这种方法是优于大部分正解的。

代码

#include<bits/stdc++.h>
#define x first
#define y second
//不要乱开long long
#define ll long long
#define inf 1000000000000000000
#define max(A,B) (A)>(B) ? (A) : (B)
using namespace std;
const int N=5e5+10;
int n,m,pos[N],B=750;
ll w[N],tag1[(N>>3)+10],tag2[(N>>6)+10],mx1[(N>>3)+10],mx2[(N>>6)+10],ans[N],sum[N];
pair <int,int> a[N];
//莫队排序
struct node{
	int l,r,id;
	bool operator < (const node &t) const{
		return pos[l]==pos[t.l] ? ((pos[l]&1) ? r<t.r : r>t.r) : pos[l]<pos[t.l];
	}
}q[N];
//循环展开
#define c(p) tg+=w[p],mx=max(mx,tg)
#define cc(p) mx=max(mx,mx1[p]+tg),tg+=tag1[p]
#define ccc(p) mx=max(mx,mx2[p]+tg),tg+=tag2[p]
void update(int x,int y){
  //下标从0开始，便于分块。
	--x;
	w[x]+=y;
	tag1[x>>3]+=y;
	tag2[x>>6]+=y;
	ll tg=0,mx=-inf;
	int i=(x>>3)<<3;
	c(i+7),c(i+6),c(i+5),c(i+4),c(i+3),c(i+2),c(i+1),c(i);
	mx1[x>>3]=mx;
	tg=0,mx=-inf,i=(x>>6)<<3;
	cc(i+7),cc(i+6),cc(i+5),cc(i+4),cc(i+3),cc(i+2),cc(i+1),cc(i);
	mx2[x>>6]=mx;
}
ll query(){
	ll mx=-inf,tg=0,i=(n-1)>>6;
	for(;i>=7;i-=8) ccc(i),ccc(i-1),ccc(i-2),ccc(i-3),ccc(i-4),ccc(i-5),ccc(i-6),ccc(i-7);
	for(;i>=0;--i) ccc(i);
	return mx;
}
void add(int i){
	update(a[i].x,a[i].y);
}
void del(int i){
	update(a[i].x,-a[i].y);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y,pos[i]=(i-1)/B+1;
		if(a[i].x==n) sum[i]+=a[i].y,a[i].y=0;
		sum[i]+=sum[i-1];
	}
	for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].id=i;
	sort(q+1,q+m+1);
	int L=1,R=0;
  //莫队板子
	for(int i=1;i<=m;i++){
		while(R<q[i].r) add(++R);
		while(L>q[i].l) add(--L);
		while(R>q[i].r) del(R--);
		while(L<q[i].l) del(L++);
		ans[q[i].id]=max((ll)0,query())+sum[q[i].r]-sum[q[i].l-1];
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
	return 0;
}

P13827提交记录 P10540提交记录