发表更新Problem Solutions3 分钟读完 (大约444个字)

题解：CF438D The Child and Sequence

题目

思路

题目要求我们完成三种操作：

  • 区间求和
  • 区间取模
  • 单点修改

1，3两种都非常简单，问题在于如何维护区间取模。

可以想到维护区间最大值，如果小于模数则不处理，否则将这个区间重新pushup。

如何证明该复杂度？注意到，一个数最多会被取模 $log{a_i}$ 次，所以复杂度我 $O(nlog_nlog{\max{a_i}})$ 。

代码

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
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N=1e5+5;

ll n,m;
ll a[N];

struct segtree
{
    struct node
    {
        ll sum,mx;
    } tr[N*4];

    void pushup(ll p)
    {
        tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
        tr[p].mx=max(tr[p<<1].mx,tr[p<<1|1].mx);
    }

    void build(ll p,ll l,ll r)
    {
        if(l==r)
        {
            tr[p]={a[l],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]={y,y};
            return ;
        }

        ll mid=l+r>>1;
        if(x<=mid)
        {
            update(p<<1,l,mid,x,y);
        }
        else
        {
            update(p<<1|1,mid+1,r,x,y);
        }

        pushup(p);
    }


    void update_mod(ll p,ll l,ll r,ll x,ll y,ll v)
    {
        if(l==r)
        {
            tr[p].sum%=v;
            tr[p].mx%=v;
            return ;
        }

        ll mid=l+r>>1;
        if(x<=mid&&tr[p<<1].mx>=v)
        {
            update_mod(p<<1,l,mid,x,y,v);
        }
        if(y>mid&&tr[p<<1|1].mx>=v)
        {
            update_mod(p<<1|1,mid+1,r,x,y,v);
        }

        pushup(p);
    }


    ll query(ll p,ll l,ll r,ll x,ll y)
    {
        if(x<=l&&y>=r)
        {
            return tr[p].sum;
        }

        ll mid=l+r>>1;
        ll ret=0;
        if(x<=mid)
        {
            ret+=query(p<<1,l,mid,x,y);
        }
        if(y>mid)
        {
            ret+=query(p<<1|1,mid+1,r,x,y);
        }

        return ret;
    }
} T;

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

    cin>>n>>m;
    for(ll i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    T.build(1,1,n);

    while(m--)
    {
        ll typ,l,r;
        cin>>typ>>l>>r;
        if(typ==1)
        {
            cout<<T.query(1,1,n,l,r)<<"\n";
        }
        else if(typ==2)
        {
            ll x;
            cin>>x;
            T.update_mod(1,1,n,l,r,x);
        }
        else
        {
            T.update(1,1,n,l,r);
        }
    }

    return 0;
}

然而没有什么技巧。

发表更新Problem Solutions5 分钟读完 (大约742个字)

题解：Black And White / Flip and Combos

题目

题目描述

给你一个长度为n的01序列 a[1],…,a[n]

每次询问给定一个区间[l,r]，询问[l,r]里最长的连续的1的长度

每次修改给定一个区间[l,r]，将[l,r]里的a[i]变成1-a[i]（或者说异或1）

n, m <= 100000

输入格式

第一行一个n

第二行n个数，表示01序列初始状态

第三行一个m，接下来m行，每行有三个数x,l,r

若 x=0，表示一次查询，查询[l,r]里的最长连续1的长度

若 x=1，表示一次修改，将[l,r]里的数异或1

输出格式

对于输入里的每一个查询，输出一行一个整数，该询问的最长连续1的长度

思路

维护最长子串是经典的线段树，由于有01翻转修改，所以不能只存连续1串，也要存0.

思路可能和GSS有点像，都是维护区间最长前缀、后缀和子串（GSS是子序列），修改就翻转+重新pushup就行了。

其实不是很困难，但是线段树写起来非常易错（因为我很菜orz）

代码

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
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll N=100005;

ll n,m;
ll a[N];

struct node
{
	ll l[2],r[2],mx[2]; //最长前缀，最长后缀，最长子串 
	bool lz; //懒惰标记
} tr[N*4];

void pushup(ll p,ll l,ll r) 
{
	ll mid=l+r>>1;
	
	for(ll i=0;i<2;i++)
	{
		tr[p].l[i]=tr[p<<1].l[i];
		if(tr[p<<1].l[i]==mid-l+1) //如果左半个区间全是i，前缀加上右半个区间
		{
			tr[p].l[i]+=tr[p<<1|1].l[i];	
		}
		tr[p].r[i]=tr[p<<1|1].r[i];
		if(tr[p<<1|1].r[i]==r-mid) //如果右半个区间全是i，后缀加上左半个区间
		{
			tr[p].r[i]+=tr[p<<1].r[i];
		}
		tr[p].mx[i]=max(max(tr[p<<1].mx[i],tr[p<<1|1].mx[i]),tr[p<<1].r[i]+tr[p<<1|1].l[i]);
	}
}

void flip(ll p) //翻转修改 
{
	swap(tr[p].l[0],tr[p].l[1]);
	swap(tr[p].r[0],tr[p].r[1]);
	swap(tr[p].mx[0],tr[p].mx[1]);
}

void pushdown(ll p,ll l,ll r)
{
	if(l!=r)
	{
		tr[p<<1].lz^=1;
		tr[p<<1|1].lz^=1;
		flip(p<<1),flip(p<<1|1); //左儿子右儿子继续翻转
		
		tr[p].lz=0;
	}
}

void build(ll p,ll l,ll r)
{
	tr[p].lz=0;
	if(l==r) //叶子区间赋值，写得比较无用抽象
	{
		for(ll i=0;i<2;i++)
		{
			ll j=i;
			if(a[l]==0) 
			{
				j^=1;
			}
			tr[p].l[i]=tr[p].r[i]=tr[p].mx[i]=j;
		}
		return ;
	}
	
	ll mid=l+r>>1;
	
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	
	pushup(p,l,r);
}


void update(ll p,ll l,ll r,ll x,ll y)
{
	if(l>=x&&r<=y)
	{
		tr[p].lz^=1;
		flip(p);
		return ;
	}
	
	if(tr[p].lz)
	{
		pushdown(p,l,r);
	}
	
	ll mid=l+r>>1;
	if(mid>=y)
	{
		update(p<<1,l,mid,x,y);
	}
	else if(mid<x)
	{
		update(p<<1|1,mid+1,r,x,y);
	}
	else
	{
		update(p<<1,l,mid,x,y);
		update(p<<1|1,mid+1,r,x,y);	
	}
	
	pushup(p,l,r);
}

ll query(ll p,ll l,ll r,ll x,ll y)
{
	if(l>=x&&r<=y)
	{
		return tr[p].mx[1];
	}
	
	if(tr[p].lz)
	{
		pushdown(p,l,r);
	}
	
	ll mid=l+r>>1;
	if(mid>=y)
	{
		return query(p<<1,l,mid,x,y);
	}
	else if(mid<x)
	{
		return query(p<<1|1,mid+1,r,x,y);
	}
	else
	{
		ll m1=query(p<<1,l,mid,x,y); //左半个区间的mx
		ll m2=query(p<<1|1,mid+1,r,x,y); //右半个区间的mx
		
		ll m3=min(mid-x+1,tr[p<<1].r[1]); //左半个区间的最大后缀 
		ll m4=min(y-mid,tr[p<<1|1].l[1]); //右半个区间的最大前缀 
		
		return max(max(m1,m2),m3+m4);
	}
	
	pushup(p,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 q,l,r;
		cin>>q>>l>>r;
		
		if(q==1)
		{
			update(1,1,n,l,r);
		}
		else
		{
			cout<<query(1,1,n,l,r)<<"\n";
		}
	}
	
	
	return 0;
}

撒花！

发表更新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;
}
发表更新Ideas5 分钟读完 (大约710个字)

关于线段树的创新优化（原创）

原创！

这是一件伟大的事情，因为本文的核心诞生于2023年4月12日，距离我开始学习OI仅7个月。
但是当时我还是一名被各种碾压的蒟蒻，于是放弃更新本文，如今，作为略有提升的蒟蒻，我要完善它。

设想

这是对线段树的一个空间优化，因为我当时刚学线段树，还不知道有动态开点这个东西，但是我设想的这个线段树，是完全符合普通线段树的规则，只是略作修改，使其和动态开点线段树一样，变成一棵满二叉树。

哦对了，还有一点很特殊，当时写的线段树都是根为0的，所以左节点是p2+1，右节点是p\2+2。

建树

普通建树

线段树模板中我们使用的建树方式是将父节点/2下放给子节点的

这样，在设置数组的时候我们总共需要n*4的数组（实际上占了4n-1的空间），这样的建树方式简单明了，容易记忆，同时也广为流传。

优化——完全二叉树建树

但是，如果我们把这棵线段树建成完全二叉树，它的空间需求就可以从n4降到n2（实际为定值2n-1）（如图）

经过计算，我们只需要找到不小于现节点区间大小的最小二的幂num，如果现节点区间大小大于num的3/4，则分界点为l+num/2，否则为r-num/4。

代码如下:

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
struct
{
	int sum;
} tree[n<<1]; //线段树
int t=1; //填充

void pushup(ll p)
{
	tree[p].sum=tree[p*2+1].sum+tree[p*2+2].sum;
}

void build(ll p,ll l,ll r)
{
	if(l==r)
	{
		tree[p].sum=t;
		t++;
		return;
	}
	
	//这里可能会使常数大一些
	//就是求不小于r-l+1即区间大小的2的幂 
	int num=pow(2,__lg(r-l+1));
	if((r-l+1)>num)
	{
		num<<=1;
	}
	
	//这个我目前没有证明 
	ll mid;
	if(r-l+1>num/4*3)
	{
		mid=l+num/2-1;
	}
	else
	{
		mid=r-num/4;
	}
	
	build(p*2+1,l,mid);
	build(p*2+2,mid+1,r);
	
	pushup(p);
}

这种建树方法将空间复杂度减少了一半。
事实上，因为完全二叉树的特性，我们也可以用循环建树，代码如下：

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
struct
{
  int sum;
}tree[n<<1];//线段树

void build(ll n)
{
	int num=pow(2,__lg(n));
	if(n>num)
	{
		num<<=1;
	}
	
	int a=2*n-num;
	int b=n;
	int i;
	for(i=2*n-2;a>=1;a--,i--)
	{
		tree[i].sum=a;
	}
	a=2*n-num;
	for(;b>a;b--,i--)
	{
		tree[i].sum=b;
	}
	for(;i>=0;i--)
	{
		tree[i].sum=tree[i*2+1].sum+tree[i*2+2].sum;
	}
}

更新

普通更新

线段树的更新为：从上至下分发懒惰标记，在从下至上重新pushup。
这里不再赘述。

优化——完全二叉树更新

关注我

链接

分类

最新文章

归档

标签

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

×

×