专栏文章

题解：P10540 [THUPC 2024 决赛] 古明地枣的袜子

nningyy
P10540题解参与者 9已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@mio088v2
此快照首次捕获于
2025/12/02 11:14
3 个月前
此快照最后确认于
2025/12/02 11:14
3 个月前
查看原文
本题解并非正解的分块+分治，学习正解请看其他题解。

双倍经验

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

题意

给定 nn 个操作，每次询问求在执行 l∼rl\sim r 的操作后全局最大值，操作为将 a1∼axa_1\sim a_x 加 yy，可为负数。

做法

很容易想到 O(nnlog⁡n)O(n \sqrt n\log n) 的莫队加线段树做法，理论复杂度只可以过这题的，但是由于线段树的超大常数，直接 T 飞了。
原本还想尝试分块代替线段树，可以做到 O(n74)O(n^{\frac{7}{4}})，但是感觉这题不会这么简单，没有去试，直接去学正解了，结果写完发现有人写莫队过了，于是又想了一下分块，发现普通分块确实不行，但是分块 plus 好像可行。
分块 plus 就是可以做到 O(n13)O(n^{\frac{1}{3}}) 修改和查询的分块，线段树1的板题写这个比大部分线段树都快，具体可以看这篇文章，这里我简单讲一下。普通分块是直接讲序列分块，但我们其实可以把每一块再次分块（理论上可以一直分下去，但常数会越来越大），每次更新修改所在小块和大块的贡献，查询直接查大块，假设小块块长为 bb，大块块长为 BB，则这个分块的复杂度为 O(nB+Bb+b)O(\frac{n}{B}+\frac{B}{b}+b) 取 B=b=n13B=b=n^{\frac{1}{3}} 时复杂度最优。
接下来看这道题，注意到前缀加只会改变 xx 所在块的最大值位置，其余只要在这个块上打一个 tag，然后查询时从后往前扫累加上每个块的 tag 即可。
设小块块长为 BB，大块块长为 B2B^2，则复杂度为 O(nBn+n2B2)O(nB\sqrt n+\frac{n^2}{B^2})，考虑到除法操作较慢， BB 取 22 的幂次时可用位运算代替除法操作，综合考虑 BB 取 88 最优。但这样任然无法通过，所以直接循环展开，最终代码跑得飞快，优于大部分正解。
但到这里交上去还是会WA，原因是在处理最后面的散块时会统计到 nn 以外的数，如果答案小于 00 就会输出 00 。我们将全局的操作单独拎出来，这样若答案小于 00 ，则我们可以取第 nn 个数使得答案为 00 ，最后加上全局的操作即可。
这样我们终于用暴力通过了这题，并且因为正解的超大常数，这种方法是优于大部分正解的。

代码

CPP
#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提交记录

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...