TJ For [Ynoi2007] rgxsxrs
前言
第一次写 Ynoi 的题解，并且成功卡进最优解第一页。
题意
标题即题意：range greater than x subtract x,range sum。
思路
看到这种东西既和值域有关，又和原序列有关，无疑需要使用两种数据结构维护。\
于是先考虑树套树，发现有区间修改，打不了 tag，pass。\
再考虑按值域分块，块长暂定为
- 如果当前区间的最大值小于
x 就不管它。 - 如果当前区间的最小值
\ge x+L 可以直接打标记处理，L 是当前块的下界。 - 除了这两种情况，只能暴力将这些数减去
x 并丢到某个块去。
毫无疑问，这样写的复杂度直接飞起来。
思考上面的做法失败在了什么方面。\
先假定
这说明了两个事：
- 复杂度和块长似乎没多大关系，所以可以开大一点。
- 但是较前的块不能太长了，这会使算法退化成暴力。
于是考虑一种很新的分块方式，倍增分块。\
具体说，就是把值域在
如果是这样写，重新分析下复杂度。\
每次修改时，如果只遇到前两种情况，那么最坏情况下复杂度是
发现时间复杂度 平衡树每次操作都会消耗掉树高的栈空间，以及平衡树的巨大常熟。\
不过还是给一份可以过掉前 4 个包的代码。
好像已经无法进一步优化了，总不能让平衡树矮一点，再让它快一点吧？\
事实是真的可以让它矮一点。\
平衡树（WBLT）的底层叶子长得很不优雅，占用了大量空间，于是可以考虑在维护的区间大小
当然，这样只是用时间换了空间，平衡树的常数问题还是没有解决。考虑直接用常数较小线段树代替，此时需要额外维护区间属于当前值域块的数的数量。
然后就可以在大量的卡常和调参后通过这道题了。
代码
#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;
}后记
在 猜测是这可以平衡操作和势能的常数，希望有大佬可以指出原因。
另外这份代码并没有开快读，充分说明了关流的 cin 和快读一样快。