线段树训练

GSS3 - Can you answer these queries III

题面翻译

\(n\) 个数，\(q\) 次操作

操作0 x y把\(A_x\) 修改为\(y\)

操作1 l r询问区间\([l, r]\) 的最大子段和

感谢 @Edgration 提供的翻译

题目描述

You are given a sequence A of N (N <= 50000) integers between -10000 and 10000. On this sequence you have to apply M (M <= 50000) operations:
modify the i-th element in the sequence or for given x y print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.

输入格式

The first line of input contains an integer N. The following line contains N integers, representing the sequence A1..AN.
The third line contains an integer M. The next M lines contain the operations in following form:
0 x y: modify Ax into y (|y|<=10000).
1 x y: print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.

输出格式

For each query, print an integer as the problem required.

样例 #1

样例输入 #1

1
2
3
4
5
6
7
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3

样例输出 #1

1
2
3
6
4
-3
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
#include<bits/stdc++.h>
using namespace std;
const int N = 2000001;
int n, m;
struct Tree
{
	int l, r;
	long long maxleft, maxright, sum,ans;
}tree[N];
//pushup部分
void pushup(int u)
{
	tree[u].sum = tree[u*2].sum + tree[u *2+1].sum;
	tree[u].maxleft = max(tree[u*2].maxleft, tree[u *2].sum + tree[u*2+1].maxleft);
	tree[u].maxright = max(tree[u*2+1].maxright, tree[u *2].maxright + tree[u *2+1].sum);
	tree[u].ans = max(max(tree[u*2].ans, tree[u*2+1].ans), tree[u*2].maxright + tree[u*2+1].maxleft);
}
//建树
void build(int l, int r, int u)
{
	tree[u].l = l;
	tree[u].r = r;
	if (l == r)
	{
		cin >> tree[u].sum;
		tree[u].maxleft = tree[u].maxright = tree[u].ans = tree[u].sum;
		return;
	}
	int mid = (l + r)/2;
	build( l, mid,2*u);
	build( mid + 1, r,2*u+1);
	pushup(u);
}
Tree query(int u, int l, int r)
{
	if (l <= tree[u].l && tree[u].r <= r)
	{
		return tree[u];
	}
	int mid =(tree[u].l + tree[u].r)/2;
	if (r <= mid)
	{
	return 	query(u * 2,l, r);
	}
	else
	{
		if (l > mid)
		{
		return 	query(u * 2 + 1, l, r);
		}
		else
            //这里不太好理解
		{
			Tree t, a = query(u * 2, l, r), b = query(u * 2 + 1, l, r);
			t.maxleft = max(a.maxleft, a.sum + b.maxleft);//做类似的合并区间
			t.maxright = max(b.maxright, a.maxright + b.sum);
			t.ans = max(max(a.ans, b.ans), a.maxright + b.maxleft);
			return t;
		}
	}
}
//单点修改
void update(int u, int x, int y)
{
	if (tree[u].l == tree[u].r)
	{
		tree[u].maxleft = tree[u].maxright = tree[u].ans = tree[u].sum = y;
		return;
	}
	int mid = (tree[u].l + tree[u].r) / 2;
	if (x <= mid)
	{
		update(u * 2, x, y);
	}
	else update(u * 2 + 1, x, y);
	pushup(u);
}
int main()
{
	cin >> n;
	build(1, n, 1);
	cin >> m;
	while (m--)
	{
		int opt, x, y;
		cin >> opt >> x >> y;
		if (opt == 1)
		{
			if (x > y)
			{
				swap(x, y);
			}//坑
			Tree t = query(1, x, y);
			cout << t.ans << '\n';
		}
		else
		{
			update(1, x, y);
		}
	}
	return 0;
}

interval GCD

【题目】

给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一： 1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。 2、“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。 对于每个询问，输出一个整数表示答案。

区间gcd再加区间修改。

一般求gcd的时候辗转相除法。

gcd(x,y)=gcd(x,y-x)

那么可以把这个公式推到3个项。

gcd(x,y,z)=gcd(x,y-x,z-y)

可以看出来这是一个差分数列。

原数列为a[],差分数列为b[]。

这样就可以用线段树在b[]上单点修改，l加上d，r+1减去d。

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

#define ls u<<1
#define rs u<<1|1
const int N=500010;
typedef long long LL;
int n,m; LL a[N],b[N];
struct Tree{ //线段树
  int l,r;
  LL sum,d; //差分序列的区间和,最大公约数
}tr[N*4];

LL gcd(LL a,LL b){
  return b ? gcd(b,a%b) : a;
}
void pushup(Tree &u,Tree l,Tree r){
  u.sum=l.sum+r.sum;
  u.d=gcd(l.d,r.d);
}
void build(int u,int l,int r)
{ //建树
  tr[u]={l,r,b[l],b[l]};
  if(l==r) return;
  int mid=l+r>>1;
  build(ls,l,mid);
  build(rs,mid+1,r);
  pushup(tr[u],tr[ls],tr[rs]);
}
void change(int u,int x,LL v)
{ //点修
  if(tr[u].l==tr[u].r){
    tr[u].sum+=v; tr[u].d+=v;
    return;
  }
  int mid=tr[u].l+tr[u].r>>1;
  if(x<=mid) change(ls,x,v);
  else change(rs,x,v);
  pushup(tr[u],tr[ls],tr[rs]);
}
Tree query(int u,int l,int r){ //区查
  if(l<=tr[u].l && tr[u].r<=r) return tr[u];
  int mid=tr[u].l+tr[u].r>>1;
  if(r<=mid) return query(ls,l,r);
  if(l>mid) return query(rs,l,r);
  Tree T; //开一个临时节点，存储拼凑结果
  pushup(T,query(ls,l,r),query(rs,l,r));
  return T;
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++) 
    cin>>a[i], b[i]=a[i]-a[i-1];
  build(1,1,n);
  while(m --){
    char c[1]; int l,r; 
      cin>>c>>l>>r;
    if(*c=='C'){
      LL v;
      cin>>v;
      change(1,l,v);
      if(r+1<=n) change(1,r+1,-v);
        //r=n时,越界
    }
    else
    {
      Tree L, R={0,0,0,0};
      L=query(1,1,l);     //a[l]=sum(b[1~l])
      if(l+1<=r) R=query(1,l+1,r);
        //b[l+1~r]的gcd
     cout<<abs(gcd(L.sum, R.d));
    }
  }
  return 0;
}