发表更新Problem Solutions13 分钟读完 (大约1883个字)

题解：SPOJ-GSS系列

GSS系列 - 题单 - 洛谷

又开天坑.mp4

做一下SPOJ的8道数据结构，但是什么时候能写完我也不知道qwq

关于SPOJ注册问题

这个很多帖子都有讲，主要就是google的recaptcha用不了，把它更换成recaptcha.net的验证（虽然尝试跨越长城了，但是仍然用不了，不知道为啥）

解决方法就是安装 Gooreplacer(for Microsoft Edge)

下载完成后，点击橙色小刷子，在弹出的窗口中点击最上方的蓝色按钮“配置规则”。点击页面中表格上方的“新增”，在弹出的窗口内依次输入 www.google.com/recaptcha，“通配符”，recaptcha.net/recaptcha，点击“提交”。

正文

GSS1

思路

这个比较简单，就是最基本的一个框架。

一个节点有4个部分：区间和sum、区间最大前缀和lmx，区间最大后缀和rmx，区间最大子段和mx

  • 在算一个区间最大子段和时，会出现两种情况：

    1. 该区间最大子段和是左/右儿子的最大子段和
    2. 该区间最大子段和是左儿子的最大后缀和+右儿子的最大前缀和

  • 在算一个区间的最大前缀/后缀和时，也会出现两种情况：（以前缀和为例）

    1. 该区间最大前缀和是左儿子的最大前缀和
    2. 该区间最大前缀和是左儿子的区间和加右儿子的最大前缀和

至此，我们就可以将线段树build起来了，有一个技巧注意一下，因为在接下来的题里也会用：

​ 重定义node结构体的”+“，或者写一个merge函数，表示node之间的加法，因为不仅有pushup会用到，query也会用。

然后关于query没有什么好讲的吧。就这样，看代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N=50005;

ll n,m;
ll a[N];

struct node
{
    ll sum,lmx,rmx,mx;
    
    node()
    {
    	sum=lmx=rmx=mx=0;
	}
    
} tr[N<<2];

node merge(node x,node y)
{
	node ans;
	ans.sum=x.sum+y.sum;
    ans.lmx=max(x.lmx,x.sum+y.lmx);
    ans.rmx=max(y.rmx,y.sum+x.rmx);
    ans.mx=max(max(x.mx,y.mx),x.rmx+y.lmx);
    
    return ans;
}

void pushup(ll p) 
{
    tr[p]=merge(tr[p<<1],tr[p<<1|1]);
}

void build(ll p,ll l,ll r) 
{
    if(l==r) 
	{
        tr[p].lmx=tr[p].rmx=tr[p].mx=tr[p].sum=a[l];
        return;
    }
    
    ll mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    
    pushup(p);
}

node query(ll p,ll l,ll r,ll x,ll y) 
{
    if(x<=l&&y>=r) 
	{
		return tr[p]; 
	}
	
    ll mid=(l+r)>>1;
    node L,R;
    
    if(y<=mid)
    {
    	return query(p<<1,l,mid,x,y);
	}
    else if(x>mid)
    {
    	return query(p<<1|1,mid+1,r,x,y);
	}
	else
	{
		L=query(p<<1,l,mid,x,y);
		R=query(p<<1|1,mid+1,r,x,y);
		return merge(L,R);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
    	cin>>a[i];
	}
    
    build(1,1,n);
    
    cin>>m;
    while(m--) 
	{
        ll x,y;
        cin>>x>>y;
        
        cout<<query(1,1,n,x,y).mx<<"\n";
        
    }
    
    return 0;
}

GSS2

思路

没写，这个难，咕

代码

1

GSS3

思路

本题在第一题的基础上加入了单点修改，没有任何攻击性（确信

update就很正常，把边界的点重新赋值，然后重新往上pushup一下就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N=100005;

int n,m;
int a[N];

struct node
{
    ll sum,lmx,rmx,mx;
    
    node()
    {
    	sum=lmx=rmx=mx=0;
	}
    
} tr[N<<2];

node merge(node x,node y)
{
	node ans;
	ans.sum=x.sum+y.sum;
    ans.lmx=max(x.lmx,x.sum+y.lmx);
    ans.rmx=max(y.rmx,y.sum+x.rmx);
    ans.mx=max(max(x.mx,y.mx),x.rmx+y.lmx);
    
    return ans;
}

void pushup(int p) 
{
    tr[p]=merge(tr[p<<1],tr[p<<1|1]);
}

void build(int p,int l,int r) 
{
    if(l==r) 
	{
        tr[p].lmx=tr[p].rmx=tr[p].mx=tr[p].sum=a[l];
        return;
    }
    
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    
    pushup(p);
}

void update(int p,int l,int r,int x,int v)
{
	if(l==r)
	{
		tr[p].lmx=tr[p].rmx=tr[p].mx=tr[p].sum=v;
		return;
	}
	
	int mid=(l+r)>>1;
	if(x<=mid)
    {
        update(p<<1,l,mid,x,v);
    }
    else
    {
        update(p<<1|1,mid+1,r,x,v);
    }
    
    pushup(p);
}

node query(ll p,ll l,ll r,ll x,ll y) 
{
    if(x<=l&&y>=r) 
	{
		return tr[p]; 
	}
	
    ll mid=(l+r)>>1;
    node L,R;
    
    if(y<=mid)
    {
    	return query(p<<1,l,mid,x,y);
	}
    else if(x>mid)
    {
    	return query(p<<1|1,mid+1,r,x,y);
	}
	else
	{
		L=query(p<<1,l,mid,x,y);
		R=query(p<<1|1,mid+1,r,x,y);
		return merge(L,R);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    	cin>>a[i];
	}
    
    build(1,1,n);
    
    cin>>m;
    while(m--) 
	{
        int op,x,y;
        cin>>op>>x>>y;
        
        if(op==0)
        {
        	update(1,1,n,x,y);
		}
        else
        {
        	cout<<query(1,1,n,x,y).mx<<"\n";
		}
    }
    
    return 0;
}

GSS4

思路

这题跟前面3问好像没啥关系，不知道为啥放这，但是总体架构仍然不变。

区间求和没有什么难度，但是在修改的时候如果每一个数用sqrt开一下方，常数会剧增，因此需要讨论一种特殊情况：

​ 如果这一个区间的最大值已经<=1了，那么对其开方不会有用，可以跳过

所以在记区间和的基础上记一个区间最大值即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
#include<bits/stdc++.h>

using namespace std;

#define ll long long
mt19937 rnd(time(NULL));

ll n,m;
ll a[100005];

struct node
{
	ll sum,mx;
	node()
	{
		sum=mx=0;
	}
} tr[400005];

node merge(node x,node y)
{
	node ans;
	ans.sum=x.sum+y.sum;
    ans.mx=max(x.mx,y.mx);
    
    return ans;
}

void pushup(ll p)
{
	tr[p]=merge(tr[p<<1],tr[p<<1|1]);
}

void build(ll p,ll l,ll r)
{
	if(l==r)
	{
		tr[p].sum=tr[p].mx=a[l];
		return ;
	}
	
	ll mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	
	pushup(p);
}

void update(ll p,ll l,ll r,ll x,ll y)
{
	if(l==r)
	{
		tr[p].sum=sqrt(tr[p].sum);
		tr[p].mx=sqrt(tr[p].mx);
		return ;
	}
	
	ll mid=(l+r)>>1;
	if(x<=mid&&tr[p<<1].mx>1)
	{
		update(p<<1,l,mid,x,y);
	}
	if(y>mid&&tr[p<<1|1].mx>1)
	{
		update(p<<1|1,mid+1,r,x,y);
	}
	
	
	pushup(p);
	
}

node query(ll p,ll l,ll r,ll x,ll y)
{
	if(x<=l&&y>=r)
	{
		return tr[p];
	}
	
	ll mid=(l+r)>>1;
	node L,R;
	if(x<=mid)
	{
		L=query(p<<1,l,mid,x,y);
	}
	if(y>mid)
	{
		R=query(p<<1|1,mid+1,r,x,y);
	}
	
	return merge(L,R);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	for(ll cs=1;cin>>n;cs++)
	{
		for(ll i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		build(1,1,n);
		
		cout<<"Case #"<<cs<<":\n";
		
		cin>>m;
		while(m--)
		{
			ll op,x,y;
			cin>>op>>x>>y;
			
			if(x>y)
			{
				swap(x,y);
			}
			
			if(op==0)
			{
				update(1,1,n,x,y);
			}
			else
			{
				cout<<query(1,1,n,x,y).sum<<"\n";
			} 
		}
		cout<<"\n";
	}

	return 0;
}

GSS7

思路

在第三题的基础上加入树链剖分。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int inf=0x3f3f3f3f;
const int N=1e5+5;

ll n,q;
ll x[N];

ll tot;
ll head[N],to[N*2],nxt[N*2];

ll cnt;
ll dfn[N],id[N];

ll sz[N],dep[N],hvy[N],top[N],par[N];

struct node
{
	ll sum,lmx,rmx,mx,lz;
	
	node()
    {
        sum=lmx=rmx=mx=0;
        lz=inf;
    }
    
} tr[N<<2];

void add(ll u,ll v)
{
    to[++tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
}

void dfs1(ll u,ll f)
{
    dep[u]=dep[f]+1;
    par[u]=f;
    sz[u]=1;
    
    for(ll i=head[u];i;i=nxt[i])
    {
        ll v=to[i];
        if(v==f)
        {
            continue;
        }
        dfs1(v,u);
        
        sz[u]+=sz[v];
        if(sz[v]>sz[hvy[u]])
        {
            hvy[u]=v;
        }
    }
}

void dfs2(ll u,ll tp) 
{
    dfn[u]=++cnt;
    id[cnt]=u;
    top[u]=tp;
    
    if(!hvy[u])
    {
        return;
    }
    
    dfs2(hvy[u],tp);
    
    for(ll i=head[u];i;i=nxt[i])
    {
        ll v=to[i];
        if(v==par[u]||v==hvy[u])
        {
            continue;
        }
        
        dfs2(v,v);
    }
}

node merge(node x,node y)
{
    node ans;
    ans.sum=x.sum+y.sum;
    ans.lmx=max(x.lmx,x.sum+y.lmx);
    ans.rmx=max(y.rmx,y.sum+x.rmx);
    ans.mx=max(max(x.mx,y.mx),x.rmx+y.lmx);
    ans.lz=inf;
    
    return ans;
}

void pushup(ll p)
{
    tr[p]=merge(tr[p<<1],tr[p<<1|1]);
}

void build(ll p,ll l,ll r)
{
    if(l==r)
    {
        tr[p].sum=x[id[l]];
        tr[p].lmx=tr[p].rmx=tr[p].mx=max(tr[p].sum,0ll);
        tr[p].lz=inf;
        return;
    }
    
    ll mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    
    pushup(p);
}

void pushdown(ll p,ll l,ll r)
{
    if(tr[p].lz==inf)
    {
        return;
    }
    
    ll t=tr[p].lz;
    
    ll mid=(l+r)>>1;
    tr[p<<1].sum=(mid-l+1)*t;
    tr[p<<1].lmx=tr[p<<1].rmx=tr[p<<1].mx=max(tr[p<<1].sum,0ll);
    tr[p<<1].lz=t;
    tr[p<<1|1].sum=(r-mid)*t;
    tr[p<<1|1].lmx=tr[p<<1|1].rmx=tr[p<<1|1].mx=max(tr[p<<1|1].sum,0ll);
    tr[p<<1|1].lz=t;
    
    tr[p].lz=inf;
}

void update(ll x,ll y,ll p,ll l,ll r,ll k)
{
    if(x<=l&&r<=y)
    {
        tr[p].sum=(r-l+1)*k;
        tr[p].lmx=tr[p].rmx=tr[p].mx=max(tr[p].sum,0ll);
        tr[p].lz=k;
        return;
    }
    
    pushdown(p,l,r);
    
    ll mid=(l+r)>>1;
    if(x<=mid)
    {
        update(x,y,p<<1,l,mid,k);
    }
    if(mid<y)
    {
        update(x,y,p<<1|1,mid+1,r,k);
    }
    
    pushup(p);
}

node query(ll x,ll y,ll p,ll l,ll r)
{
    if(x<=l&&r<=y)
    {
        return tr[p];
    }
    
    pushdown(p,l,r);
    
    ll mid=(l+r)>>1;
    node L,R;
    if(x<=mid)
    {
        L=query(x,y,p<<1,l,mid);
    }
    if(mid<y)
    {
        R=query(x,y,p<<1|1,mid+1,r);
    }
    
    return merge(L,R);
}

void update_chain(ll u,ll v,ll k)
{
    ll fu=top[u],fv=top[v];
    
    while(fu!=fv)
    {
        if(dep[fu]<dep[fv])
        {
            swap(u,v);
            swap(fu,fv);
        }
        
        update(dfn[fu],dfn[u],1,1,n,k);
        u=par[fu],fu=top[u];
    }
    
    if(dep[u]>dep[v])
    {
        swap(u,v);
    }
    update(dfn[u],dfn[v],1,1,n,k);
}

node query_chain(ll u,ll v)
{
    node L,R;
    
    ll fu=top[u],fv=top[v];
    while(fu!=fv)
    {
        if(dep[fu]<dep[fv])
        {
            R=merge(query(dfn[fv],dfn[v],1,1,n),R);
            v=par[fv],fv=top[v];
        }
        else
        {
            L=merge(query(dfn[fu],dfn[u],1,1,n),L);
            u=par[fu],fu=top[u];
        }
    }
    
    if(dep[u]>dep[v])
    {
        L=merge(query(dfn[v],dfn[u],1,1,n),L);
    }
    else
    {
        R=merge(query(dfn[u],dfn[v],1,1,n),R);
    }
    
    swap(L.lmx,L.rmx);
    
    return merge(L,R);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
        cin>>x[i];
    }
    for(ll i=1;i<n;i++)
    {
        ll u,v;
        cin>>u>>v;
        add(u,v),add(v,u);
    }
    
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    
    cin>>q;
    while(q--)
    {
        ll op,a,b,c;
        cin>>op>>a>>b;
        
        if(op==1)
        {
            cout<<query_chain(a,b).mx<<"\n";
        }
        else
        {
            cin>>c;
            update_chain(a,b,c);
        }
    }
    
    return 0;
}
关注我

链接

分类

最新文章

归档

标签

Combinatorics1
Disjoint Set1
Dynamic Programming3
Euler's totient function1
Game Theory1
Graph Theory2
Monotonic queue1
Number theory1
Ordinary Generating Function1
Segment Tree4
Simulated Annealing1
Society1
Spanning Tree2
Teenagers1
Tree1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.

follow.it

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×