-
CFdiv1+2-Bash and a Tough Math Puzzle-(线段树维护gcd+单点+区间)
题意：
就是有一个n的数组，然后有m次操作，有两种，一种是让va[a] = b，一种是问你l到r这段区间的gcd是否接近x。接近x的定义是，要么等于x，要么你改变这段区间的一个数再等于x。思考：
1.看到这题，首先想到了gcd的性质，gcd(a1,a2,a3) = gcd(a1,a2-1,a3-a2)。也就是这一段区间的差分的gcd。但是这个题目用不到，因为每次修改一个数，也就是单点修改，就直接维护gcd就行了。只要具有区间可合并性的各种题目，比如最值，总和，区间GCD。如果有单点修改，那就可以直接线段树。如果去区间修改的话，一般就要看看这个维护的东西的性质了。
2.然后就是是否接近x，最多让你修改一个数。这就和我以前做的那个线段树维护hash二分判断是否两个字符串接近的题目差不多科学幻想。对于可以删掉一个，那么就可以二分得到不一样的地方在哪，然后这里可以修改，剩下的左右两端区间必须要符合题意。
3.写完发现超时了。因为这样的复杂度是m*log(n)*log(n)。2e8吧，但是就超时了。所以就要换个判断方法。这时候想到以前做过的那道题：浙江省赛-Bin Packing Problem。这个题要找个最左端可以装下x的点，如果也二分去找，也超时了。然后就直接在树上找，对于l到r，看看左子树的最大值是否>=x，如果可以往左右，如果不可以往右走。直到搜到叶子节点，把x装下去就行了。如果最终没找到，那么就开一个新的盒子。
4.所以这个题也可以这样，直接在树上搜，这样复杂度是log(n)的，因为每次都可以扔掉一半，只去不合法的那一半。这个题，如果左区间的gcd不是x的倍数，就走左边，如果右边不是走右边。如果两边都不是那么就直接非法，因为最多改掉一个数，这样就出现两个不合法的了。当然对于这段区间在查询的区间范围内，但是都合法，就直接不搜了。两种不同的写法而已。一种是：就是刚才描述的，看看哪边不合法就走哪边，如果两边都不合法就是非法直接退出。一种是：就看看有多少非法的个数，累加起来，每次左右搜，但是这样两边都会搜，但是你写上如果这段区间都合法就return 0就可以，这样就不会搜下去了。
5.刚开始我以为最多一个点不等于x，然后其余的gcd==x。实际上，应该是看是否为x的倍数，因为6 6 12也是接近3的，因为我把其中一个改成3，剩下的区间gcd都是3的倍数也可以。当然求的时候，gcd可能是负数，取绝对值就可以了。但是正负不影响取模的是否=0的事。代码：
#include#define fi first #define se second #define pb push_back #define db double #define int long long #define PII pair<int,int > #define mem(a,b) memset(a,b,sizeof(a)) #define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #define node_l node<<1 #define node_r node<<1|1 using namespace std; const int mod = 1e9+7,inf = 1e18; const int N = 5e5+20,M = 2010; int T,n,m,k; int va[N]; int maxn = 0; int gcd(int a,int b) { if(!b) return a; return gcd(b,a%b); } struct seg_gcd { struct node{ int L,R; int ans; }t[4*N]; void pushup(int node) { t[node].ans = gcd(t[node_l].ans,t[node_r].ans); } void build(int node,int l,int r) { t[node].L = l,t[node].R = r; if(l==r) { t[node].ans = va[l]; return ; } int mid = (l+r)>>1; build(node_l,l,mid);build(node_r,mid+1,r); pushup(node); } void update(int node,int x,int value) { if(t[node].L==x&&t[node].R==x) { t[node].ans = value; return ; } int mid = (t[node].L+t[node].R)>>1; if(x<=mid) update(node_l,x,value); else update(node_r,x,value); pushup(node); } int query(int node,int l,int r) { if(t[node].L>=l&&t[node].R<=r) return t[node].ans; int mid = (t[node].L+t[node].R)>>1; if(r<=mid) return query(node_l,l,r); else if(l>mid) return query(node_r,l,r); else return gcd(query(node_l,l,mid),query(node_r,mid+1,r)); } int check(int node,int l,int r,int c) { if(maxn>=2) return maxn; //如果此时非法了，就直接return 2 if(t[node].L>=l&&t[node].R<=r&&t[node].ans%c==0) return 0; //如果这段区间没必要搜下去了,这里会省去很多时间，因为如果可以的话，每次只有一半区间是不合法的。 if(t[node].L==t[node].R) return (t[node].ans%c!=0); //如果这个一个点是非法的就要操作一次 int mid = (t[node].L+t[node].R)>>1; if(r<=mid) return maxn = check(node_l,l,r,c); else if(l>mid) return maxn = check(node_r,l,r,c); else return maxn = check(node_l,l,mid,c)+check(node_r,mid+1,r,c); } }t_gcd; signed main() { IOS; cin>>n; for(int i=1;i<=n;i++) cin>>va[i]; t_gcd.build(1,1,n); cin>>m; while(m--) { int op,a,b,c; cin>>op; if(op==1) { cin>>a>>b>>c; maxn = 0; if(t_gcd.check(1,a,b,c)<=1) cout<<"YES\n"; else cout<<"NO\n"; } else { cin>>a>>b; t_gcd.update(1,a,b); } } return 0; } /* 二分超时的写法 bool check(int l,int r,int c) { int anw = t_gcd.query(1,l,r); return anw%c==0; } if(op==1) { cin>>a>>b>>c; int l = a,r = b; while(l - 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
题意：
就是给你一个n的数组，有两种操作，一种是让一段区间的数都加上D，一种是查询这一段区间的gcd。思考：
1.这题很明显就和上一题不同，这里是区间修改，这样你就没法直接维护了。但是gcd有个性质，就是gcd(a1,a2,a3)=gcd(a1,a2-a1,a3-a2)也就是一些数的gcd就是他们差分的gcd。但是这个能干什么呢？
2.如果我们线段树维护这个数组的差分，那么区间修改对应差分来说就是单点修改，就是修改l和r+1这两个点。但是你维护差分，虽然把区间修改变成单点修改了，但是你怎么求gcd呢？
3.这里就用到了那个公式，维护差分的gcd。但是只能求出来1到n这一个区间的gcd呀，如果求l和r这段区间的gcd呢？直接query(l,r)求出来的不是l到r的gcd，因为你l点的值是va[l]-va[l-1]，而应该是va[l]-0。所以每次你还要知道va[l]的值什么，然后gcd(va[l],query(l+1,r))这个就是真正的l到r的gcd。
4.所以由于我们维护的是差分，那么如果我们对差分再维护一个区间和，是不是如果查询query_sum(1,l)的值，这个值是不是就是真正的va[l]，因为差分的前缀和就是原本的值。其实我们发现，对差分数组维护区间和，但是我们实际上只要求1到i的值，也就是前缀和。所以这个前缀和也可以用树状数组来维护。每次修改也是修改l和r+1就可以了。但是只写一个线段树更方便，所以这里就用线段树维护了。
5.到这里就可以维护区间修改的gcd了。但是每次查询区间gcd的复杂度是2*log(n)。因为每次你还要查询一个差分的前缀和。代码：
#include#define fi first #define se second #define pb push_back #define db double #define int long long #define PII pair<int,int > #define mem(a,b) memset(a,b,sizeof(a)) #define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #define node_l node<<1 #define node_r node<<1|1 using namespace std; const int mod = 1e9+7,inf = 1e18; const int N = 5e5+20,M = 2010; int T,n,m,k; int va[N],vb[N]; int gcd(int a,int b) { if(!b) return a; return gcd(b,a%b); } struct seg_gcd { struct node{ int L,R; int sum,ans; }t[4*N]; void pushup(int node) { t[node].sum = t[node_l].sum+t[node_r].sum; t[node].ans = gcd(t[node_l].ans,t[node_r].ans); } void build(int node,int l,int r) { t[node].L = l,t[node].R = r; if(l==r) { t[node].sum = vb[l]; t[node].ans = vb[l]; return ; } int mid = (l+r)>>1; build(node_l,l,mid);build(node_r,mid+1,r); pushup(node); } void update(int node,int x,int value) { if(t[node].L==x&&t[node].R==x) { t[node].sum += value; t[node].ans += value; return ; } int mid = (t[node].L+t[node].R)>>1; if(x<=mid) update(node_l,x,value); else update(node_r,x,value); pushup(node); } int query1(int node,int l,int r) { if(l>r) return 0; if(t[node].L>=l&&t[node].R<=r) return t[node].ans; int mid = (t[node].L+t[node].R)>>1; if(r<=mid) return query1(node_l,l,r); else if(l>mid) return query1(node_r,l,r); else return gcd(query1(node_l,l,mid),query1(node_r,mid+1,r)); } int query2(int node,int l,int r) { if(t[node].L>=l&&t[node].R<=r) return t[node].sum; int mid = (t[node].L+t[node].R)>>1; if(r<=mid) return query2(node_l,l,r); else if(l>mid) return query2(node_r,l,r); else return query2(node_l,l,mid)+query2(node_r,mid+1,r); } }t_gcd; signed main() { IOS; cin>>n>>m; for(int i=1;i<=n;i++) cin>>va[i]; for(int i=1;i<=n;i++) vb[i] = va[i]-va[i-1]; t_gcd.build(1,1,n); while(m--) { char op; int a,b,c; cin>>op; if(op=='C') { cin>>a>>b>>c; t_gcd.update(1,a,c); if(b+1<=n) t_gcd.update(1,b+1,-c); } else { cin>>a>>b; int anw = abs(gcd(t_gcd.query1(1,a+1,b),t_gcd.query2(1,1,a))); //gcd可能求出来是负数，取个绝对值就可以了。 cout<<anw<<"\n"; } } return 0; } - 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
题意：
就是给你个n数组，有三种操作，一种是让l到r区间的数都加上x，一种是查询l到r所有相邻数差的绝对值的最大值，一种是询问l到r区间的最大公约数。思考：
1.很明显，这题就是比上一题多了一个，查询所有相邻数差的绝对值的最大值。当然如果l==r，也就是只有一个数，那么就没有相邻了，答案就是0。
2.这怎么维护呢，其实对于差，很明显就是对差分数组维护区间最大值。然后修改的话，对于差分数组而言，修改一段区间就是修改两个端点，所以修改的时候也是单点修改，但是一定要先在vb这个原数组修改后，再让线段树里面的值 = abs(vb[l])。因为本身维护的是绝对值，并不是本身的值，如果你加上一个x，是不对的。比如本身是-2，+2后应该为0，但是线段树维护的是绝对值也就是本身是2,+2后变成4了就不对了。同时呢也要注意，比如查询l到r的差的绝对值最大值，l前面是没有数的，所以我们只看每个数减去前面的数的差就可以了，所以l这个点的值我们就不能看。也就是query(l+1,r)。还要注意的是，差分数组的第一个元素的值不能放进线段树里面，因为它前面是没有值的，算进去的话就会让这个线段树的最大值可能变大。反正要考虑好细节，到底怎么维护的。代码：
#include#define fi first #define se second #define pb push_back #define db double #define int long long #define PII pair<int,int > #define mem(a,b) memset(a,b,sizeof(a)) #define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #define node_l node<<1 #define node_r node<<1|1 using namespace std; const int mod = 1e9+7,inf = 1e18; const int N = 2e5+20,M = 2010; int T,n,m,k; int va[N],vb[N]; int gcd(int a,int b) { if(!b) return a; return gcd(b,a%b); } struct seg_gcd { struct node{ int L,R; int sum,ans,maxn; }t[4*N]; void pushup(int node) { t[node].sum = t[node_l].sum+t[node_r].sum; t[node].ans = gcd(t[node_l].ans,t[node_r].ans); t[node].maxn = max(t[node_l].maxn,t[node_r].maxn); } void build(int node,int l,int r) { t[node].L = l,t[node].R = r; if(l==r) { t[node].sum = vb[l]; t[node].ans = vb[l]; if(l>1) t[node].maxn = abs(vb[l]); //1号点不更新 return ; } int mid = (l+r)>>1; build(node_l,l,mid);build(node_r,mid+1,r); pushup(node); } void update(int node,int x,int value) { if(t[node].L==x&&t[node].R==x) { t[node].sum += value; t[node].ans += value; if(x>1) t[node].maxn = abs(vb[x]); //1号点永远都不更新 return ; } int mid = (t[node].L+t[node].R)>>1; if(x<=mid) update(node_l,x,value); else update(node_r,x,value); pushup(node); } int query1(int node,int l,int r) { if(l>r) return 0; if(t[node].L>=l&&t[node].R<=r) return t[node].ans; int mid = (t[node].L+t[node].R)>>1; if(r<=mid) return query1(node_l,l,r); else if(l>mid) return query1(node_r,l,r); else return gcd(query1(node_l,l,mid),query1(node_r,mid+1,r)); } int query2(int node,int l,int r) { if(t[node].L>=l&&t[node].R<=r) return t[node].sum; int mid = (t[node].L+t[node].R)>>1; if(r<=mid) return query2(node_l,l,r); else if(l>mid) return query2(node_r,l,r); else return query2(node_l,l,mid)+query2(node_r,mid+1,r); } int query3(int node,int l,int r) { if(t[node].L>=l&&t[node].R<=r) return t[node].maxn; int mid = (t[node].L+t[node].R)>>1; if(r<=mid) return query3(node_l,l,r); else if(l>mid) return query3(node_r,l,r); else return max(query3(node_l,l,mid),query3(node_r,mid+1,r)); } }t_gcd; signed main() { IOS; cin>>n>>m; for(int i=1;i<=n;i++) cin>>va[i]; for(int i=1;i<=n;i++) vb[i] = va[i]-va[i-1]; t_gcd.build(1,1,n); while(m--) { int op,a,b,c; cin>>op>>a>>b; if(op==1) { cin>>c; vb[a] += c; t_gcd.update(1,a,c); if(b+1<=n) { vb[b+1] -= c; t_gcd.update(1,b+1,-c); } } if(op==2) { if(a==b) cout<<0<<"\n"; else cout<<t_gcd.query3(1,a+1,b)<<"\n"; } if(op==3) { int anw = abs(gcd(t_gcd.query1(1,a+1,b),t_gcd.query2(1,1,a))); cout<<anw<<"\n"; } } return 0; } - 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
总结：
多多思考，注意细节，多多注意各种细致的点。 -
相关阅读:
Bootstrap警告和轮播插件详解【前端Bootstrap框架】
Python-日志模块
===、==、Object.is 基本包装类型
java毕业设计校园资料在线分享网站mybatis+源码+调试部署+系统+数据库+lw
通达OA与think PHP对接
Oracle创建Trigger报错
PG索引失败排查记录
优维EasyOps，打造新一代运维新方式
Beego之Beego简介和安装
STM32 RTC实验
- 原文地址：https://blog.csdn.net/m0_52398496/article/details/126031911
