NOI2005维修数列

2014年7月30日23,55625

Description

Input

输入文件的第1行包含两个数N和M，N表示初始时数列中数的个数，M表示要进行的操作数目。第2行包含N个数字，描述初始时的数列。以下M行，每行一条命令，格式参见问题描述中的表格。

Output

对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。

Sample Input

9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM

Sample Output

-1
10
1
10

HINT

题解

这是一道经典的splay模板题

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define N 1000005
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,rt,cnt;
int a[N],id[N],fa[N],c[N][2];
int sum[N],size[N],v[N],mx[N],lx[N],rx[N];
bool tag[N],rev[N];
queue<int> q;
void update(int x)
{
	int l=c[x][0],r=c[x][1];
	sum[x]=sum[l]+sum[r]+v[x];
	size[x]=size[l]+size[r]+1;
	mx[x]=max(mx[l],mx[r]);
	mx[x]=max(mx[x],rx[l]+v[x]+lx[r]);
	lx[x]=max(lx[l],sum[l]+v[x]+lx[r]);
	rx[x]=max(rx[r],sum[r]+v[x]+rx[l]);
}
void pushdown(int x)
{
	int l=c[x][0],r=c[x][1];
	if(tag[x])
	{
		rev[x]=tag[x]=0;
		if(l)tag[l]=1,v[l]=v[x],sum[l]=v[x]*size[l];
		if(r)tag[r]=1,v[r]=v[x],sum[r]=v[x]*size[r];
		if(v[x]>=0)
		{
			if(l)lx[l]=rx[l]=mx[l]=sum[l];
			if(r)lx[r]=rx[r]=mx[r]=sum[r];
		}
		else 
		{
			if(l)lx[l]=rx[l]=0,mx[l]=v[x];
			if(r)lx[r]=rx[r]=0,mx[r]=v[x];
		}
	}
	if(rev[x])
	{
		rev[x]^=1;rev[l]^=1;rev[r]^=1;
		swap(lx[l],rx[l]);swap(lx[r],rx[r]);
		swap(c[l][0],c[l][1]);swap(c[r][0],c[r][1]);
	}
}
void rotate(int x,int &k)
{
	int y=fa[x],z=fa[y],l,r;
	l=(c[y][1]==x);r=l^1;
	if(y==k)k=x;
	else c[z][c[z][1]==y]=x;
	fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
	c[y][l]=c[x][r];c[x][r]=y;
	update(y);update(x);
}
void splay(int x,int &k)
{
	while(x!=k)
	{
		int y=fa[x],z=fa[y];
	    if(y!=k)
		{
			if(c[y][0]==x^c[z][0]==y)rotate(x,k);
			else rotate(y,k);
		}
		rotate(x,k);
	}
}
int find(int x,int rk)
{
	pushdown(x);
	int l=c[x][0],r=c[x][1];
	if(size[l]+1==rk)return x;
	if(size[l]>=rk)return find(l,rk);
	return find(r,rk-size[l]-1);
}
void rec(int x)
{
	if(!x)return;
	int l=c[x][0],r=c[x][1];
	rec(l);rec(r);q.push(x);
	fa[x]=c[x][0]=c[x][1]=0;
	tag[x]=rev[x]=0;
}
int split(int k,int tot)
{
	int x=find(rt,k),y=find(rt,k+tot+1);
	splay(x,rt);splay(y,c[x][1]);
	return c[y][0];
}
void query(int k,int tot)
{
	int x=split(k,tot);
	printf("%d\n",sum[x]);
}
void modify(int k,int tot,int val)
{
	int x=split(k,tot),y=fa[x];
	v[x]=val;tag[x]=1;sum[x]=size[x]*val;
	if(val>=0)lx[x]=rx[x]=mx[x]=sum[x];
	else lx[x]=rx[x]=0,mx[x]=val;
	update(y);update(fa[y]);
}
void rever(int k,int tot)
{
	int x=split(k,tot),y=fa[x];
	if(!tag[x])
	{
		rev[x]^=1;
		swap(c[x][0],c[x][1]);
		swap(lx[x],rx[x]);
		update(y);update(fa[y]);
	}
}
void erase(int k,int tot)
{
	int x=split(k,tot),y=fa[x];
	rec(x);c[y][0]=0;
	update(y);update(fa[y]);
}
void build(int l,int r,int f)
{
	if(l>r)return;
	int mid=(l+r)>>1,now=id[mid],last=id[f];
	if(l==r)
	{
		sum[now]=a[l];size[now]=1;
		tag[now]=rev[now]=0;
		if(a[l]>=0)lx[now]=rx[now]=mx[now]=a[l];
		else lx[now]=rx[now]=0,mx[now]=a[l];
	}
	else build(l,mid-1,mid),build(mid+1,r,mid);
	v[now]=a[mid];fa[now]=last;update(now);
	c[last][mid>=f]=now;
   }
void insert(int k,int tot)
{
	for(int i=1;i<=tot;i++)a[i]=read();
	for(int i=1;i<=tot;i++)
		if(!q.empty())id[i]=q.front(),q.pop();
		else id[i]=++cnt;
	build(1,tot,0);int z=id[(1+tot)>>1];
	int x=find(rt,k+1),y=find(rt,k+2);
	splay(x,rt);splay(y,c[x][1]);
	fa[z]=y;c[y][0]=z;
	update(y);update(x);
}
int main()
{
	n=read();m=read();
	mx[0]=a[1]=a[n+2]=-inf;
	for(int i=1;i<=n;i++)a[i+1]=read();
	for(int i=1;i<=n+2;i++)id[i]=i;
	build(1,n+2,0);
	rt=(n+3)>>1;cnt=n+2;
	int k,tot,val;
	char ch[10];
	while(m--)
	{
		scanf("%s",ch);
		if(ch[0]!='M'||ch[2]!='X')k=read(),tot=read();
		if(ch[0]=='I')insert(k,tot);
		if(ch[0]=='D')erase(k,tot);
		if(ch[0]=='M')
		{
			if(ch[2]=='X')printf("%d\n",mx[rt]);
			else val=read(),modify(k,tot,val);
		}
		if(ch[0]=='R')rever(k,tot);
		if(ch[0]=='G')query(k,tot);
	}
	return 0;
}

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

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define N 1000005

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,rt,cnt;

int a[N],id[N],fa[N],c[N][2];

int sum[N],size[N],v[N],mx[N],lx[N],rx[N];

bool tag[N],rev[N];

queue<int> q;

void update(int x)

{

int l=c[x][0],r=c[x][1];

sum[x]=sum[l]+sum[r]+v[x];

size[x]=size[l]+size[r]+1;

mx[x]=max(mx[l],mx[r]);

mx[x]=max(mx[x],rx[l]+v[x]+lx[r]);

lx[x]=max(lx[l],sum[l]+v[x]+lx[r]);

rx[x]=max(rx[r],sum[r]+v[x]+rx[l]);

}

void pushdown(int x)

{

int l=c[x][0],r=c[x][1];

if(tag[x])

{

rev[x]=tag[x]=0;

if(l)tag[l]=1,v[l]=v[x],sum[l]=v[x]*size[l];

if(r)tag[r]=1,v[r]=v[x],sum[r]=v[x]*size[r];

if(v[x]>=0)

{

if(l)lx[l]=rx[l]=mx[l]=sum[l];

if(r)lx[r]=rx[r]=mx[r]=sum[r];

}

else

{

if(l)lx[l]=rx[l]=0,mx[l]=v[x];

if(r)lx[r]=rx[r]=0,mx[r]=v[x];

}

if(rev[x])

{

rev[x]^=1;rev[l]^=1;rev[r]^=1;

swap(lx[l],rx[l]);swap(lx[r],rx[r]);

swap(c[l][0],c[l][1]);swap(c[r][0],c[r][1]);

}

void rotate(int x,int &k)

{

int y=fa[x],z=fa[y],l,r;

l=(c[y][1]==x);r=l^1;

if(y==k)k=x;

else c[z][c[z][1]==y]=x;

fa[c[x][r]]=y;fa[y]=x;fa[x]=z;

c[y][l]=c[x][r];c[x][r]=y;

update(y);update(x);

}

void splay(int x,int &k)

{

while(x!=k)

{

int y=fa[x],z=fa[y];

if(y!=k)

{

if(c[y][0]==x^c[z][0]==y)rotate(x,k);

else rotate(y,k);

}

rotate(x,k);

}

int find(int x,int rk)

{

pushdown(x);

int l=c[x][0],r=c[x][1];

if(size[l]+1==rk)return x;

if(size[l]>=rk)return find(l,rk);

return find(r,rk-size[l]-1);

}

void rec(int x)

{

if(!x)return;

int l=c[x][0],r=c[x][1];

rec(l);rec(r);q.push(x);

fa[x]=c[x][0]=c[x][1]=0;

tag[x]=rev[x]=0;

}

int split(int k,int tot)

{

int x=find(rt,k),y=find(rt,k+tot+1);

splay(x,rt);splay(y,c[x][1]);

return c[y][0];

}

void query(int k,int tot)

{

int x=split(k,tot);

printf("%d\n",sum[x]);

}

void modify(int k,int tot,int val)

{

int x=split(k,tot),y=fa[x];

v[x]=val;tag[x]=1;sum[x]=size[x]*val;

if(val>=0)lx[x]=rx[x]=mx[x]=sum[x];

else lx[x]=rx[x]=0,mx[x]=val;

update(y);update(fa[y]);

}

void rever(int k,int tot)

{

int x=split(k,tot),y=fa[x];

if(!tag[x])

{

rev[x]^=1;

swap(c[x][0],c[x][1]);

swap(lx[x],rx[x]);

update(y);update(fa[y]);

}

void erase(int k,int tot)

{

int x=split(k,tot),y=fa[x];

rec(x);c[y][0]=0;

update(y);update(fa[y]);

}

void build(int l,int r,int f)

{

if(l>r)return;

int mid=(l+r)>>1,now=id[mid],last=id[f];

if(l==r)

{

sum[now]=a[l];size[now]=1;

tag[now]=rev[now]=0;

if(a[l]>=0)lx[now]=rx[now]=mx[now]=a[l];

else lx[now]=rx[now]=0,mx[now]=a[l];

}

else build(l,mid-1,mid),build(mid+1,r,mid);

v[now]=a[mid];fa[now]=last;update(now);

c[last][mid>=f]=now;

}

void insert(int k,int tot)

{

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

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

if(!q.empty())id[i]=q.front(),q.pop();

else id[i]=++cnt;

build(1,tot,0);int z=id[(1+tot)>>1];

int x=find(rt,k+1),y=find(rt,k+2);

splay(x,rt);splay(y,c[x][1]);

fa[z]=y;c[y][0]=z;

update(y);update(x);

}

int main()

{

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

mx[0]=a[1]=a[n+2]=-inf;

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

for(int i=1;i<=n+2;i++)id[i]=i;

build(1,n+2,0);

rt=(n+3)>>1;cnt=n+2;

int k,tot,val;

char ch[10];

while(m--)

{

scanf("%s",ch);

if(ch[0]!='M'||ch[2]!='X')k=read(),tot=read();

if(ch[0]=='I')insert(k,tot);

if(ch[0]=='D')erase(k,tot);

if(ch[0]=='M')

{

if(ch[2]=='X')printf("%d\n",mx[rt]);

else val=read(),modify(k,tot,val);

}

if(ch[0]=='R')rever(k,tot);

if(ch[0]=='G')query(k,tot);

}

return 0;

}

« 「BZOJ3223」JoyOI 1729 文艺平衡树「BZOJ1861」[ZJOI2006] Book 书架 »

大家好全民制作人们好我是练习时长两年半的个人练习生

黄学长，请问代码里id数组是什么意思，是指节点的编号吗

斯巴达临时工

黄学长，请问第164行的mx[0]=-inf有什么作用？

hao

黄学长，可以给新手加一点温暖吗？：比如写一下注入 v[],tag[],sum[],lx[],rx[]….这些数组的意义 QAQ

qwq

我觉得你学一下splay再看这题会比较好= =

hzwer

已加

Devin

学长，如果要让splay跑得快一点，可以往什么方向改进呢 QAQ

hzwer

指针版。？反正我不会

Starzxy

指针确实快比较多但是代码量要多一倍的样子QAQ

lowsfish

代码量并不会多。。而且可读性更高

Starzxy

我这种一用指针写5k+的是不是没救了。。

Recursion

我还是觉得指针用起来舒服多了

shanquan2

不应该是数组舒服吗

HansBug

额。。。表示以前常用指针写各种树结构代码坑爹的一塌糊涂而且经常滚粗了还半天找不出来= =，直到后来统统改用数组

LYK

测试了下pushdown中的pushup是没有必要的。

hzwer

恩恩

嗯哼

黄学长为什么不用处理0号节点咩？在pushup（）的时候不会更新错么？

hzwer

mx[0]=-inf;

HBH

处理rev标记的时候为什么不需要交换ch [0]和ch ?

HBH

哦。。之前处理过了

lyx

学长求解释一下Build函数的具体过程和数组的作用，我现在Splay唯一不懂的就是建树，旋转什么的都已经会了，就这个不理解，蛋疼死了。（LCT的Splay不用建树，直接access，splay就好。。于是就没学建树）

hzwer

实际上就是把一个序列递归建成二叉树T T。。。我这个代码写的繁琐了

lyx

有同感- -不太好记，不过感觉Splay和Rotate写的很优美，一下就记着了。PS：缩行看起来不是很习惯QAQ

zld3794955

给用数组写Splay的黄学长跪烂烂。。

smkx

splay还能怎么写？

hzwer

听他意思估计是指针23333

hzwer.com _ Home | http://hzwer.com

NOI2005维修数列

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论