自娱自乐之GCD0.1
传送门：null
（此题是我在看jls的数论视频中看到的，纯属记录一下自己的心得）
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
给出一个包含 n 个整数得序列 a； 定义序列 a 上得两个操作： ①U L R D : ∀ i ∈[L,R] , a[i]=a[i]+d; ②Q L R : 询问GCD(a[L],a[L+1],....,a[R]) 给出你 m 次操作； 对于第 i 次操作，如果是②，输出GCD(a[L,...,R])；题目描述
样例输入 10 22 8 4 13 12 6 12 9 18 6 3 Q 2 2 Q 2 3 Q 4 6 Q 4 7 Q 7 8 U 1 10 1 Q 2 2 Q 2 3 Q 4 6 Q 4 7 Q 7 8 U 2 2 2 U 4 4 8 U 6 6 1 U 7 7 -3 U 8 8 2 U 10 10 10 Q 2 2 Q 2 3 Q 4 6 Q 4 7 Q 7 8 样例输出 4 1 6 3 9 5 1 1 1 1 7 7 7 7 7样例输入输出
题解：
引理：GCD(a,b,c) = GCD(a,b-a,c-b)
定义数组 b 为数组 a 的差分数组：
那么，由引理可得GCD(a[L,....R]) = GCD(a[L],b[L+1,....R])；
对于区间更新操作[L,R] + d；
用两个线段树来维护数组a和数组b；
其中维护的数组a就是常用的区间更新，懒惰标记操作；
维护的数组b就是单点插入，b中得L处增加d,R+1处减少d；
询问得话，先求出a[L]当前的值，在求出GCD(b[L+1,...,R])两者取GCD即可，注意答案要为正数；
代码：（没有OJ可以提交，写着玩的，不喜勿喷）
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<cmath> 6 using namespace std; 7 #define GCD(a,b) __gcd(a,b) 8 #define ls(x) (x<<1) 9 #define rs(x) (x<<1|1) 10 const int maxn=1e5+50; 11 12 int n,m;///n个数m次询问 13 int a[maxn]; 14 int b[maxn]; 15 struct SegA 16 { 17 int l,r; 18 int lazy; 19 int val; 20 int mid() 21 { 22 return l+((r-l)>>1); 23 } 24 }segA[maxn<<2]; 25 struct SegB 26 { 27 int l,r; 28 int gcd; 29 int mid() 30 { 31 return l+((r-l)>>1); 32 } 33 }segB[maxn<<2]; 34 35 void pushUp(int pos) 36 { 37 segB[pos].gcd=GCD(segB[ls(pos)].gcd,segB[rs(pos)].gcd); 38 } 39 void pushDown(int pos) 40 { 41 int &lazy=segA[pos].lazy; 42 if(lazy)///如果lazy != 0 执行一下代码，刚开始判断错了，写成if(!lazy)了 43 { 44 segA[ls(pos)].lazy=lazy; 45 segA[rs(pos)].lazy=lazy; 46 } 47 lazy=0; 48 } 49 void buildSegTree(int l,int r,int pos) 50 { 51 segA[pos].l=segB[pos].l=l; 52 segA[pos].r=segB[pos].r=r; 53 segA[pos].lazy=0; 54 if(l == r) 55 { 56 segA[pos].val=a[l]; 57 segB[pos].gcd=b[l]; 58 return ; 59 } 60 int mid=l+((r-l)>>1); 61 buildSegTree(l,mid,ls(pos)); 62 buildSegTree(mid+1,r,rs(pos)); 63 64 pushUp(pos); 65 } 66 void UpdateA(int l,int r,int val,int pos)///区间更新 67 { 68 if(segA[pos].l == l && segA[pos].r == r) 69 { 70 segA[pos].lazy += val; 71 return ; 72 } 73 pushDown(pos); 74 75 int mid=segA[pos].mid(); 76 if(r <= mid) 77 UpdateA(l,r,val,ls(pos)); 78 else if(l > mid) 79 UpdateA(l,r,val,rs(pos)); 80 else 81 { 82 UpdateA(l,mid,val,ls(pos)); 83 UpdateA(mid+1,r,val,rs(pos)); 84 } 85 } 86 int QueryA(int x,int pos)///单点查询 87 { 88 if(segA[pos].l == segA[pos].r) 89 return segA[pos].val+segA[pos].lazy; 90 91 pushDown(pos); 92 93 int mid=segA[pos].mid(); 94 if(x <= mid) 95 return QueryA(x,ls(pos)); 96 else 97 return QueryA(x,rs(pos)); 98 } 99 void UpdateB(int x,int val,int pos)///单点更新 100 { 101 if(segB[pos].l == segB[pos].r) 102 { 103 segB[pos].gcd += val; 104 return ; 105 } 106 int mid=segB[pos].mid(); 107 if(x <= mid) 108 UpdateB(x,val,ls(pos)); 109 else 110 UpdateB(x,val,rs(pos)); 111 pushUp(pos); 112 } 113 int QueryB(int l,int r,int pos)///区间查询 114 { 115 if(segB[pos].l == l && segB[pos].r == r) 116 return segB[pos].gcd; 117 118 int mid=segB[pos].mid(); 119 if(r <= mid) 120 return QueryB(l,r,ls(pos)); 121 else if(l > mid) 122 return QueryB(l,r,rs(pos)); 123 else 124 return GCD(QueryB(l,mid,ls(pos)),QueryB(mid+1,r,rs(pos))); 125 } 126 /////暴力程序，初始对拍用的 127 //int Query(int l,int r) 128 //{ 129 // int gcd=a[l]; 130 // for(int i=l;i <= r;++i) 131 // gcd=GCD(gcd,a[i]); 132 // return gcd; 133 //} 134 //void Update(int l,int r,int d) 135 //{ 136 // for(int i=l;i <= r;++i) 137 // a[i] += d; 138 //} 139 void Solve() 140 { 141 buildSegTree(1,n,1); 142 143 for(int i=1;i <= m;++i) 144 { 145 char order[10]; 146 scanf("%s",order); 147 if(order[0] == 'Q') 148 { 149 int l,r;///查询GCD(a[l,...,r]) 150 scanf("%d%d",&l,&r); 151 152 int gcd=QueryA(l,1);///线段树维护 153 if(l+1 <= r)///越界问题 154 gcd=GCD(gcd,QueryB(l+1,r,1)); 155 printf("%d\n",abs(gcd)); 156 157 // int gcd1=Query(l,r);///暴力 158 // printf("gcd1=%d,gcd=%d\n",abs(gcd1),abs(gcd)); 159 } 160 else 161 { 162 int l,r,d;///a[l,r]每个值增加d 163 scanf("%d%d%d",&l,&r,&d); 164 165 UpdateA(l,r,d,1); 166 UpdateB(l,d,1);///维护b的线段树中l处增加d,r+1处减少d 167 if(r+1 <= n)///防止越界 168 UpdateB(r+1,-d,1); 169 170 // Update(l,r,d);///暴力增加 171 } 172 } 173 } 174 int main() 175 { 176 // freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin); 177 while(~scanf("%d%d",&n,&m)) 178 { 179 for(int i=1;i <= n;++i) 180 { 181 scanf("%d",a+i); 182 b[i]=(i == 1 ? a[i]:a[i]-a[i-1]); 183 } 184 Solve(); 185 } 186 return 0; 187 }View Code
更多精彩
