描述

给定一个长度为N的数列A，以及M条指令 (N≤5*10^5, M<=10^5)，每条指令可能是以下两种之一：

“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。

“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。

输入格式

第一行两个整数N,M，第二行N个整数Ai，接下来M行每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

样例输入

5 5

1 3 5 7 9

Q 1 5

C 1 5 1

Q 1 5

C 3 3 6

Q 2 4

样例输出

1

2

4

数据范围与约定

• N,M≤2*10^5，l<=r，数据保证任何时刻序列中的数都是不超过2^62-1的正整数。

        </article>

分析

根据“更相减损术”，\(gcd(x,y,z)=gcd(x,y-x,z-y)\)，所以

所以用线段树维护差分序列的gcd，在线段树上单点修改区间查询；然后是要区间修改单点查询原序列的值，用树状数组维护新差分序列即可。

时间复杂度\(O(M \log N)\)

co int N=5e5+1;

int n,m;

ll a[N],b[N],c[N];

#define lowbit(i) (i&-i)

void add(int p,ll v){

	for(;p<=n;p+=lowbit(p)) c[p]+=v;

}

ll ask(int p){

	ll re=0;

	for(;p;p-=lowbit(p)) re+=c[p];

	return re;

}

ll s[N*4];

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

#define lc (x<<1)

#define rc (x<<1|1)

void build(int x,int l,int r){

	if(l==r) return s[x]=b[l],void();

	int mid=l+r>>1;

	build(lc,l,mid),build(rc,mid+1,r);

	s[x]=gcd(s[lc],s[rc]);

}

void change(int x,int l,int r,int p){

	if(l==r) return s[x]=b[l],void();

	int mid=l+r>>1;

	if(p<=mid) change(lc,l,mid,p);

	else change(rc,mid+1,r,p);

	s[x]=gcd(s[lc],s[rc]);

}

ll query(int x,int l,int r,int ql,int qr){

	if(ql>qr) return 0;

	if(ql<=l&&r<=qr) return s[x];

	int mid=l+r>>1;

	if(qr<=mid) return query(lc,l,mid,ql,qr);

	if(ql>mid) return query(rc,mid+1,r,ql,qr);

	return gcd(query(lc,l,mid,ql,qr),query(rc,mid+1,r,ql,qr));

}

int main(){

//	freopen("CH4302.in","r",stdin),freopen("CH4302.out","w",stdout);

	read(n),read(m);

	for(int i=1;i<=n;++i) b[i]=read(a[i])-a[i-1];

	build(1,1,n); // edit 1: reserve for changing b[1]

	for(int l,r;m--;){

		static char op[2];

		scanf("%s",op),read(l),read(r);

		if(op[0]=='C'){

			ll d=read<ll>(); // edit 2

			b[l]+=d,change(1,1,n,l),add(l,d);

			if(r+1<=n) b[r+1]-=d,change(1,1,n,r+1),add(r+1,-d);

		}

		else printf("%lld\n",llabs(gcd(a[l]+ask(l),query(1,1,n,l+1,r))));

	}

	return 0;

}

LG1438 无聊的数列

区间加等差数列和单点询问。

可以维护差分数组。也可以维护0次方和1次方和。

CO int N=1e5+10;

int sum[4*N],tag[4*N][2];

#define lc (x<<1)

#define rc (x<<1|1)

void push_up(int x){

    sum[x]=sum[lc]+sum[rc];

}

void push_down(int x,int l,int r){

    int mid=(l+r)>>1;

    if(tag[x][0]){

        sum[lc]+=(mid-l+1)*tag[x][0],tag[lc][0]+=tag[x][0];

        sum[rc]+=(r-mid)*tag[x][0],tag[rc][0]+=tag[x][0];

        tag[x][0]=0;

    }

    if(tag[x][1]){

        sum[lc]+=(mid*(mid+1)/2-(l-1)*l/2)*tag[x][1],tag[lc][1]+=tag[x][1];

        sum[rc]+=(r*(r+1)/2-mid*(mid+1)/2)*tag[x][1],tag[rc][1]+=tag[x][1];

        tag[x][1]=0;

    }

}

void build(int x,int l,int r){

    tag[x][0]=tag[x][1]=0;

    if(l==r) return read(sum[x]);

    int mid=(l+r)>>1;

    build(lc,l,mid),build(rc,mid+1,r);

    push_up(x);

}

void change(int x,int l,int r,int ql,int qr,int v[2]){

    if(ql<=l and r<=qr){

        sum[x]+=(r-l+1)*v[0],tag[x][0]+=v[0];

        sum[x]+=(r*(r+1)/2-(l-1)*l/2)*v[1],tag[x][1]+=v[1];

        return;

    }

    push_down(x,l,r);

    int mid=(l+r)>>1;

    if(ql<=mid) change(lc,l,mid,ql,qr,v);

    if(qr>mid) change(rc,mid+1,r,ql,qr,v);

    push_up(x);

}

int query(int x,int l,int r,int ql,int qr){

    if(ql<=l and r<=qr) return sum[x];

    push_down(x,l,r);

    int mid=(l+r)>>1;

    if(qr<=mid) return query(lc,l,mid,ql,qr);

    if(ql>mid) return query(rc,mid+1,r,ql,qr);

    return query(lc,l,mid,ql,qr)+query(rc,mid+1,r,ql,qr);

}

#undef lc

#undef rc

signed main(){

    int n=read<int>(),m=read<int>();

    build(1,1,n);

    while(m--){

        if(read<int>()==1){

            int l=read<int>(),r=read<int>();

            int a=read<int>(),d=read<int>();

            int v[2]={a-l*d,d};

            change(1,1,n,l,r,v);

        }

        else{

            int p=read<int>();

            printf("%lld\n",query(1,1,n,p,p));

        }

    }

    return 0;

}

最新文章

1. 【腾讯优测干货分享】Android内存泄漏的简单检查与分析方法
2. 1 python大数据挖掘系列之基础知识入门
3. 一个获取指定目录下一定格式的文件名称和文件修改时间并保存为文件的python脚本
4. 【USACO 1.3】Barn Repair
5. maven问题－&quot;resolution will not be reattempted until the update interval of MyRepo has elapsed&quot;
6. Mac上添加adb_usb.ini
7. 项目开发--&gt;身份认证及用户登录模块
8. Apache Virtual Include
9. 重新开始学习javase_类再生（类的合成和继承）
10. SQL Server JDBC驱动中sqljdbc和sqljdbc4区别
11. 如何灵活使用 ActionBar， Google 音乐ActionBar 隐藏和显示效果
12. spring框架内置笔记本
13. ASP.NET Core 运行原理解剖[2]:Hosting补充之配置介绍
14. Extensions in UWP Community Toolkit - Visual Extensions
15. springBoot 自动配置原理--自己新建一个 starter
16. 通过ajax返回值
17. [hdu P4334] Trouble
18. java常用技术名词解析
19. main.jsbundle 脱离掉本地服务
20. js 事件event

热门文章

1. prometheus使用postgresql-adapter连接postgresql
2. nginx location指令详解
3. Java学习：List接口
4. 安装软件时出现这样错误：文件“proe50-1a.bin”无法在“C:\User\ZFTL\Desktop\proe50”定位，请插入正确的磁盘或选择其他文件夹
5. 【C#常用方法】3.将DataTable一次性插入数据库表中（使用SqlBulkCopy）
6. 指针 vs 引用 （2）
7. 2019 贝壳找房java面试笔试题 （含面试题解析）
8. iOS - 架构的认识过程，悬崖勒马。
9. 33、vue中的事件修饰符.stop、.prevent、.self、.capture、.once
10. JavaScript 之 基本包装类型