牛客 2022年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛 签到题13题_2022gplt团体程序设计天梯赛a+b

序

题号 标题 已通过代码 通过率 我的状态
A A+B Problem 点击查看 1705/4843 通过， （贪心）
B Komorebi的数学课 点击查看 1372/5349 通过 （快速幂）
C 次佛锅 点击查看 1070/5160 通过 （字符串STL）
D Setsuna的K数列 点击查看 597/2425 通过 （二进制）di
E Wiki下象棋 点击查看 308/2312 通过（BFS最短路）
F 黄金律法 点击查看 1286/3529 通过（排序不等式）
G 天气预报 点击查看 184/2800 通过（前缀和，尺取法） die
H 叠硬币 点击查看 67/702 通过（背包dp，打印方案）die
I A+B Problem again 点击查看 27/512 通过（数据敏感，字典树）die
J 史东薇尔城 点击查看 461/4005 通过（Dijkstra板子）
K 取模 点击查看 207/3545 通过（数论分块板子）die
L 剪绳子 点击查看 84/593 通过（STL集合二分）di
M 数硬币 点击查看 34/385 通过（线段树板子）di
N 截肢葛瑞克 点击查看 0/288 未通过
O 上海施工小学 点击查看 5/1817 未通过

1、A+B Problem

• 找到最大值和次大值，如果当前数字不是最大值就加最大值，不然就加次大值

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
int a[maxn], f[maxn];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;   cin>>n;
    if(n==1){
        int x;  cin>>x;  cout<<x;
        return 0;
    }
    for(int i = 1; i <= n; i++){
        cin>>a[i];  f[i] = a[i];
    }
    sort(f+1,f+n+1);
    for(int i = 1; i <= n; i++){
        if(a[i]!=f[n])cout<<a[i]+f[n]<<" ";
        else cout<<a[i]+f[n-1]<<" ";
    }
    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

2、Komorebi的数学课

• 显然是一个快速幂板子题

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
LL pows(LL a, LL x, LL p){if(x==0)return 1; LL t = pows(a, x>>1,p);if(x%2==0)return t*t%p;return t*t%p*a%p;}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    LL n;  cin>>n;
    cout<<pows(n,n,n+2);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11

3、次佛锅

• 判断T次询问的字符串在第一行位置后面的数字。
• stringsteam加到map里面，直接输出就行

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    string s;  getline(cin,s);
    stringstream ss(s);
    map<string,int>ma;
    int x;
    while(ss>>s>>x){
        ma[s]+=x;
    }
    int T;  cin>>T;
    while(T--){
        cin>>s;
        cout<<ma[s]<<"\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

4、Setsuna的K数列

• 一开始没想到一直不知道怎么暴力，后来自己想想就是一个进制枚举
• 考虑3^0，3^1，3^2，3^3，，，3^n各自可以使用0次或1次，那么就是选或者不选的问题
• 那么就是判断第n个数的二进制位是否是1，如果是1就加上对应的3^i即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 1e7+10,mod=1e9+7;
LL pows(LL a, LL x, LL p){if(x==0)return 1; LL t = pows(a, x>>1,p);if(x%2==0)return t*t%p;return t*t%p*a%p;}
int a[maxn];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    LL n, k;  cin>>n>>k;
    LL w = n, ans = 0, t = 1;
    while(w){
        if(w&1){
            ans = (ans+t)%mod;
        }
        t = t*k%mod;
        w >>= 1;
    }
    cout<<ans<<"\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

5、Wiki下象棋

• 给出两种走位方式，分别求起点到终点的最短路
• 直接bfs暴力即可

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL pows(LL a, LL x, LL p){if(x==0)return 1; LL t = pows(a, x>>1,p);if(x%2==0)return t*t%p;return t*t%p*a%p;}
int a[310][310];

struct node{int x, y,st=0;};
int vis[310][310];
int n, m;
int k, sx,sy, ex, ey;
int dx[] = {-2,-2,2,2,-1,1,-1,1};
int dy[] = {1,-1,1,-1,-2,-2,2,2};
int bfs(int ok){
    memset(vis,0,sizeof(vis));
    queue<node>q;
    q.push({sx,sy,0});
    while(q.size()){
        node t = q.front();  q.pop();
        if(t.x==ex&&t.y==ey){
            return t.st;
        }
        for(int i = 0; i < 8; i++){
            int nx = t.x+dx[i], ny = t.y+dy[i];
            if(nx<1||nx>n||ny<1||ny>m)continue;
            if(a[nx][ny])continue;
            if(vis[nx][ny])continue;
            if(ok==1){
                if(abs(dx[i])==2){
                    if(a[t.x+dx[i]/2][t.y]==1){///||a[t.x+dx[i]][t.y]==1
                        continue;
                    }
                }else{
                    if(a[t.x][t.y+dy[i]/2]==1){//||a[t.x][t.y+dy[i]]==1
                        continue;
                    }
                }
            }
            q.push({nx,ny,t.st+1});
            vis[nx][ny] = 1;
        }
    }
    return -1;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        cin>>n>>m;
        cin>>k>>sx>>sy>>ex>>ey;
        memset(a,0,sizeof(a));
        for(int i = 1; i <= k; i++){
            int tx, ty;  cin>>tx>>ty;
            a[tx][ty] = 1;
        }
        cout<<bfs(0)<<" "<<bfs(1)<<"\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

6、黄金律法

• 给出两个长度相同的序列，分别重新排序后，令每个对应位置上的数两两相乘加起来的值最小，求结果，ai<1e5。
• 贪心，排序不等式结论，一个从大到小一个从小到大即可，注意不开ll只有10分

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e7+10;
LL a[maxn], b[maxn];
bool cmp(LL x, LL y){
    return x>y;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        for(int i = 1; i <= n; i++)cin>>a[i];
        for(int i = 1; i <= n; i++)cin>>b[i];
        sort(a+1,a+n+1);
        sort(b+1,b+n+1,cmp);
        LL sum = 0;
        for(int i = 1; i <= n; i++){
            sum += a[i]*b[i];
        }
        cout<<sum<<"\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

7、天气预报

• 将01串存为数组，即判断一个区间的区间和>=b，且长度>=a+b时满足条件，求区间个数。
• 想到了前缀和O1求区间和，但是不知道为啥前缀和写错了（bushi），然后按照双指针每次枚举终点，k从前往后直到刚好不能满足条件为止（尺取法），那么以i为终点的区间个数就是k-1个，即包含区间[k,i]并向前面可以拓展k-1个。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+10;
LL c[maxn], s[maxn], sb[maxn];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;  cin>>n;
    LL a, b;  cin>>a>>b;
    string str;  cin>>str; 
    LL ans = 0, k = 1;
    for(int i = 1; i <= n; i++){
        // c[i] = str[i-1]-'0'; //93%WA
        // s[i] = s[i-1]+c[i]; //在家
        // sb[i] = i-s[i];     //出门
        if(str[i-1]=='0')s[i]=s[i-1], sb[i]=sb[i-1]+1;
        else s[i]=s[i-1]+1, sb[i]=sb[i-1];
        while(sb[i]-sb[k-1]>=a && s[i]-s[k-1]>=b && k<=i)k++;
        ans += k-1;
    }
    if(a==0 && b==0)ans++;
    cout<<ans<<"\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

8、叠硬币

• n堆硬币，选择最少的数量叠起来刚好等于高度H，多种方案选字典序小的输出。
• dfs暴力所有选择方案+剪枝剪掉大于H高度的子树，33分
• 首先不难想到要堆数量尽可能小，那么先从大到小排个序。
• 然后考虑每堆硬币选还是不选，最后高度为h，就是类似于01背包问题变种+打印方案。
  记f[i]表示拼成高度为i的硬币堆需要的最小长度，转移时尝试使用当前a[i]为所有h到a[i]的最小高度更新，取max（f[j-a[i]]+1，f[i]），初始值都为正无穷,f[0]=0。
• 记p[j]=i表示高度为j时使用的点为i，循环打印即可

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 3030;
int a[maxn], f[maxn], p[maxn];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n, h;  cin>>n>>h;
    for(int i = 1; i <= n; i++)cin>>a[i];
    sort(a+1,a+n+1,[](int x, int y){return x>y;});
    memset(f,0x3f,sizeof(f));
    f[0] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = h; j >= a[i]; j--){
            if(f[j-a[i]]==f[h+1])continue;
            if(f[j]>=f[j-a[i]]+1){//等于的时候也要更新，因为字典序最小，后面的更优
                f[j] = f[j-a[i]]+1;
                p[j] = i;
            }
        }
    }
    if(f[h]==f[h+1])return cout<<"-1\n", 0;
    cout<<f[h]<<"\n";
    while(h){
        cout<<a[p[h]]<<" ";
        h -= a[p[h]];
    }
    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

9、A+B Problem again

• 第一题的做法是直接每个数加上除了自己以外的最大值，最大值可以扫一遍O（n）获得且最大值是固定的不会变的，但是本题因为改变了两数比较的规则，所以对于每个数，最大值需要加的数可能会不一样，所以只能每次O（n）扫一遍去按照题目规则做加法，NM复杂度+手写字符串高精的常数只能拿到20分。
• 考虑新的规则本身，注意到题目每个数字的大小都不超过6位，可以把每个数都拆出来逐位的考虑，即越靠前的位，两位相加就越大。所以能过的做法是把每个数都当做6位的字符串建一颗字典树（类似于暑假集训遇到的异或最大和的做法去比较）。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;

int a[maxn][9];
int tree[maxn*6][10], cnt;
vector<int>vc[maxn*6];
void insert(int x){
    int p = 0; //根
    for(int i = 6; i > 0; i--){ //靠前的位加到上层
        if(!tree[p][a[x][i]])tree[p][a[x][i]]=++cnt;
        p = tree[p][a[x][i]];
    }
    vc[p].push_back(x);//叶子节点存这里保存下标
}
int query(int p, int j, int i){
    // cout<<"as: "<<p<<"\n";
    if(j==0){
        // cout<<p<<"\n";
        for(int x:vc[p]){
            if(x!=i)return x;//不能跟自己相加 
        }
        return 0;
    }
    int st = 9-a[i][j];//最好是能凑到9
    for(int k = 1; k <= 10; k++){
        if(tree[p][st]){
            int ans = query(tree[p][st],j-1,i);//去凑第i个数的下一位
            if(ans)return ans; 
        }
        st--; //凑不到就凑的小一点
        if(st<0)st = 9;
    }
    return 0;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;  cin>>n;
    for(int i = 1; i <= n; i++){
        int x;  cin>>x;
        for(int j = 1; j <= 6; j++)a[i][j]=x%10, x/=10;//654321的顺序存进去
        insert(i);
    }
    for(int i = 1; i <= n; i++){
        int x = query(0,6,i), ans = 0;
        for(int j = 6; j >= 1; j--)
            ans = ans*10+(a[i][j]+a[x][j])%10;
        cout<<ans<<" ";
    }
    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

10、史东薇尔城

• 给出n个点m条边的无向图，求点s->1->t的最短路
• Dijkstra板子跑出1到所有点的最短路，每次输出就行

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
#define debug(a) cout<<"debug:"<<#a<<"\n"
using namespace std;
typedef long long LL;
typedef pair<LL,LL>P;///first距离，second编号
const LL mod=1e9+7;
const LL maxn=1e5+1000;
struct Edge{
    LL to,val;
};
vector<Edge>g1[maxn];
vector<Edge>g4[maxn];
multiset<LL>s1;
LL dis1c[maxn],disnd[maxn];
LL a[maxn];
LL n,m,q;
bool vis[maxn];
void dijkstra(LL st, vector<Edge>g[], LL dis[]){
     memset(vis,0,sizeof(vis));
     for(LL i=0;i<n+10;i++) dis[i]=1e18;
     priority_queue< P,vector<P>, greater<P> >que;
     dis[st]=0;
     que.push({dis[st],st});
     while(!que.empty()){
        P now=que.top();que.pop();
        LL u=now.second;
        if(vis[u]) continue;
        vis[u]=1;
        for(LL i=0;i<g[u].size();i++){
            LL v=g[u][i].to;
            LL cost=g[u][i].val;
            if(dis[v]>dis[u]+cost){
                dis[v]=dis[u]+cost;
                que.push({dis[v],v});
            }
        }
     }
}
int main(void){
   cin.tie(0);std::ios::sync_with_stdio(false);
   cin>>n>>m;
   for(LL i=1;i<=m;i++){
       LL u,v,c;cin>>u>>v>>c;
       g1[u].push_back({v,c});
       g1[v].push_back({u,c});
   }
 
   dijkstra(1,g1,dis1c);
        int T;  cin>>T;
        while(T--){
            int s, t;  cin>>s>>t;
            cout<<dis1c[s]+dis1c[t]<<"\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

11、取模

• 数论分块板子题（buhui），51nod 1168 余数之和 原题简单版（cpp）
• 注意取模没有取好只有60分。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
LL pows(LL a, LL x, LL p){if(x==0)return 1; LL t = pows(a, x>>1,p);if(x%2==0)return t*t%p;return t*t%p*a%p;}
int main(){
    LL n;  cin>>n;
    LL xx=pows(2LL,mod-2,mod);
    LL ans=(n%mod)*(n%mod)%mod;
    LL ret=sqrt(n);
    LL tmp=n/(ret+1);
    for(int i=1;i<=tmp;i++){
        ans=(ans-n/i*i)%mod;
    }
    for(int i=n/(tmp+1);i>0;i--){
        LL a=n/i;        a %= mod;
        LL b=n/(i+1)+1;  b %= mod;
        LL cnt=(((LL)i*((a+b))%mod)%mod*(a-b+1)%mod+mod)*xx%mod;
        ans=(ans-cnt+mod)%mod;
    }
    cout<<(ans%mod+mod)%mod<<endl;
    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

12、剪绳子

• 每次减绳子的值用set维护一下让其有序，对于查询的长度，二分找到刚好比他大的和比他小的，两个减一下就是答案，边界0和10
• 其实set维护以后暴力一下也可以过（）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int q;  cin>>q;
    set<float>se;
    se.insert(0);
    se.insert(10);
    while(q--){
        string op; float x;  cin>>op>>x;
        if(op=="C"){
            se.insert(x);
        }else{
            auto p1=lower_bound(se.begin(),se.end(),x); 
            auto p2=upper_bound(se.begin(),se.end(),x);
            if(p2==se.end())printf("%.5f\n",10-(*--p1));
            else printf("%.5f\n",(*p2)-(*--p1));
        }
    }
    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

13、数硬币

• 给出长为n的序列，支持区间加值，区间和查询，区间gcd。n<1e5,q<1e5。
• 线段树板子题。 可以参考Acwings246. 区间最大公约数
• 讲个笑话，线段树调了两个小时拿了10分，发现循环一遍打暴力可以过。。。。

//暴力AC
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
int a[maxn];
int main(){
    int n, m;  cin>>n>>m;
    for(int i =1; i <= n; i++)cin>>a[i];
    while(m--){
        int op, l, r;  cin>>op>>l>>r;
        if(l>r)swap(l,r);
        if(op==0){
            int d;  cin>>d;
            for(int i = l; i <= r; i++)a[i]+=d;
        }else if(op==1){
            LL ans = 0;
            for(int i = l; i <= r; i++)ans+=a[i];
            cout<<ans<<"\n";
        }else{
            int ans = a[l];
            for(int i = l+1; i <= r; i++)ans = gcd(ans, a[i]);
            cout<<ans<<"\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

//10分代码，区间加的修改写错了，不知道错哪
//题面：线段树，支持区间+d，区间求gcd
//思路：gcd(a,b)=gcd(a,b−a)，所以(a,b,c)=(a,b−a,c−b)，即在知道a的情况下可以通过维护差分序列(b-a,c-b)的gcd来获得三个数的gcd，而差分数列可以变区间修改为单点修改
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;

LL a[maxn], b[maxn];

#define lch p<<1
#define rch p<<1|1
struct node{
    int l, r; LL v, d, s;
}sgt[maxn<<2];
LL tag[maxn<<2];
void pushup(node &p, node &l, node &r){
    p.v = l.v+r.v;
    p.d = __gcd(l.d,r.d);
    p.s = l.s+r.s;
}
void pushup(int p){ pushup(sgt[p],sgt[lch],sgt[rch]); }
void pushdown(int p){
    if(tag[p]){
        tag[lch] += tag[p];  tag[rch]+= tag[p];
        sgt[lch].s += (sgt[lch].r-sgt[lch].l+1)*tag[p];
        sgt[rch].s += (sgt[rch].r-sgt[rch].l+1)*tag[p];
        tag[p] = 0;
    }
}
void build(int p, int l, int r){
    if(l==r)sgt[p] = {l,r,b[l],b[l],a[l]};
    else{
        sgt[p] = {l,r};
        int mid = l+r>>1;
        build(lch, l, mid);
        build(rch, mid+1, r);
        pushup(p);
    }
}
LL query_d(int p, int l, int r){
    if (l > r) return 0;//Segmentation Fault
    if(sgt[p].l>=l && sgt[p].r<=r)return sgt[p].d;
    else{
        int mid = sgt[p].l+sgt[p].r>>1;
        if(r<=mid)return query_d(lch, l, r);
        else if(l>mid)return query_d(rch,l,r);
        else return __gcd(query_d(lch,l,r),query_d(rch,l,r));
    }
}
LL query_v(int p, int l, int r){
    if (l > r) return 0;
    if(sgt[p].l>=l && sgt[p].r<=r)return sgt[p].v;
    else{
        int mid = sgt[p].l+sgt[p].r>>1;
        if(r<=mid)return query_v(lch, l, r);
        else if(l>mid)return query_v(rch,l,r);
        else return query_v(lch,l,r)+query_v(rch,l,r);
    }
}
LL query_s(int p, int l, int r){
    if (l > r) return 0;
    if(sgt[p].l>=l && sgt[p].r<=r)return sgt[p].s;
    else{
        pushdown(p);
        int mid = sgt[p].l+sgt[p].r>>1;
        LL ans = 0;
        if(l<=mid)ans += query_s(lch, l, r);
        if(r>mid)ans += query_s(rch,l,r);
        return ans;
    }
}
void modify(int p, int x, LL v){
    if(sgt[p].l==sgt[p].r && sgt[p].l==x){//找到位置
        sgt[p].d += v;  sgt[p].v+=v;
    }else{
        int mid = sgt[p].l+sgt[p].r>>1;
        if(x<=mid)modify(lch,x,v);
        else modify(rch, x, v);
        pushup(p);
    }
}
void modify_s(int p, int l, int r, LL v){
    if(l <= sgt[p].l && sgt[p].r<=r){
        tag[p] += v;
        sgt[p].s += (sgt[p].r-sgt[p].l+1)*v;
    }else{
        pushdown(p);
        int mid = sgt[p].l+sgt[p].r>>1;
        if(l<=mid)modify_s(lch,l,r,v);
        if(r>mid)modify_s(rch,l,r,v);
        pushup(p);
    }
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n, m;  cin>>n>>m;
    for(int i = 1; i <= n; i++){
        cin>>a[i];  b[i]=a[i]-a[i-1];
    }
    build(1,1,n+1);
    for(int i = 1; i <= m; i++){
        int op ;  cin>>op;
        if(op==0){
            LL l, r, d;  cin>>l>>r>>d;
            if(l>r)swap(l,r);//?
            modify_s(1,l,r,d);
            modify(1, l, d);
            //if(r+1<=n)
            modify(1,r+1,-d);
        }else if(op==2){
            LL l, r;  cin>>l>>r;
            if(l>r)swap(l,r);//?
            LL t = query_v(1,1,l);
            cout<<abs( __gcd(t, query_d(1, l+1, r)))<<"\n";
        }else if(op==1){
            LL l, r;  cin>>l>>r;
            if(l>r)swap(l,r);//?
            cout<<query_s(1,l,r)<<"\n";
            // LL sum = 0;
            // for(int i = l; i <= r; i++){
            //     sum += query_v(1,1,i);
            // }
            // cout<<sum<<"\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
128
129
130
131

//别人的一颗可以通过的线段树
#include <bits/stdc++.h>
typedef long long ll;
const int MAXN = 1e5 + 10;
ll _abs(ll x)
{
    return x < 0? -x: x;
}
struct node
{
    ll l, r, sum, gcd;
} tr[MAXN << 2];
ll tag[MAXN << 2], a[MAXN];
void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].gcd = std::__gcd(_abs(tr[u << 1].gcd), _abs(tr[u << 1 | 1].gcd));
}
void pushdown(int u)
{
    if (tag[u])
    {
        tag[u << 1] += tag[u]; tag[u << 1 | 1] += tag[u];
        tr[u << 1].sum += (tr[u << 1].r - tr[u << 1].l + 1) * tag[u];
        tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tag[u];
        tag[u] = 0;
    }
}
void build(int l, int r, int u)
{
    tr[u] = {l, r};
    if (l == r)
    {
        tr[u].sum = a[l];
        tr[u].gcd = a[l] - a[l - 1];
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, u << 1); build(mid + 1, r, u << 1 | 1);
    pushup(u);
}
void modifysum(int l, int r, int k, int u)
{
    if (l <= tr[u].l && tr[u].r <= r)
    {
        tag[u] += k;
        tr[u].sum += (tr[u].r - tr[u].l + 1) * k;
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modifysum(l, r, k, u << 1);
    if (r > mid) modifysum(l, r, k, u << 1 | 1);
    pushup(u);
}
void modifygcd(int x, int k, int u)
{
    if (tr[u].l == tr[u].r && tr[u].l == x)
    {
        tr[u].gcd += k;
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) modifygcd(x, k, u << 1);
    else modifygcd(x, k, u << 1 | 1);
    pushup(u);
}
ll querysum(int l, int r, int u)
{
    if (l <= tr[u].l && tr[u].r <= r)
        return tr[u].sum;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    ll ans = 0;
    if (l <= mid) ans += querysum(l, r, u << 1);
    if (r > mid) ans += querysum(l, r, u << 1 | 1);
    return ans;
}
ll querygcd(int l, int r, int u)
{
    if (l > r) return 0;
    if (l <= tr[u].l && tr[u].r <= r)
        return _abs(tr[u].gcd);
    int mid = tr[u].l + tr[u].r >> 1;
    ll gcd = 0;
    if (l <= mid) gcd = std::__gcd(gcd, querygcd(l, r, u << 1));
    if (r > mid) gcd = std::__gcd(gcd, querygcd(l, r, u << 1 | 1));
    return gcd;
}
int main()
{
    int n, q; scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &a[i]);
    a[n + 1] = 0;
    build(1, n + 1, 1);
    while (q--)
    {
        int opt; scanf("%d", &opt);
        if (opt == 0)
        {
            int x, y, k; scanf("%d%d%d", &x, &y, &k);
            if (x > y) std::swap(x, y);
            modifysum(x, y, k, 1);
            modifygcd(x, k, 1); modifygcd(y + 1, -k, 1);
        }
        else if (opt == 1)
        {
            int x, y; scanf("%d%d", &x, &y);
            if (x > y) std::swap(x, y);
            printf("%lld\n", querysum(x, y, 1));
        }
        else
        {
            int x, y; scanf("%d%d", &x, &y);
            if (x > y) std::swap(x, y);
            printf("%lld\n", std::__gcd(querysum(x, x, 1), querygcd(x + 1, y, 1)));
        }
    }
    // for (int i = 1; i <= n; ++i)
    //     printf("%lld ", querysum(i, i, 1));
    // printf("%lld\n", querysum(6, 9, 1));
    return 0;
}
/*
5 5
63 96 19 7 37 
0 1 3 95
1 1 3
0 2 2 85
1 5 3
2 3 2

*/
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