BZOJ 1500: [NOI2005]维修数列&&洛谷P2042 [NOI2005]维护数列（多标记Treap）

Posted On 2017年12月25日

Description

Solution

fhq Treap大boss题

解决此题，你需要：

①内存回收

②线性建树

③强大的DeBUG能力

④强大的DeBUG能力

⑤强大的DeBUG能力…

对于每个节点维护以下信息：

①premx:当前最大前缀和（如无leftson，从自己开始计算）

②rearmx:当前最大后缀和（同上）

③mx:当前区间最大和

④tag:当前区间是否被旋转

⑤is_set:当前区间是否被重置

对于④&&⑤，为了避免上传标记时的额外判断，在标记到达该节点的同时更新该节点信息

对于④tag的下传：

if (t[cur].tag)
{
        if (t[cur].lc) {
            swap(t[t[cur].lc].lc,t[t[cur].lc].rc);
            swap(t[t[cur].lc].premx,t[t[cur].lc].rearmx);
            t[t[cur].lc].tag^=1;
        }
        if (t[cur].rc) {
            swap(t[t[cur].rc].lc,t[t[cur].rc].rc);
            swap(t[t[cur].rc].premx,t[t[cur].rc].rearmx);
            t[t[cur].rc].tag^=1;
        }
        t[cur].tag=0;
}

if (t[cur].tag)

{

if (t[cur].lc) {

swap(t[t[cur].lc].lc,t[t[cur].lc].rc);

swap(t[t[cur].lc].premx,t[t[cur].lc].rearmx);

t[t[cur].lc].tag^=1;

}

if (t[cur].rc) {

swap(t[t[cur].rc].lc,t[t[cur].rc].rc);

swap(t[t[cur].rc].premx,t[t[cur].rc].rearmx);

t[t[cur].rc].tag^=1;

}

t[cur].tag=0;

}

对于⑤is_set的下传:

if (t[cur].is_set)
{
        t[cur].is_set=0;
        if (t[cur].lc) {
            t[t[cur].lc].is_set=1;
            t[t[cur].lc].set=t[t[cur].lc].val=t[cur].set;
            if (t[cur].set>0)
            t[t[cur].lc].premx=t[t[cur].lc].rearmx=t[t[cur].lc].mx=
                t[cur].set*t[t[cur].lc].siz;
            else t[t[cur].lc].premx=t[t[cur].lc].rearmx=t[t[cur].lc].mx=t[cur].set;
            t[t[cur].lc].sum=t[cur].set*t[t[cur].lc].siz;
        }
        if (t[cur].rc) {
            t[t[cur].rc].is_set=1;
            t[t[cur].rc].set=t[t[cur].rc].val=t[cur].set;
            if (t[cur].set>0)
            t[t[cur].rc].premx=t[t[cur].rc].rearmx=t[t[cur].rc].mx=
                t[cur].set*t[t[cur].rc].siz;
            else t[t[cur].rc].premx=t[t[cur].rc].rearmx=t[t[cur].rc].mx=t[cur].set;
            t[t[cur].rc].sum=t[cur].set*t[t[cur].rc].siz;
        }
        t[cur].set=0;
}

if (t[cur].is_set)

{

t[cur].is_set=0;

if (t[cur].lc) {

t[t[cur].lc].is_set=1;

t[t[cur].lc].set=t[t[cur].lc].val=t[cur].set;

if (t[cur].set>0)

t[t[cur].lc].premx=t[t[cur].lc].rearmx=t[t[cur].lc].mx=

t[cur].set*t[t[cur].lc].siz;

else t[t[cur].lc].premx=t[t[cur].lc].rearmx=t[t[cur].lc].mx=t[cur].set;

t[t[cur].lc].sum=t[cur].set*t[t[cur].lc].siz;

}

if (t[cur].rc) {

t[t[cur].rc].is_set=1;

t[t[cur].rc].set=t[t[cur].rc].val=t[cur].set;

if (t[cur].set>0)

t[t[cur].rc].premx=t[t[cur].rc].rearmx=t[t[cur].rc].mx=

t[cur].set*t[t[cur].rc].siz;

else t[t[cur].rc].premx=t[t[cur].rc].rearmx=t[t[cur].rc].mx=t[cur].set;

t[t[cur].rc].sum=t[cur].set*t[t[cur].rc].siz;

}

t[cur].set=0;

}

最后注意空节点预处理和标记传递时的分类即可

另：

BZOJ普通建树可以AC，洛谷要线性建树…

O(nlogn)建树版

#include <cstdio>
#include <iostream>
#include <cstdlib>
using namespace std;
inline int read()
{
    register int f=1,k=0;register char c=getchar();
    while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
    while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
const int maxn=500000+10,inf=1e9;
int stack[(maxn+1)<<1];
struct mc{int lc,rc,siz,val,premx,rearmx,mx,sum,rnd,set;bool tag,is_set;}t[maxn+1];
inline void up(const int cur)
{
    t[cur].siz=t[t[cur].lc].siz+t[t[cur].rc].siz+1;
    t[cur].premx=max(t[t[cur].lc].premx,t[t[cur].lc].sum+t[cur].val+
        max(t[t[cur].rc].premx,0));
    t[cur].rearmx=max(t[t[cur].rc].rearmx,t[t[cur].rc].sum+t[cur].val+
        max(t[t[cur].lc].rearmx,0));
    t[cur].sum=t[t[cur].lc].sum+t[cur].val+t[t[cur].rc].sum;
    t[cur].mx=max(max(max(t[t[cur].lc].rearmx,0)+t[cur].val+max(t[t[cur].rc].premx,0),
        t[t[cur].lc].mx),t[t[cur].rc].mx);
}
inline void down(const int cur)
{
    if (t[cur].tag)
    {
        if (t[cur].lc) {
            swap(t[t[cur].lc].lc,t[t[cur].lc].rc);
            swap(t[t[cur].lc].premx,t[t[cur].lc].rearmx);
            t[t[cur].lc].tag^=1;
        }
        if (t[cur].rc) {
            swap(t[t[cur].rc].lc,t[t[cur].rc].rc);
            swap(t[t[cur].rc].premx,t[t[cur].rc].rearmx);
            t[t[cur].rc].tag^=1;
        }
        t[cur].tag=0;
    }
    if (t[cur].is_set)
    {
        t[cur].is_set=0;
        if (t[cur].lc) {
            t[t[cur].lc].is_set=1;
            t[t[cur].lc].set=t[t[cur].lc].val=t[cur].set;
            if (t[cur].set>0)
            t[t[cur].lc].premx=t[t[cur].lc].rearmx=t[t[cur].lc].mx=
                t[cur].set*t[t[cur].lc].siz;
            else t[t[cur].lc].premx=t[t[cur].lc].rearmx=t[t[cur].lc].mx=t[cur].set;
            t[t[cur].lc].sum=t[cur].set*t[t[cur].lc].siz;
        }
        if (t[cur].rc) {
            t[t[cur].rc].is_set=1;
            t[t[cur].rc].set=t[t[cur].rc].val=t[cur].set;
            if (t[cur].set>0)
            t[t[cur].rc].premx=t[t[cur].rc].rearmx=t[t[cur].rc].mx=
                t[cur].set*t[t[cur].rc].siz;
            else t[t[cur].rc].premx=t[t[cur].rc].rearmx=t[t[cur].rc].mx=t[cur].set;
            t[t[cur].rc].sum=t[cur].set*t[t[cur].rc].siz;
        }
        t[cur].set=0;
    }
}
int merge(const int x,const int y)
{
    if ((!x)||(!y))return x+y;
    if (t[x].rnd<t[y].rnd)
    {
        down(x);
        t[x].rc=merge(t[x].rc,y);
        up(x);
        return x;
    }
    down(y);
    t[y].lc=merge(x,t[y].lc);
    up(y);
    return y;
}
void split(const int cur,const int k,int&x,int&y)
{
    down(cur);
    if (!k)
    {
        x=0;y=cur;
        return;
    }
    if (t[cur].siz==k)
    {
        x=cur;y=0;
        return;
    }
    if (k<=t[t[cur].lc].siz)split(t[cur].lc,k,x,t[cur].lc),y=cur;
    else split(t[cur].rc,k-t[t[cur].lc].siz-1,t[cur].rc,y),x=cur;
    up(cur);
}
void reuse(const int cur,int&top)
{
    stack[++top]=cur;
    if (t[cur].lc)reuse(t[cur].lc,top);
    if (t[cur].rc)reuse(t[cur].rc,top);
}
int main()
{
    srand(19260817);
    int n=read(),m=read(),top=maxn-n,root=0,tmp,pos,tot,x,y,z,c,tmproot;
    char order[20];
    t[0].mx=t[0].premx=t[0].rearmx=-inf;
    for (register int i=1;i<=maxn;i++)stack[i]=maxn-i+1;
    for (register int i=1;i<=n;i++)
    tmp=read(),t[i]=(mc){0,0,1,tmp,tmp,tmp,tmp,tmp,rand(),0,0,0},
    (root=merge(root,i));
    for(register int i=1;i<=m;i++)
    {
        scanf("%s",order+1);
        if (order[1]=='I')//insert
        {
            pos=read(),tot=read();tmproot=0;
            split(root,pos,x,y);
            while (tot--)
            tmp=read(),
            t[stack[top--]]=(mc){0,0,1,tmp,tmp,tmp,tmp,tmp,rand(),0,0,0},
            tmproot=merge(tmproot,stack[top+1]);
            root=merge(merge(x,tmproot),y);
        }
        else if (order[1]=='D')//delete
        {
            pos=read(),tot=read();
            split(root,pos-1,x,y);
            split(y,tot,y,z);
            reuse(y,top);
            root=merge(x,z);
        }
        else if (order[1]=='M'&&order[4]=='E')//make_same
        {
            pos=read(),tot=read(),c=read();
            split(root,pos-1,x,y);
            split(y,tot,y,z);
            t[y].is_set=1,t[y].set=c;t[y].val=c;
            if (c>0)t[y].mx=t[y].premx=t[y].rearmx=t[y].sum=c*t[y].siz;
            else t[y].sum=c*t[y].siz,t[y].mx=t[y].premx=t[y].rearmx=c;
            root=merge(merge(x,y),z);
        }
        else if (order[1]=='R')//reverse
        {
            pos=read(); tot=read();
            split(root,pos-1,x,y);
            split(y,tot,y,z);
            t[y].tag^=1;
            swap(t[y].lc,t[y].rc);
            swap(t[y].premx,t[y].rearmx);
            root=merge(merge(x,y),z);
        }
        else if (order[1]=='G')//get-sum
        {
            pos=read(),tot=read();
            split(root,pos-1,x,y);
            split(y,tot,y,z);
            printf("%d\n",t[y].is_set?t[y].set:t[y].sum);
            root=merge(merge(x,y),z);
        }
        else if (order[1]=='M'&&order[4]=='-')printf("%d\n",t[root].mx);//max-sum
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

#include <cstdio>

#include <iostream>

#include <cstdlib>

using namespace std;

inline int read()

{

while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();

return k*f;

}

const int maxn=500000+10,inf=1e9;

int stack[(maxn+1)<<1];

struct mc{int lc,rc,siz,val,premx,rearmx,mx,sum,rnd,set;bool tag,is_set;}t[maxn+1];

inline void up(const int cur)

{

t[cur].siz=t[t[cur].lc].siz+t[t[cur].rc].siz+1;

t[cur].premx=max(t[t[cur].lc].premx,t[t[cur].lc].sum+t[cur].val+

max(t[t[cur].rc].premx,0));

t[cur].rearmx=max(t[t[cur].rc].rearmx,t[t[cur].rc].sum+t[cur].val+

max(t[t[cur].lc].rearmx,0));

t[cur].sum=t[t[cur].lc].sum+t[cur].val+t[t[cur].rc].sum;

t[cur].mx=max(max(max(t[t[cur].lc].rearmx,0)+t[cur].val+max(t[t[cur].rc].premx,0),

t[t[cur].lc].mx),t[t[cur].rc].mx);

}

inline void down(const int cur)

{

if (t[cur].tag)

{

if (t[cur].lc) {

swap(t[t[cur].lc].lc,t[t[cur].lc].rc);

swap(t[t[cur].lc].premx,t[t[cur].lc].rearmx);

t[t[cur].lc].tag^=1;

}

if (t[cur].rc) {

swap(t[t[cur].rc].lc,t[t[cur].rc].rc);

swap(t[t[cur].rc].premx,t[t[cur].rc].rearmx);

t[t[cur].rc].tag^=1;

}

t[cur].tag=0;

}

if (t[cur].is_set)

{

t[cur].is_set=0;

if (t[cur].lc) {

t[t[cur].lc].is_set=1;

t[t[cur].lc].set=t[t[cur].lc].val=t[cur].set;

if (t[cur].set>0)

t[t[cur].lc].premx=t[t[cur].lc].rearmx=t[t[cur].lc].mx=

t[cur].set*t[t[cur].lc].siz;

else t[t[cur].lc].premx=t[t[cur].lc].rearmx=t[t[cur].lc].mx=t[cur].set;

t[t[cur].lc].sum=t[cur].set*t[t[cur].lc].siz;

}

if (t[cur].rc) {

t[t[cur].rc].is_set=1;

t[t[cur].rc].set=t[t[cur].rc].val=t[cur].set;

if (t[cur].set>0)

t[t[cur].rc].premx=t[t[cur].rc].rearmx=t[t[cur].rc].mx=

t[cur].set*t[t[cur].rc].siz;

else t[t[cur].rc].premx=t[t[cur].rc].rearmx=t[t[cur].rc].mx=t[cur].set;

t[t[cur].rc].sum=t[cur].set*t[t[cur].rc].siz;

}

t[cur].set=0;

}

int merge(const int x,const int y)

{

if ((!x)||(!y))return x+y;

if (t[x].rnd<t[y].rnd)

{

down(x);

t[x].rc=merge(t[x].rc,y);

up(x);

return x;

}

down(y);

t[y].lc=merge(x,t[y].lc);

up(y);

return y;

}

void split(const int cur,const int k,int&x,int&y)

{

down(cur);

if (!k)

{

x=0;y=cur;

return;

}

if (t[cur].siz==k)

{

x=cur;y=0;

return;

}

if (k<=t[t[cur].lc].siz)split(t[cur].lc,k,x,t[cur].lc),y=cur;

else split(t[cur].rc,k-t[t[cur].lc].siz-1,t[cur].rc,y),x=cur;

up(cur);

}

void reuse(const int cur,int&top)

{

stack[++top]=cur;

if (t[cur].lc)reuse(t[cur].lc,top);

if (t[cur].rc)reuse(t[cur].rc,top);

}

int main()

{

srand(19260817);

int n=read(),m=read(),top=maxn-n,root=0,tmp,pos,tot,x,y,z,c,tmproot;

char order[20];

t[0].mx=t[0].premx=t[0].rearmx=-inf;

for (register int i=1;i<=maxn;i++)stack[i]=maxn-i+1;

for (register int i=1;i<=n;i++)

tmp=read(),t[i]=(mc){0,0,1,tmp,tmp,tmp,tmp,tmp,rand(),0,0,0},

(root=merge(root,i));

for(register int i=1;i<=m;i++)

{

scanf("%s",order+1);

if (order[1]=='I')//insert

{

pos=read(),tot=read();tmproot=0;

split(root,pos,x,y);

while (tot--)

tmp=read(),

t[stack[top--]]=(mc){0,0,1,tmp,tmp,tmp,tmp,tmp,rand(),0,0,0},

tmproot=merge(tmproot,stack[top+1]);

root=merge(merge(x,tmproot),y);

}

else if (order[1]=='D')//delete

{

pos=read(),tot=read();

split(root,pos-1,x,y);

split(y,tot,y,z);

reuse(y,top);

root=merge(x,z);

}

else if (order[1]=='M'&&order[4]=='E')//make_same

{

pos=read(),tot=read(),c=read();

split(root,pos-1,x,y);

split(y,tot,y,z);

t[y].is_set=1,t[y].set=c;t[y].val=c;

if (c>0)t[y].mx=t[y].premx=t[y].rearmx=t[y].sum=c*t[y].siz;

else t[y].sum=c*t[y].siz,t[y].mx=t[y].premx=t[y].rearmx=c;

root=merge(merge(x,y),z);

}

else if (order[1]=='R')//reverse

{

pos=read(); tot=read();

split(root,pos-1,x,y);

split(y,tot,y,z);

t[y].tag^=1;

swap(t[y].lc,t[y].rc);

swap(t[y].premx,t[y].rearmx);

root=merge(merge(x,y),z);

}

else if (order[1]=='G')//get-sum

{

pos=read(),tot=read();

split(root,pos-1,x,y);

split(y,tot,y,z);

printf("%d\n",t[y].is_set?t[y].set:t[y].sum);

root=merge(merge(x,y),z);

}

else if (order[1]=='M'&&order[4]=='-')printf("%d\n",t[root].mx);//max-sum

}

对于线性建树：

自己YY的一个写法（~~其实是HR大爷的单调栈版不会写~~）：

对于一个满二叉堆（满足中序遍历为1~n）

$lc=cur-2^{heap.max.height-cur.dep-1}$

$rc=cur+2^{heap.max.height-cur.dep-1}$

现假设要建立一个大小大于等于n而最小的满二叉堆

求其max.height:

while(n>>=1)height++;height++;

1	while(n>>=1)height++;height++;

其根节点为：root=(1<<(max.height-1))

DFS建树后再split出前N个再合并回原平衡树即可

另：为维护Treap性质，当前节点rand()=depth*magic_number+cur(magic_number>maxn)

O(n)线性建树Code：（对于初始build与insert均为线性建树）：

#include <cstdio>
#include <iostream>
#include <cstdlib>
using namespace std;
inline int read()
{
    register int f=1,k=0;register char c=getchar();
    while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
    while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
const int N=(500000+10),inf=1e9;
int stack[(N+1)<<1],a[N],n,dep,map[N],mi[233];
struct mc{int lc,rc,siz,val,premx,rearmx,mx,sum,rnd,set;bool tag,is_set;}t[N+1],T[N+1];
inline void up(const int cur)
{
    t[cur].siz=t[t[cur].lc].siz+t[t[cur].rc].siz+1;
    t[cur].premx=max(t[t[cur].lc].premx,t[t[cur].lc].sum+t[cur].val+
        max(t[t[cur].rc].premx,0));
    t[cur].rearmx=max(t[t[cur].rc].rearmx,t[t[cur].rc].sum+t[cur].val+
        max(t[t[cur].lc].rearmx,0));
    t[cur].sum=t[t[cur].lc].sum+t[cur].val+t[t[cur].rc].sum;
    t[cur].mx=max(max(max(t[t[cur].lc].rearmx,0)+t[cur].val+
        max(t[t[cur].rc].premx,0),t[t[cur].lc].mx),t[t[cur].rc].mx);
}
inline void down(const int cur)
{
    if (t[cur].tag)
    {
        if (t[cur].lc) 
		{
            swap(t[t[cur].lc].lc,t[t[cur].lc].rc);
            swap(t[t[cur].lc].premx,t[t[cur].lc].rearmx);
            t[t[cur].lc].tag^=1;
        }
        if (t[cur].rc) 
		{
            swap(t[t[cur].rc].lc,t[t[cur].rc].rc);
            swap(t[t[cur].rc].premx,t[t[cur].rc].rearmx);
            t[t[cur].rc].tag^=1;
        }
        t[cur].tag=0;
    }
    if (t[cur].is_set)
    {
        t[cur].is_set=0;
        if (t[cur].lc) 
		{
            t[t[cur].lc].is_set=1;
            t[t[cur].lc].set=t[t[cur].lc].val=t[cur].set;
            if (t[cur].set>0)
                t[t[cur].lc].premx=t[t[cur].lc].rearmx=t[t[cur].lc].mx=
                    t[cur].set*t[t[cur].lc].siz;
            else t[t[cur].lc].premx=t[t[cur].lc].rearmx=t[t[cur].lc].mx=t[cur].set;
            t[t[cur].lc].sum=t[cur].set*t[t[cur].lc].siz;
        }
        if (t[cur].rc) 
		{
            t[t[cur].rc].is_set=1;
            t[t[cur].rc].set=t[t[cur].rc].val=t[cur].set;
            if (t[cur].set>0)
            t[t[cur].rc].premx=t[t[cur].rc].rearmx=t[t[cur].rc].mx=
                t[cur].set*t[t[cur].rc].siz;
            else t[t[cur].rc].premx=t[t[cur].rc].rearmx=t[t[cur].rc].mx=t[cur].set;
            t[t[cur].rc].sum=t[cur].set*t[t[cur].rc].siz;
        }
        t[cur].set=0;
    }
}
int merge(const int x,const int y)
{
    if ((!x)||(!y))return x+y;
    if (t[x].rnd<=t[y].rnd)
    {
        down(x);
        t[x].rc=merge(t[x].rc,y);
        up(x);
        return x;
    }
    down(y);
    t[y].lc=merge(x,t[y].lc);
    up(y);
    return y;
}
void split(const int cur,const int k,int&x,int&y)
{
    down(cur);
    if (!k)
    {
        x=0;y=cur;
        return;
    }
    if (t[cur].siz==k)
    {
        x=cur;y=0;
        return;
    }
    if (k<=t[t[cur].lc].siz)split(t[cur].lc,k,x,t[cur].lc),y=cur;
    else split(t[cur].rc,k-t[t[cur].lc].siz-1,t[cur].rc,y),x=cur;
    up(cur);
}
void reuse(const int cur,int&top)
{
    stack[++top]=cur;
    if (t[cur].lc)reuse(t[cur].lc,top);
    if (t[cur].rc)reuse(t[cur].rc,top);
}
void nonupd_split(const int cur,const int k,int&x,int&y)
{
    if (!k)
    {
        x=0;y=cur;
        return;
    }
    if (T[cur].siz==k)
    {
        x=cur;y=0;
        return;
    }
    if (k<=T[T[cur].lc].siz)nonupd_split(T[cur].lc,k,x,T[cur].lc),y=cur;
    else nonupd_split(T[cur].rc,k-T[T[cur].lc].siz-1,T[cur].rc,y),x=cur;
    T[cur].siz=T[T[cur].lc].siz+1+T[T[cur].rc].siz;
}
void upd(const int&cur)
{
	if (t[cur].lc)upd(t[cur].lc);
	if (t[cur].rc)upd(t[cur].rc);
	up(cur);
}
void build(const int cur,const int depth)
{
    if (cur>=(1<<dep))return;
    const int lc=cur-mi[dep-depth-1],rc=cur+mi[dep-depth-1];
    T[cur]=(mc){lc,rc,1,a[cur],a[cur],a[cur],a[cur],a[cur],depth*1e7+cur,0,0,0};
    if (depth==dep){T[cur].lc=T[cur].rc=0;return;}
    build(lc,depth+1),build(rc,depth+1);
    T[cur].siz=T[T[cur].lc].siz+1+T[T[cur].rc].siz;
}
int main()
{
	mi[0]=1;for (register int i=1;i<=22;i++)mi[i]=mi[i-1]<<1;
    srand(19260817);
    n=read();int m=read(),top=N-n,root,tmp=n,pos,tot,x,y,z,c,tmproot;char order[20];
    t[0].mx=t[0].premx=t[0].rearmx=-inf;
    for (register int i=1;i<=N;i++)stack[i]=N-i+1;
    while(tmp>>=1)dep++;dep++;
    for (register int i=1;i<=n;i++)a[i]=read();
    build(root=(1<<(dep-1)),1);
    nonupd_split(root,n,x,y);root=x;
    for (register int i=1;i<=n;i++)t[i]=T[i];
	upd(root);
    for(register int i=1;i<=m;i++)
    {
        scanf("%s",order+1);
        if (order[1]=='I')//insert
        {
            pos=read(),tot=read();tmproot=0;
            split(root,pos,x,y);
            dep=0;int tx,ty;
            tmp=tot;while(tmp>>=1)dep++;dep++;
			for(register int i=1;i<=tot;i++)a[i]=read();
			build(tmproot=(1<<(dep-1)),1);
			nonupd_split(tmproot,tot,tx,ty);tmproot=tx;
			for (register int i=1;i<=tot;i++)
                            map[i]=stack[top],(i==tmproot)&&(root=stack[top]),top--;
			for (register int i=1;i<=tot;i++)
                            t[map[i]]=T[i],t[map[i]].lc=map[t[map[i]].lc],
                            t[map[i]].rc=map[t[map[i]].rc];
			upd(root);
			root=merge(merge(x,root),y);
        }
        else if (order[1]=='D')//delete
        {
            pos=read(),tot=read();
            split(root,pos-1,x,y);
            split(y,tot,y,z);
            reuse(y,top);
            root=merge(x,z);
        }
        else if (order[1]=='M'&&order[4]=='E')//make_same
        {
            pos=read(),tot=read(),c=read();
            split(root,pos-1,x,y);
            split(y,tot,y,z);
            t[y].is_set=1,t[y].set=c;t[y].val=c;
            if (c>0)t[y].mx=t[y].premx=t[y].rearmx=t[y].sum=c*t[y].siz;
            else t[y].sum=c*t[y].siz,t[y].mx=t[y].premx=t[y].rearmx=c;
            root=merge(merge(x,y),z);
        }
        else if (order[1]=='R')//reverse
        {
            pos=read(); tot=read();
            split(root,pos-1,x,y);
            split(y,tot,y,z);
            t[y].tag^=1;
            swap(t[y].lc,t[y].rc);
            swap(t[y].premx,t[y].rearmx);
            root=merge(merge(x,y),z);
        }
        else if (order[1]=='G')//get-sum
        {
            pos=read(),tot=read();
            split(root,pos-1,x,y);
            split(y,tot,y,z);
            printf("%d\n",t[y].is_set?t[y].set:t[y].sum);
            root=merge(merge(x,y),z);
        }
        else if (order[1]=='M'&&order[4]=='-')printf("%d\n",t[root].mx);//max-sum
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

#include <cstdio>

#include <iostream>

#include <cstdlib>

using namespace std;

inline int read()

{

while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();

return k*f;

}

const int N=(500000+10),inf=1e9;

int stack[(N+1)<<1],a[N],n,dep,map[N],mi[233];

struct mc{int lc,rc,siz,val,premx,rearmx,mx,sum,rnd,set;bool tag,is_set;}t[N+1],T[N+1];

inline void up(const int cur)

{

t[cur].siz=t[t[cur].lc].siz+t[t[cur].rc].siz+1;

t[cur].premx=max(t[t[cur].lc].premx,t[t[cur].lc].sum+t[cur].val+

max(t[t[cur].rc].premx,0));

t[cur].rearmx=max(t[t[cur].rc].rearmx,t[t[cur].rc].sum+t[cur].val+

max(t[t[cur].lc].rearmx,0));

t[cur].sum=t[t[cur].lc].sum+t[cur].val+t[t[cur].rc].sum;

t[cur].mx=max(max(max(t[t[cur].lc].rearmx,0)+t[cur].val+

max(t[t[cur].rc].premx,0),t[t[cur].lc].mx),t[t[cur].rc].mx);

}

inline void down(const int cur)

{

if (t[cur].tag)

{

if (t[cur].lc)

{

swap(t[t[cur].lc].lc,t[t[cur].lc].rc);

swap(t[t[cur].lc].premx,t[t[cur].lc].rearmx);

t[t[cur].lc].tag^=1;

}

if (t[cur].rc)

{

swap(t[t[cur].rc].lc,t[t[cur].rc].rc);

swap(t[t[cur].rc].premx,t[t[cur].rc].rearmx);

t[t[cur].rc].tag^=1;

}

t[cur].tag=0;

}

if (t[cur].is_set)

{

t[cur].is_set=0;

if (t[cur].lc)

{

t[t[cur].lc].is_set=1;

t[t[cur].lc].set=t[t[cur].lc].val=t[cur].set;

if (t[cur].set>0)

t[t[cur].lc].premx=t[t[cur].lc].rearmx=t[t[cur].lc].mx=

t[cur].set*t[t[cur].lc].siz;

else t[t[cur].lc].premx=t[t[cur].lc].rearmx=t[t[cur].lc].mx=t[cur].set;

t[t[cur].lc].sum=t[cur].set*t[t[cur].lc].siz;

}

if (t[cur].rc)

{

t[t[cur].rc].is_set=1;

t[t[cur].rc].set=t[t[cur].rc].val=t[cur].set;

if (t[cur].set>0)

t[t[cur].rc].premx=t[t[cur].rc].rearmx=t[t[cur].rc].mx=

t[cur].set*t[t[cur].rc].siz;

else t[t[cur].rc].premx=t[t[cur].rc].rearmx=t[t[cur].rc].mx=t[cur].set;

t[t[cur].rc].sum=t[cur].set*t[t[cur].rc].siz;

}

t[cur].set=0;

}

int merge(const int x,const int y)

{

if ((!x)||(!y))return x+y;

if (t[x].rnd<=t[y].rnd)

{

down(x);

t[x].rc=merge(t[x].rc,y);

up(x);

return x;

}

down(y);

t[y].lc=merge(x,t[y].lc);

up(y);

return y;

}

void split(const int cur,const int k,int&x,int&y)

{

down(cur);

if (!k)

{

x=0;y=cur;

return;

}

if (t[cur].siz==k)

{

x=cur;y=0;

return;

}

if (k<=t[t[cur].lc].siz)split(t[cur].lc,k,x,t[cur].lc),y=cur;

else split(t[cur].rc,k-t[t[cur].lc].siz-1,t[cur].rc,y),x=cur;

up(cur);

}

void reuse(const int cur,int&top)

{

stack[++top]=cur;

if (t[cur].lc)reuse(t[cur].lc,top);

if (t[cur].rc)reuse(t[cur].rc,top);

}

void nonupd_split(const int cur,const int k,int&x,int&y)

{

if (!k)

{

x=0;y=cur;

return;

}

if (T[cur].siz==k)

{

x=cur;y=0;

return;

}

if (k<=T[T[cur].lc].siz)nonupd_split(T[cur].lc,k,x,T[cur].lc),y=cur;

else nonupd_split(T[cur].rc,k-T[T[cur].lc].siz-1,T[cur].rc,y),x=cur;

T[cur].siz=T[T[cur].lc].siz+1+T[T[cur].rc].siz;

}

void upd(const int&cur)

{

if (t[cur].lc)upd(t[cur].lc);

if (t[cur].rc)upd(t[cur].rc);

up(cur);

}

void build(const int cur,const int depth)

{

if (cur>=(1<<dep))return;

const int lc=cur-mi[dep-depth-1],rc=cur+mi[dep-depth-1];

T[cur]=(mc){lc,rc,1,a[cur],a[cur],a[cur],a[cur],a[cur],depth*1e7+cur,0,0,0};

if (depth==dep){T[cur].lc=T[cur].rc=0;return;}

build(lc,depth+1),build(rc,depth+1);

T[cur].siz=T[T[cur].lc].siz+1+T[T[cur].rc].siz;

}

int main()

{

mi[0]=1;for (register int i=1;i<=22;i++)mi[i]=mi[i-1]<<1;

srand(19260817);

n=read();int m=read(),top=N-n,root,tmp=n,pos,tot,x,y,z,c,tmproot;char order[20];

t[0].mx=t[0].premx=t[0].rearmx=-inf;

for (register int i=1;i<=N;i++)stack[i]=N-i+1;

while(tmp>>=1)dep++;dep++;

for (register int i=1;i<=n;i++)a[i]=read();

build(root=(1<<(dep-1)),1);

nonupd_split(root,n,x,y);root=x;

for (register int i=1;i<=n;i++)t[i]=T[i];

upd(root);

for(register int i=1;i<=m;i++)

{

scanf("%s",order+1);

if (order[1]=='I')//insert

{

pos=read(),tot=read();tmproot=0;

split(root,pos,x,y);

dep=0;int tx,ty;

tmp=tot;while(tmp>>=1)dep++;dep++;

for(register int i=1;i<=tot;i++)a[i]=read();

build(tmproot=(1<<(dep-1)),1);

nonupd_split(tmproot,tot,tx,ty);tmproot=tx;

for (register int i=1;i<=tot;i++)

map[i]=stack[top],(i==tmproot)&&(root=stack[top]),top--;

for (register int i=1;i<=tot;i++)

t[map[i]]=T[i],t[map[i]].lc=map[t[map[i]].lc],

t[map[i]].rc=map[t[map[i]].rc];

upd(root);

root=merge(merge(x,root),y);

}

else if (order[1]=='D')//delete

{

pos=read(),tot=read();

split(root,pos-1,x,y);

split(y,tot,y,z);

reuse(y,top);

root=merge(x,z);

}

else if (order[1]=='M'&&order[4]=='E')//make_same

{

pos=read(),tot=read(),c=read();

split(root,pos-1,x,y);

split(y,tot,y,z);

t[y].is_set=1,t[y].set=c;t[y].val=c;

if (c>0)t[y].mx=t[y].premx=t[y].rearmx=t[y].sum=c*t[y].siz;

else t[y].sum=c*t[y].siz,t[y].mx=t[y].premx=t[y].rearmx=c;

root=merge(merge(x,y),z);

}

else if (order[1]=='R')//reverse

{

pos=read(); tot=read();

split(root,pos-1,x,y);

split(y,tot,y,z);

t[y].tag^=1;

swap(t[y].lc,t[y].rc);

swap(t[y].premx,t[y].rearmx);

root=merge(merge(x,y),z);

}

else if (order[1]=='G')//get-sum

{

pos=read(),tot=read();

split(root,pos-1,x,y);

split(y,tot,y,z);

printf("%d\n",t[y].is_set?t[y].set:t[y].sum);

root=merge(merge(x,y),z);

}

else if (order[1]=='M'&&order[4]=='-')printf("%d\n",t[root].mx);//max-sum

}

HR大爷的单调栈O(n)建树版：

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
int n,m,num,x,y,z,root,top,s[500100];
struct treap{
    int lc,rc,rnd,siz,val,sum,mx,lx,rx,del;
    bool xun,same;
} a[500100];
int read() {
    int tmp=0,fh=1; char c=getchar();
    while ((c<'0'||c>'9')&&c!='-') c=getchar();
    if (c=='-') fh=-1,c=getchar();
    while (c>='0'&&c<='9') tmp=tmp*10+c-48,c=getchar();
    return tmp*fh;
}
int newnode(int v) {
    int o=s[top--];
    a[o]=(treap){0,0,rand(),1,v,v,v,v,v,0,0,0};
    return o;
}
void reuse(int z) {
    if (!z) return;
    s[++top]=z;
    reuse(a[z].lc);
    reuse(a[z].rc);
}
void update1(int z) {
    if (!z) return;
    a[z].xun^=1;
    swap(a[z].lc,a[z].rc);
    swap(a[z].lx,a[z].rx);
}
void update2(int z,int v) {
    if (!z) return;
    a[z].same=1,a[z].del=v;
   	if (a[z].del>=0) {
       a[z].val=a[z].del;
       a[z].sum=a[z].mx=a[z].lx=a[z].rx=a[z].del*a[z].siz;
    } else {
       a[z].sum=a[z].del*a[z].siz;
       a[z].val=a[z].mx=a[z].lx=a[z].rx=a[z].del;
    }
}           
void up(int o) {
    a[o].siz=a[a[o].lc].siz+a[a[o].rc].siz+1;
    a[o].sum=a[a[o].lc].sum+a[a[o].rc].sum+a[o].val;
    a[o].mx=max(max(a[a[o].lc].mx,a[a[o].rc].mx),
		max(a[a[o].lc].rx,0)+max(a[a[o].rc].lx,0)+a[o].val);
    a[o].lx=max(a[a[o].lc].lx,
		a[a[o].lc].sum+a[o].val+max(a[a[o].rc].lx,0));
    a[o].rx=max(a[a[o].rc].rx,
		a[a[o].rc].sum+a[o].val+max(a[a[o].lc].rx,0));
}
void down(int o) {
    if (a[o].xun) a[o].xun=0,update1(a[o].lc),update1(a[o].rc);
    if (a[o].same) 
		update2(a[o].lc,a[o].del),update2(a[o].rc,a[o].del),a[o].same=0,a[o].del=0;
}
void split(int o,int k,int &x,int &y) {
    down(o);
    if (k==0) {x=0,y=o; return;}
    if (a[o].siz==k) {x=o,y=0; return;}
    if (a[a[o].lc].siz>=k) split(a[o].lc,k,x,a[o].lc),y=o;
    else split(a[o].rc,k-a[a[o].lc].siz-1,a[o].rc,y),x=o;
    up(o);
}
int merge(int x,int y) {
    if ((!x)||(!y)) return x+y;
    if (a[x].rnd<a[y].rnd) {
        down(x); a[x].rc=merge(a[x].rc,y);
        up(x); return x;
    } else {
        down(y); a[y].lc=merge(x,a[y].lc);
        up(y); return y;
    }
}
void build(int &o,int n) {
    int tot=0,st[n+3];
    memset(st,0,sizeof(st));
    st[++tot]=newnode(read());
    for (int i=1;i<n;i++) {
        int p=newnode(read());
        while (tot&&a[p].rnd<a[st[tot]].rnd) up(st[tot]),a[p].lc=st[tot--];
        if (tot) a[st[tot]].rc=p;
        st[++tot]=p;
    }
    while (tot) up(st[tot--]);
    o=st[1];
}
int main() {
    srand(20171222);
    n=read(); m=read();
    for (int i=500010;i;i--) s[++top]=i;
    a[0].mx=a[0].lx=a[0].rx=-2e9;
    build(root,n);
    while (m--) {
        char c=getchar(),b;
        while (c!='G'&&c!='K'&&c!='I'&&c!='R'&&c!='D'&&c!='X') c=getchar();
        b=getchar();
        while (b!='-'&&b!=' ') b=getchar();
        if (c=='X') 
		printf("%d\n",a[root].same?max(a[root].del*a[root].siz,a[root].del):a[root].mx);
        else if (c=='I') {
            split(root,read(),x,y);
            build(z,read());
            root=merge(x,merge(z,y));
        } else {
            split(root,read()-1,x,y);
            split(y,read(),z,y);
            if (c=='D') reuse(z),z=0;
            if (c=='R') update1(z);
            if (c=='K') update2(z,read());
            if (c=='G') printf("%d\n",a[z].same?a[z].del*a[z].siz:a[z].sum);
            root=merge(merge(x,z),y);
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

#include<cstdio>

#include<algorithm>

#include<cstdlib>

#include<cstring>

using namespace std;

int n,m,num,x,y,z,root,top,s[500100];

struct treap{

int lc,rc,rnd,siz,val,sum,mx,lx,rx,del;

bool xun,same;

} a[500100];

int read() {

int tmp=0,fh=1; char c=getchar();

while ((c<'0'||c>'9')&&c!='-') c=getchar();

if (c=='-') fh=-1,c=getchar();

while (c>='0'&&c<='9') tmp=tmp*10+c-48,c=getchar();

return tmp*fh;

}

int newnode(int v) {

int o=s[top--];

a[o]=(treap){0,0,rand(),1,v,v,v,v,v,0,0,0};

return o;

}

void reuse(int z) {

if (!z) return;

s[++top]=z;

reuse(a[z].lc);

reuse(a[z].rc);

}

void update1(int z) {

if (!z) return;

a[z].xun^=1;

swap(a[z].lc,a[z].rc);

swap(a[z].lx,a[z].rx);

}

void update2(int z,int v) {

if (!z) return;

a[z].same=1,a[z].del=v;

if (a[z].del>=0) {

a[z].val=a[z].del;

a[z].sum=a[z].mx=a[z].lx=a[z].rx=a[z].del*a[z].siz;

} else {

a[z].sum=a[z].del*a[z].siz;

a[z].val=a[z].mx=a[z].lx=a[z].rx=a[z].del;

}

void up(int o) {

a[o].siz=a[a[o].lc].siz+a[a[o].rc].siz+1;

a[o].sum=a[a[o].lc].sum+a[a[o].rc].sum+a[o].val;

a[o].mx=max(max(a[a[o].lc].mx,a[a[o].rc].mx),

max(a[a[o].lc].rx,0)+max(a[a[o].rc].lx,0)+a[o].val);

a[o].lx=max(a[a[o].lc].lx,

a[a[o].lc].sum+a[o].val+max(a[a[o].rc].lx,0));

a[o].rx=max(a[a[o].rc].rx,

a[a[o].rc].sum+a[o].val+max(a[a[o].lc].rx,0));

}

void down(int o) {

if (a[o].xun) a[o].xun=0,update1(a[o].lc),update1(a[o].rc);

if (a[o].same)

update2(a[o].lc,a[o].del),update2(a[o].rc,a[o].del),a[o].same=0,a[o].del=0;

}

void split(int o,int k,int &x,int &y) {

down(o);

if (k==0) {x=0,y=o; return;}

if (a[o].siz==k) {x=o,y=0; return;}

if (a[a[o].lc].siz>=k) split(a[o].lc,k,x,a[o].lc),y=o;

else split(a[o].rc,k-a[a[o].lc].siz-1,a[o].rc,y),x=o;

up(o);

}

int merge(int x,int y) {

if ((!x)||(!y)) return x+y;

if (a[x].rnd<a[y].rnd) {

down(x); a[x].rc=merge(a[x].rc,y);

up(x); return x;

} else {

down(y); a[y].lc=merge(x,a[y].lc);

up(y); return y;

}

void build(int &o,int n) {

int tot=0,st[n+3];

memset(st,0,sizeof(st));

st[++tot]=newnode(read());

for (int i=1;i<n;i++) {

int p=newnode(read());

while (tot&&a[p].rnd<a[st[tot]].rnd) up(st[tot]),a[p].lc=st[tot--];

if (tot) a[st[tot]].rc=p;

st[++tot]=p;

}

while (tot) up(st[tot--]);

o=st[1];

}

int main() {

srand(20171222);

n=read(); m=read();

for (int i=500010;i;i--) s[++top]=i;

a[0].mx=a[0].lx=a[0].rx=-2e9;

build(root,n);

while (m--) {

char c=getchar(),b;

while (c!='G'&&c!='K'&&c!='I'&&c!='R'&&c!='D'&&c!='X') c=getchar();

b=getchar();

while (b!='-'&&b!=' ') b=getchar();

if (c=='X')

printf("%d\n",a[root].same?max(a[root].del*a[root].siz,a[root].del):a[root].mx);

else if (c=='I') {

split(root,read(),x,y);

build(z,read());

root=merge(x,merge(z,y));

} else {

split(root,read()-1,x,y);

split(y,read(),z,y);

if (c=='D') reuse(z),z=0;

if (c=='R') update1(z);

if (c=='K') update2(z,read());

if (c=='G') printf("%d\n",a[z].same?a[z].del*a[z].siz:a[z].sum);

root=merge(merge(x,z),y);

}

return 0;

}

Compare:

我的O(n)建树版：

2483807

mczhuang

1500

Accepted

52080 kb

4444 ms

C++/Edit

7002 B

2017-12-26 19:46:20

我的普通fhq Treap版：

2481249

mczhuang

1500

Accepted

26688 kb

7236 ms

C++/Edit

5473 B

2017-12-25 19:28:47

HR大爷的单调栈O(n)建树版：

2475651

child

1500

Accepted

24976 kb

4640 ms

C++/Edit

3766 B

2017-12-22 20:06:57

0 0 vote

Article Rating

0 评论

Inline Feedbacks

View all comments