序
题号 标题 已通过代码 通过率 我的状态
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
//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;
}
//别人的一颗可以通过的线段树
#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
*/