专栏文章

TJ For [Ynoi2007] rgxsxrs

TTiffake
P7447题解参与者 3已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@mio4lum1
此快照首次捕获于
2025/12/02 13:16
3 个月前
此快照最后确认于
2025/12/02 13:16
3 个月前
查看原文

前言

第一次写 Ynoi 的题解，并且成功卡进最优解第一页。

题意

标题即题意：range greater than x subtract x,range sum。

思路

看到这种东西既和值域有关，又和原序列有关，无疑需要使用两种数据结构维护。
于是先考虑树套树，发现有区间修改，打不了 tag，pass。
再考虑按值域分块，块长暂定为 BB，内层再用平衡树维护在当前值域块的数。
对一个块内的修改可以分成一下几种情况：
  1. 如果当前区间的最大值小于 xx 就不管它。
  2. 如果当前区间的最小值 ≥x+L\ge x+L 可以直接打标记处理，LL 是当前块的下界。
  3. 除了这两种情况，只能暴力将这些数减去 xx 并丢到某个块去。
毫无疑问，这样写的复杂度直接飞起来。
思考上面的做法失败在了什么方面。
先假定 n,mn,m 同阶。每次修改时，如果只遇到前两种情况，那么复杂度是 O(VB)O(\frac V B)，如果是第三种情况，那么每个数都需要用 O(log⁡n)O(\log n) 的时间丢到某个块中，最多会丢 O(VB)O(\frac V B) 次，并且会导致最后所有数全部都处于前几个块，然后就只能几乎纯暴力了。
这说明了两个事：
  1. 复杂度和块长似乎没多大关系，所以可以开大一点。
  2. 但是较前的块不能太长了，这会使算法退化成暴力。
于是考虑一种很新的分块方式，倍增分块。
具体说，就是把值域在 [Pi,Pi+1)[P^i,P^{i+1}) 的数搞到一个块里面。
如果是这样写，重新分析下复杂度。
每次修改时，如果只遇到前两种情况，那么最坏情况下复杂度是 O(log⁡nlog⁡V)O(\log n\log V)，如果是第三种情况，那么每个数都需要用 O(log⁡n)O(\log n) 的时间丢到某个块中，最多会丢 O(log⁡V)O(\log V) 次，并且最后只会让所有的数变成 11，我们并不需要对其进行操作。
发现时间复杂度 O(nlog⁡nlog⁡V)O(n\log n\log V) 好像是对的，但是忽略了空间复杂度 O(nlog⁡n)O(n\log n)，平衡树每次操作都会消耗掉树高的栈空间，以及平衡树的巨大常熟。
不过还是给一份可以过掉前 4 个包的代码。
好像已经无法进一步优化了，总不能让平衡树矮一点，再让它快一点吧？
事实是真的可以让它矮一点。
平衡树（WBLT）的底层叶子长得很不优雅，占用了大量空间，于是可以考虑在维护的区间大小 ≤log⁡n\le \log n 时直接在原序列上分块而不是继续分叉来优化它。
当然，这样只是用时间换了空间，平衡树的常数问题还是没有解决。考虑直接用常数较小线段树代替，此时需要额外维护区间属于当前值域块的数的数量。
然后就可以在大量的卡常和调参后通过这道题了。

代码

CPP
#include<bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
#define ls k<<1
#define rs k<<1|1
using namespace std;
const int N=5e5+1,M=2e5+1,B=10,P=14,G=8;//这是一组可以卡到最优解第一页的参数
//M表示线段树节点数量，B表示线段树底层分块的块长，P表示倍增分块的底数，G表示倍增分块的块数
struct node{
	int lz,c,mx,mn;//c表示当前区间属于当前值域块的数量
	ll s;//注意部分开long long
}s[G][M];
int n,m,w,v,x,y,X,Y,a[N];
ll lans,L[N];//L表示每个值域块的下界
inline int getb(ll x){//快速查询每个数处于哪个值域块
	return upper_bound(L,L+G,x)-L-1;
}
inline void subnode(int w,int k,int v){
	s[w][k].mx-=!!s[w][k].c*v,s[w][k].mn-=!!s[w][k].c*v,s[w][k].s-=(ll)s[w][k].c*v,s[w][k].lz+=v;
}
inline void pushup(int w,int k){
	s[w][k].mx=max(s[w][ls].mx,s[w][rs].mx),s[w][k].mn=min(s[w][ls].mn,s[w][rs].mn);
	s[w][k].c=s[w][ls].c+s[w][rs].c,s[w][k].s=s[w][ls].s+s[w][rs].s;
}
inline void pushdown(int w,int k){
	if(s[w][k].lz)subnode(w,ls,s[w][k].lz),subnode(w,rs,s[w][k].lz),s[w][k].lz=0;
}
inline void b_pushdown(int w,int l,int r,int v){
	if(!v)return;
	for(int i=l;i<=r;i++)if(L[w]<=a[i]&&a[i]<L[w+1])a[i]-=v;
}//向线段树底层的块下传标记
inline void b_pushup(int w,int k,int l,int r){
	s[w][k].c=s[w][k].mx=s[w][k].s=0,s[w][k].mn=1e9;
	for(int i=l;i<=r;i++)if(L[w]<=a[i]&&a[i]<L[w+1])
		s[w][k].c++,s[w][k].s+=a[i],s[w][k].mx=max(s[w][k].mx,a[i]),s[w][k].mn=min(s[w][k].mn,a[i]);
}//由线段树底层的块上传答案
inline void ins(int w,int k,int l,int r,int x,int v){
	if(r-l<B){//注意需要先pushdown
		b_pushdown(w,l,r,s[w][k].lz),s[w][k].lz=0;
		return a[x]=v,b_pushup(w,k,l,r);
	}
	pushdown(w,k);
	if(x<=mid)ins(w,ls,l,mid,x,v); 
	else ins(w,rs,mid+1,r,x,v);
	pushup(w,k);
}//将某个数插入到某个值域块的线段树中
inline void b_sub(int w,int l,int r,int v){
	for(int i=l;i<=r;i++)if(L[w]<=a[i]&&a[i]<L[w+1]&&a[i]>v)
		a[i]-=v,a[i]<L[w]&&(ins(getb(a[i]),1,1,n,i,a[i]),0);
}//暴力对某个线段树底层的块进行修改
inline void b_ask(int w,int l,int r){
	for(int i=l;i<=r;i++)if(L[w]<=a[i]&&a[i]<L[w+1])
		lans+=a[i],Y=min(Y,a[i]),X=max(X,a[i]);
}//暴力对某个线段树底层的块进行查询
void sub(int k,int l,int r){
	if(s[w][k].mx<=v)return;//最大值还小于x的就可以直接跳过
	if(x<=l&&r<=y&&s[w][k].mn-v>=L[w])return subnode(w,k,v);//最小值减v之后如果还在当前值域块就可以打标记
	if(r-l<B){
		b_pushdown(w,l,r,s[w][k].lz),s[w][k].lz=0;
		return b_sub(w,max(l,x),min(r,y),v),b_pushup(w,k,l,r);
	}
	pushdown(w,k);
	if(x<=mid)sub(ls,l,mid);
	if(y>mid)sub(rs,mid+1,r);
	pushup(w,k);
}
void ask(int k,int l,int r){
	if(!s[w][k].c)return;//当前区间没有在当前值域块的数可以直接跳过
	if(x<=l&&r<=y)return lans+=s[w][k].s,Y=min(Y,s[w][k].mn),X=max(X,s[w][k].mx),void();
	if(r-l<B){
		b_pushdown(w,l,r,s[w][k].lz),s[w][k].lz=0;
		return b_ask(w,max(l,x),min(r,y));
	}
	pushdown(w,k);
	if(x<=mid)ask(ls,l,mid);
	if(y>mid)ask(rs,mid+1,r);
}
void build(int k,int l,int r){
	if(r-l<B)return b_pushup(w,k,l,r);
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(w,k);
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m,L[0]=1;
	for(int i=1;i<=G;i++)L[i]=L[i-1]*P;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(w=0;w<G;w++)build(1,1,n);
	for(int i=1,op;i<=m;i++){
		cin>>op>>x>>y,x^=lans,y^=lans;//强制在线
		if(op&1){
			cin>>v,v^=lans;
			for(w=0;w<G;w++)sub(1,1,n);
		}
		else{
			lans=X=0,Y=1e9;
			for(w=0;w<G;w++)ask(1,1,n);
			cout<<lans<<' '<<Y<<' '<<X<<'\n',lans&=(1<<20)-1;
		}
	}
	return 0;
}

后记

在 PP 取值稍大的时候可以跑得较快，猜测是这可以平衡操作和势能的常数，希望有大佬可以指出原因。
另外这份代码并没有开快读，充分说明了关流的 cin 和快读一样快。

评论

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

正在加载评论...