Myhchael原创题系列 Mychael vs Kid 【题解】-白红宇

Myhchael原创题系列 Mychael vs Kid 【题解】

阅读量：5252 次

发布时间：2019-06-14

本文共 4479 字，大约阅读时间需要 14 分钟。

题目链接

题解

先说说这题的由来及前身

前身

首先有一个很经典的题目：

维护区间加，查询区间\(gcd\)

如果强行用线段树维护的话，区间加之后就没法直接确定当前区间的\(gcd\)，不可直接维护

这个时候就用到了\(gcd\)的一个性质：

\[(a,b) = (a - b,b)\]

三个的\(gcd\)也是符合的：

\[(a,b,c) = (a,b,c - b) = (a,b - a,c - b)\]

同样可以推广出\(n\)个的情况

\[gcd\{a_i\} = gcd(a_1,gcd\{a_j - a_{j - 1}\}) \qquad i \in [1,n] \quad j \in [2,n]\]

也就是说，区间差分了之后，我们要求原区间\(gcd[l,r]\)，就相当于求\(a_l\)和差分后区间\([l + 1,r]\)的\(gcd\)

所以我们只需维护差分区间和区间每个位置的值即可

维护区间值用线段树一点问题都没有

在加法下维护差分区间，一个区间加上一个数，仅影响区间端点的值，所以单点修改即可

所以我们开两棵线段树，一棵维护权值，一棵维护差值的\(gcd\)，即可\(O(nlog^2n)\)解决这道题

本题

本题多加入了一个区间乘法操作

本来想\(yy\)分块的，可后来发现线段树依旧可写~~并且暴艹分块~~

思考一下发现，区间乘法后，区间差分值也乘上那个数，对应\(gcd\)也乘上一个数，可以使用线段树维护

至于端点的差值改变，只需取出端点的值计算出差值后单点加法修改即可

复杂度依旧是\(O(nlog^2n)\)

部分分

前\(5\%\)，咳，，，

对于\(n,m \le 300\)，暴力求即可

对于没有操作\(2\)的，就是原版题目

对于\(n,m \le 3 \times 10^4\)的，可以考虑分块

std

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define mp(a,b) make_pair
          
           (a,b)#define cls(s) memset(s,0,sizeof(s))#define cp pair
           
            #define LL long long int#define ls (u << 1)#define rs (u << 1 | 1)using namespace std;const int maxn = 100005,maxm = 100005,INF = 1000000000;inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();} return out * flag;}LL n,m,A[maxn],D[maxn];LL gcd(LL a,LL b){ if (a < 0) a = -a; if (b < 0) b = -b; return b ? gcd(b,a % b) : a;}struct Seg_Gcd{ LL Gcd[maxn << 2],tag[maxn << 2]; void upd(int u){ Gcd[u] = gcd(Gcd[ls],Gcd[rs]); } void pd(int u){ if (tag[u] != 1){ Gcd[ls] *= tag[u]; tag[ls] *= tag[u]; Gcd[rs] *= tag[u]; tag[rs] *= tag[u]; tag[u] = 1; } } void build(int u,int l,int r){ tag[u] = 1; if (l == r){ Gcd[u] = D[l]; return; } int mid = l + r >> 1; build(ls,l,mid); build(rs,mid + 1,r); upd(u); } void Add(int u,int l,int r,int pos,int v){ if (l == r){Gcd[u] += v; return;} pd(u); int mid = l + r >> 1; if (mid >= pos) Add(ls,l,mid,pos,v); else Add(rs,mid + 1,r,pos,v); upd(u); } void Mult(int u,int l,int r,int L,int R,int v){ if (l >= L && r <= R){Gcd[u] *= v; tag[u] *= v; return;} pd(u); int mid = l + r >> 1; if (mid >= L) Mult(ls,l,mid,L,R,v); if (mid < R) Mult(rs,mid + 1,r,L,R,v); upd(u); } LL query(int u,int l,int r,int L,int R){ if (l >= L && r <= R) return Gcd[u]; pd(u); int mid = l + r >> 1; if (mid >= R) return query(ls,l,mid,L,R); if (mid < L) return query(rs,mid + 1,r,L,R); return gcd(query(ls,l,mid,L,R),query(rs,mid + 1,r,L,R)); }}T2;struct Seg{ LL val[maxn << 2],mult[maxn << 2],add[maxn << 2]; void pd(int u){ if (mult[u] != 1){ val[ls] *= mult[u]; mult[ls] *= mult[u]; add[ls] *= mult[u]; val[rs] *= mult[u]; mult[rs] *= mult[u]; add[rs] *= mult[u]; mult[u] = 1; } if (add[u]){ val[ls] += add[u]; add[ls] += add[u]; val[rs] += add[u]; add[rs] += add[u]; add[u] = 0; } } void build(int u,int l,int r){ add[u] = 0; mult[u] = 1; if (l == r){ val[u] = A[l]; return; } int mid = l + r >> 1; build(ls,l,mid); build(rs,mid + 1,r); } void Add(int u,int l,int r,int L,int R,int v){ if (l >= L && r <= R){val[u] += v; add[u] += v; return;} pd(u); int mid = l + r >> 1; if (mid >= L) Add(ls,l,mid,L,R,v); if (mid < R) Add(rs,mid + 1,r,L,R,v); } void Mult(int u,int l,int r,int L,int R,int v){ if (l >= L && r <= R){val[u] *= v; add[u] *= v; mult[u] *= v; return;} pd(u); int mid = l + r >> 1; if (mid >= L) Mult(ls,l,mid,L,R,v); if (mid < R) Mult(rs,mid + 1,r,L,R,v); } LL query(int u,int l,int r,int pos){ if (l == r) return val[u]; pd(u); int mid = l + r >> 1; if (mid >= pos) return query(ls,l,mid,pos); return query(rs,mid + 1,r,pos); }}T1;int main(){ n = read(); m = read(); for (int i = 1; i <= n; i++){ A[i] = read(); D[i] = A[i] - A[i - 1]; } T1.build(1,1,n); T2.build(1,1,n); LL opt,l,r,v,t1,t2; while (m--){ opt = read(); l = read(); r = read(); if (opt == 1){ v = read(); T1.Add(1,1,n,l,r,v); T2.Add(1,1,n,l,v); if (r + 1 <= n) T2.Add(1,1,n,r + 1,-v); } else if (opt == 2){ v = read(); t1 = T1.query(1,1,n,l); if (r + 1 <= n) t2 = T1.query(1,1,n,r); if (l < r) T2.Mult(1,1,n,l + 1,r,v); T2.Add(1,1,n,l,t1 * v - t1); if (r + 1 <= n) T2.Add(1,1,n,r + 1,t2 - t2 * v); T1.Mult(1,1,n,l,r,v); } else { if (l < r) printf("%lld\n",gcd(T1.query(1,1,n,l),T2.query(1,1,n,l + 1,r))); else printf("%lld\n",T1.query(1,1,n,l)); } } return 0;}