标签：ch int 扶苏 问题 fa add maxn change
- 利用Splay进行序列操作时，将数组坐标整体平移1，给0留出空间，并在操作过程中始终保持0号节点的特性
- 用#define语句和struct的构造函数简化编程复杂度
- 对名字空间(namespace)有了更深刻的理解
- Splay的常数较大，难以通过1e6规模的数据
- 在建树时，根据Splay的特性，直接建出一条只有右儿子的链即可，时间复杂度仍然是正确的。
点击查看代码
#include <bits/stdc++.h>
#define l(x) ch[x][0]
#define r(x) ch[x][1]
using namespace std;
struct t1
{
long long va,maxn;
long long add;
int change;
t1()
{
va=maxn=LLONG_MIN;
add=0;
change=INT_MAX;
}
}t[1000005];
int fa[1000005],ch[1000005][2];
void pushdown(int x)
{
if(t[x].change!=INT_MAX)
{
if(l(x))
{
t[l(x)].va=t[x].change;
t[l(x)].maxn=t[x].change;
t[l(x)].change=t[x].change;
t[l(x)].add=0;
}
if(r(x))
{
t[r(x)].va=t[x].change;
t[r(x)].maxn=t[x].change;
t[r(x)].change=t[x].change;
t[r(x)].add=0;
}
t[x].change=INT_MAX;
}
if(t[x].add)
{
if(l(x))
{
t[l(x)].va+=t[x].add;
t[l(x)].maxn+=t[x].add;
t[l(x)].add+=t[x].add;
}
if(r(x))
{
t[r(x)].va+=t[x].add;
t[r(x)].maxn+=t[x].add;
t[r(x)].add+=t[x].add;
}
t[x].add=0;
}
}
int get(int x)
{
return ch[fa[x]][1]==x;
}
void maintain(int x)
{
t[x].maxn=max(t[x].va,max(t[l(x)].maxn,t[r(x)].maxn));
}
void rotate(int x)
{
int y=fa[x],z=fa[y],opt=get(x);
ch[y][opt]=ch[x][opt^1];
if(ch[x][opt^1])
{
fa[ch[x][opt^1]]=y;
}
fa[y]=x;
ch[x][opt^1]=y;
fa[x]=z;
if(z)
{
ch[z][y==ch[z][1]]=x;
}
maintain(y);
maintain(x);
}
void update(int x,int k)
{
if(fa[x]!=k)
{
update(fa[x],k);
}
pushdown(x);
}
void Splay(int x,int k)
{
update(x,k);
while(fa[x]!=k)
{
int y=fa[x],z=fa[y];
if(z==k)
{
rotate(x);
break;
}
if(get(x)==get(y))
{
rotate(y);
rotate(x);
}
else
{
rotate(x);
rotate(x);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,q;
cin>>n>>q;
ch[1][1]=2;
for(int i=2;i<=n+1;i++)
{
cin>>t[i].va;
ch[i][1]=i+1;
fa[i]=i-1;
}
fa[n+2]=n+1;
t[n+1].maxn=t[n+1].va;
for(int i=n;i>=2;i--)
{
t[i].maxn=max(t[i+1].maxn,t[i].va);
}
for(int i=1;i<=q;i++)
{
int opt,l,r,x;
cin>>opt>>l>>r;
Splay(l,0);
Splay(r+2,l);
int id=ch[r+2][0];
if(opt==1)
{
cin>>x;
pushdown(id);
t[id].change=x;
t[id].va=t[id].maxn=x;
}
else if(opt==2)
{
cin>>x;
pushdown(id);
t[id].add=x;
t[id].va+=x;
t[id].maxn+=x;
}
else
{
cout<<t[id].maxn<<"\n";
}
}
return 0;
}
标签：ch,
int,
扶苏,
问题,
fa,
add,
maxn,
change
From： https://www.cnblogs.com/watersail/p/18446741