这是完整代码(AC)![](//图.tk/0)
```cpp
#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin), freopen(a".out","w",stdout)
using namespace std;
const int N = 1e5+5;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
ll ret = 0; char ch = ' ', c = getchar();
while(!(c >= '0' && c <= '9')) ch = c, c = getchar();
while(c >= '0' && c <= '9') ret = (ret << 1) + (ret << 3) + c - '0', c = getchar();
return ch == '-' ? -ret : ret;
}
int n;
int a[N];
template <typename T> struct Splay{
int s[N][2],f[N],siz[N]; bool tag[N]; T val[N];
int rt;
inline void pushup(int k){siz[k] = siz[s[k][0]] + siz[s[k][1]] + 1;}
inline bool get(int k){return k == s[f[k]][1];}
inline void conet(int u,int v,bool op){
if(u) f[u] = v;
if(v) s[v][op] = u;
}
inline void pushdown(int k){
if(!k || !tag[k]) return;
swap(s[k][0],s[k][1]);
if(s[k][0]) tag[s[k][0]] ^= 1;
if(s[k][1]) tag[s[k][1]] ^= 1;
tag[k] = 0;
}
inline void rotate(int k){
int fa = f[k], ffa = f[fa], op1 = get(k), op2 = get(fa);
pushdown(fa), pushdown(k);
conet(s[k][op1^1],fa,op1),
conet(fa,k,op1^1),
conet(k,ffa,op2);
pushup(fa), pushup(k);
}
inline void splay(int k, int lim = 0){
for(int fa = f[k] ; (fa = f[k]) != lim ; rotate(k)){
pushdown(f[fa]), pushdown(fa), pushdown(k);
if(f[fa] != lim)
get(fa) == get(k) ? rotate(fa) : rotate(k);
}
if(!lim) rt = k;
}
void build(int& k,int l,int r,int fa = 0){
if(l > r) return;
int mid = (l + r) >> 1;
k = a[mid], f[k] = fa, tag[k] = 0;
build(s[k][0],l,mid-1,k),
build(s[k][1],mid+1,r,k);
pushup(k);
}
inline int find(T x){
int k = rt;
while(k){
pushdown(k);
if(x <= siz[s[k][0]]) k = s[k][0];
else if(x <= siz[s[k][0]] + 1) return k;
else x -= siz[s[k][0]] + 1, k = s[k][1];
}
return 0;
}
inline void reverse(int l,int r){
l = find(l-1), r = find(r+1);
pushdown(l), pushdown(r);
splay(l),splay(r,rt);
tag[s[s[rt][1]][0]] ^= 1;
}
void tprint(){
for(int i = 1 ; i <= n+2 ; i ++) printf(" (%d) [%d,%d] {%d}\n",i,s[i][0],s[i][1],f[i]);
}
void gprint(int k){
if(!k) return;
pushdown(k);
gprint(s[k][0]);
printf("%d ",k);
gprint(s[k][1]);
}
void print(int k){
if(!k) return;
pushdown(k);
print(s[k][0]);
printf("%d ",k);
print(s[k][1]);
}
};
Splay<int> sp;
struct Node{
int h,id;
inline friend bool operator < (const Node a,const Node b){return a.h != b.h ? a.h < b.h : a.id < b.id;}
}p[N];
signed main(){
n = read();
for(int i = 1 ; i <= n ; i ++) p[i].h = read(), p[i].id = i;
sort(p+1,p+n+1);
for(int i = 1 ; i <= n ; i ++) a[p[i].id] = i+1;
a[n+1] = n+2, a[0] = 1;
sp.build(sp.rt,0,n+1);
// sp.print(sp.rt);puts("");
for(int i = 2 ; i <= n+1 ; i ++){
// sp.gprint(sp.rt); puts("");
sp.splay(i);
int ans = sp.siz[sp.s[sp.rt][0]] + 1;
printf("%d ",ans-1);//puts("");
sp.reverse(i,ans);
// sp.tprint();
//sp.gprint(sp.rt);puts("");
}
}
/*
6
3 4 5 1 6 2
*/
```
by LastOrder_ @ 2021-11-02 18:43:52
显然没有交换律和结合律的标记是都要下传的。
一般的写法还有在 splay 开始的地方直接将整条链 pushdown,你看看是不是在那就下放了。
by jerry3128 @ 2021-11-02 18:45:03
@[jerry3128](/user/27338)
>显然没有交换律和结合律的标记是都要下传的。
不是很理解这个地方,请问这个标记为什么一定要在`splay()`函数里下传?
by LastOrder_ @ 2021-11-02 23:08:21
@[LastOrder_](/user/88028) splay中的rot函数会改变父子关系,即改变一个节点子树内代表的区间范围,懒标记就是作用于一个区间的。如果不下放,则懒标记作用的范围都改变了,即非法。
by jerry3128 @ 2021-11-02 23:43:55
@[jerry3128](/user/27338) 那我仅在 `rotate()` 里下放标记为什么不可行?必须在 `splay()` 里也下放?
by LastOrder_ @ 2021-11-03 07:18:01
@[LastOrder_](/user/88028) 这是可行的啊。(或者是写挂了
by jerry3128 @ 2021-11-03 07:41:23
@[jerry3128](/user/27338) 好吧谢谢![](//图.tk/s)
by LastOrder_ @ 2021-11-03 07:47:35
@[LastOrder_](/user/88028) 总的来说还是建议在splay之前就下放一条链上的写法。可以去看看那种写法。
by jerry3128 @ 2021-11-03 07:49:11
@[LastOrder_](/user/88028) 仅在rotate里下放是完全可行的,而且只需要先后下放父节点和当前节点标记,但是要注意更新 `chk` (表示当前节点是父节点的左儿子还是右儿子)
by Arson1st @ 2023-10-26 11:41:18