U582051 区间加区间gcd 题解

U582051 区间加区间gcd 题解

题目大意：

给定一个长度为$n$的序列${a_1,a_2,.....a_n}$
给出$q$次操作，分为以下两种：
1 l r x:给序列中区间$[l,r]$中的所有元素加$x$
2 l r:询问区间$[l,r]$中所有元素的$gcd$（最大公约数）

区间修改、区间查询的线段树重点储存的数据有两种：信息与标记
若要完成线段树，得看看题目能否再$O(logn)$的时间复杂度完成以下操作：
1.信息与信息合并成为新信息，即$\tt pushup$操作
2.信息与标记合并成为新信息，否则无法做到修改
3.标记与标记合并成为新标记，即$\tt pushdown$操作
这道题标记是加法，信息是$gcd$
第一种操作很简单，两个信息取$gcd$即可
第二种操作也很简单，两个标记加上即可
但是，第三种操作却不可能完成，毕竟你也不大可能吧加法与$gcd$扯上关系
所以，如果直接攻击用线段树不可解
那我们就要考虑能不能用性质绕路
既然无法将信息与标记合并，那就舍弃标记
单点修改的线段树就没有标记这个东西
注意到，$gcd$满足以下性质：

$$gcd(a,b)=gcd(a,a-b)$$

扩展即可得到：

$$gcd(a_l,a_{l+1},......,a_r)=gcd(a_l,a_{l+1}-a_l,a_{l+2}-a_{l+1},......a_r-a_{r-1}) $$

用线段树维护差分数组，如此维护区间加操作：

$$d_i=a_i-a_{i-1}$$

将$[l,r]$区间加上一个$x$，可以：

$$d_l+=x,d_{r+1}-=x$$

如此维护区间$gcd$

$$gcd(a_l,a_{l+1},......,a_r)=gcd(a_l,d_{l+1},d_{l+2},......,d_r) $$

使用两个线段树，一个是区间修改单点查询维护$a$数组，另一个是单点修改区间查询维护$d$数组，将两个查询取$gcd$即可得到答案

AC code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3e5+5;
#define lson (u<<1)
#define rson (u<<1|1)
#define mid ((l+r)>>1)
int n,q;
int a[maxn],d[maxn];
struct segtree{					//差分线段树：单点修改，区间查询 
	struct treenode{
		int l,r,val;
	}tree[maxn<<2];
	void pushup(int u){
		tree[u].val=__gcd(tree[lson].val,tree[rson].val);
	}
	void build(int u,int l,int r){
		tree[u].l=l,tree[u].r=r,tree[u].val=0;
		if(l==r){
			tree[u].val=d[l];
			return;
		}
		build(lson,l,mid);
		build(rson,mid+1,r);
		pushup(u);
	}
	void update(int u,int p,int x){
		int l=tree[u].l,r=tree[u].r;
		if(l>p||r<p)return;
		if(l==r){
			tree[u].val+=x;
			return;
		}
		if(p<=mid)update(lson,p,x);
		else update(rson,p,x);
		pushup(u);
	}
	int query(int u,int L,int R){
		int l=tree[u].l,r=tree[u].r;
		if(l>R||r<L)return 0;
		if(L<=l&&r<=R)return tree[u].val;
		return __gcd(query(lson,L,R),query(rson,L,R));
	}
}t;
struct seg_tree{							//线段树：区间修改，单点查询 
	struct treenode{
		int l,r,val,lzy;
	}tree[maxn<<2];
	void pushup(int u){
		tree[u].val=tree[lson].val+tree[rson].val;
	}
	void build(int u,int l,int r){
		tree[u].l=l,tree[u].r=r,tree[u].val=tree[u].lzy=0;
		if(l==r){
			tree[u].val=a[l];
			return;
		}
		build(lson,l,mid);
		build(rson,mid+1,r);
		pushup(u);
	}
	void pushdown(int u){
		int l=tree[u].l,r=tree[u].r;
		tree[lson].lzy=tree[rson].lzy=tree[u].lzy;
		tree[lson].val+=tree[u].lzy*(mid-l+1);
		tree[rson].val+=tree[u].lzy*(r-mid);
		tree[u].lzy=0;
	}
	void update(int u,int L,int R,int x){
		int l=tree[u].l,r=tree[u].r;
		if(l>R||r<L)return;
		pushdown(u);
		if(L<=l&&r<=R){
			tree[u].lzy+=x;
			return;
		}
		update(lson,L,R,x);
		update(rson,L,R,x);
		pushup(u);
	}
	int query(int u,int p){
		int l=tree[u].l,r=tree[u].r;
		if(l>p||r<p)return 0;
		pushdown(u);
		if(l==r){
			return tree[u].val;
		}
		return query(lson,p)+query(rson,p);
	}
}s;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		d[i]=a[i]-a[i-1];
	}
	t.build(1,1,n);
	s.build(1,1,n);
	while(q--){
		int op;
		cin>>op;
		if(op==1){
			int l,r,x;
			cin>>l>>r>>x;
			t.update(1,l,x);
			t.update(1,r+1,-x);
			s.update(1,l,r,x);
		}else{
			int l,r;
			cin>>l>>r;
			cout<<abs(__gcd(s.query(1,l),t.query(1,l+1,r)))<<endl;
		}
	}
	return 0;
}

U583518 单点赋值区间询问有重 题解

U583518 单点赋值区间询问有重 题解

题目大意：

给出$q$次操作，分为以下两种：
1 p x:给序列编号为$p \oplus cnt$的元素赋值为$x$
2 l r:询问区间$[l\oplus cnt,r\oplus cnt]$中是否存在重复元素
$cnt$表示在此之前输出"Yes"的数量

对于这种区间查询问题，优先考虑的数据结构是线段树。
如何维护这种是否存在重复元素的问题呢？
由于是单点修改，不需要标记，所以我们只需要考虑信息与信息合并的问题。
两个区间，已知两个区间是否又重复数，请问合并区间是否有重复数？
如果其中一个有重复数，那么答案很明显，合并区间也有重复数。
但是，如果两个区间都没有重复数呢？
很明显，如果需要得到这个问题的答案，需要遍历两个区间去查看是否有重复数字，不可能在$O(logn)$以内的复杂度做到。
那么，我们就另辟蹊径。

$$——————上面都是废话——————$$

对于一个下标，维护这个下标的前驱后继。
这里的前驱指在这个下标之前第一个与这个下标所对应的数相等的数所对应的下标，用$anc_i$表示。如果没有，则$anc_i$设为$0$
后继则指的是在这个下标之后第一个与这个下标所对应的数相等的数所对应的下标，用$suc_i$表示。如果没有，则$suc_i$设为$n+1$
如果一个数下标为$i$在$[l,r]$区间内有重复数字，满足$anc_i \ge l$或者$suc_i \le r$
不难证明，对于一个区间$[l,r]$，维护其内部所有元素的前驱的最大值，如果这个最大值$\lt l$，那么这个区间不存在重复数字。
那么接下来的问题是：如何用$O(logn)$的时间复杂度动态维护前驱后继？
对于每一个值$val$，记录这个值出现的每一个位置。
如果将下标$x$的数改成$y$，那么首先要修改的就是其前驱的后继与其后继的前驱。（类似链表）

$$anc_{suc_i}=anc_i,suc_{anc_i}=suc{i}$$

然后用二分查找找到值为$y$的下标中最后一个$\lt i$的数和第一个$\gt i$的数，分别就是$i$的新前驱后继。
然后再分别修改新前驱的新后继和新后继的新前驱即可。

AC code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3e5+5;
#define lson (u<<1)
#define rson (u<<1|1)
#define mid ((l+r)>>1)
int n,q;
int a[maxn],anc[maxn],suc[maxn];
unordered_map<int,set<int>> mp;
void remove(int x){
	auto &s=mp[a[x]];
	auto it=s.find(x);
	if(it==s.end())return;
	if(it!=s.begin()){
		auto pre=prev(it);
		suc[*pre]=suc[x];
	}
	if(next(it)!=s.end()){
		auto nex=next(it);
		anc[*nex]=anc[x];
	}
	s.erase(it);
	if(s.empty())mp.erase(a[x]);
}
void insert(int x,int y){
	a[x]=y;
	auto &s=mp[y];
	auto it=s.lower_bound(x);
	if(it!=s.end()){
		suc[x]=*it;
		anc[*it]=x;
	}else{
		suc[x]=n+1;
	}
	if(it!=s.begin()){
		auto pre=prev(it);
		anc[x]=*pre;
		suc[*pre]=x;
	}else{
		anc[x]=0;
	}
	s.insert(x);
}
void change(int x,int y){
	if(a[x]==y)return;
	remove(x);
	insert(x,y);
}
struct segtree{
	struct treenode{
		int l,r,mxanc;
	}tree[maxn<<2];
	void pushup(int u){
		tree[u].mxanc=max(tree[lson].mxanc,tree[rson].mxanc);
	}
	void build(int u,int l,int r){
		tree[u].l=l,tree[u].r=r;
		tree[u].mxanc=0;
		if(l==r){
			tree[u].mxanc=anc[l];
			return;
		}
		build(lson,l,mid);
		build(rson,mid+1,r);
		pushup(u);
	}
	void update(int u,int p,int x){
		int l=tree[u].l,r=tree[u].r;
		if(l>p||r<p)return;
		if(l==r){
			change(p,x);
			tree[u].mxanc=anc[p];
			return;
		}
		if(p<=mid)update(lson,p,x);
		else update(rson,p,x);
		pushup(u);
	}
	int query(int u,int L,int R){
		int l=tree[u].l,r=tree[u].r;
		if(r<L||l>R)return 0;
		if(L<=l&&r<=R){
			return tree[u].mxanc;
		}
		return max(query(lson,L,R),query(rson,L,R));
	}
}t;
signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)suc[i]=n+1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		insert(i,a[i]);
	}
	t.build(1,1,n);
	int cnt=0;
	while(q--){
		int op;
		cin>>op;
		if(op==1){
			int p,x;
			cin>>p>>x;
			p^=cnt;
			int oldsuc=suc[p];
			t.update(1,p,x);
			int newsuc=suc[p];
			t.update(1,oldsuc,a[oldsuc]);
			t.update(1,newsuc,a[newsuc]);
		}else{
			int l,r;
			cin>>l>>r;
			int mxanc=t.query(1,l^cnt,r^cnt);
			if(mxanc>=l){
				cout<<"Yes"<<endl;
				cnt++;
			}else{
				cout<<"No"<<endl;
			}
		}
	}
	return 0;
}

U584560 区间加区间乘积和 题解

U584560 区间加区间乘积和 题解

题目大意：

给出$q$次操作，分为以下两种：
1 l r x:给序列中区间$[l,r]$中的所有元素加$x$
2 l r:求出$\sum\limits_{l\le i \lt j \le r} a_i \times a_j$
答案对$10^9+7$取模

区间修改、区间查询的线段树重点储存的数据有两种：信息与标记
若要完成线段树，得看看题目能否再$O(logn)$的时间复杂度完成以下操作：
1.信息与信息合并成为新信息，即$\tt pushup$操作
2.信息与标记合并成为新信息，否则无法做到修改
3.标记与标记合并成为新标记，即$\tt pushdown$操作
最简单的就是操作3，因为标记是加法，直接加上即可
操作1和操作2就比较麻烦
因为这种带乘积的加和极难做到合并
但是，注意到：

$$\sum\limits_{l\le i \lt j \le r} a_i \times a_j=\cfrac{(\sum\limits_{i=l}^r a_i)^2-(\sum\limits_{i=l}^r a_i^2)}{2} $$

于是，我们有了思路：线段树储存和与平方和
这下，操作1就变得十分简单，直接将两个区间的和与平方和分别相加即可
但是操作2如何实现呢？
注意到：

$$(a+x)^2=a^2+2ax+x^2$$

于是便能得到：

$$\sum\limits_{i=l}^r (a_i+x)^2=\sum\limits a_i^2 + 2x \sum\limits_{i=l}^r a_i + x^2(r-l+1) $$

于是，平方和的更新操作就可以通过和的储存来完成
最后，注意一下除以2的时候的模乘法逆元即可

AC code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3e5+5;
const int mod=1e9+7;
#define lson (u<<1)
#define rson (u<<1|1)
#define mid ((l+r)>>1)
int n,q;
int a[maxn];
struct segtree{
	struct treenode{
		int l,r,sum,sqsum,lzy;
	}tree[maxn<<2];
	void pushup(int u){
		tree[u].sum=(tree[lson].sum+tree[rson].sum)%mod;
		tree[u].sqsum=(tree[lson].sqsum+tree[rson].sqsum)%mod;
	}
	void build(int u,int l,int r){
		tree[u].l=l,tree[u].r=r;
		tree[u].lzy=0;
		if(l==r){
			tree[u].sum=a[l]%mod;
			tree[u].sqsum=(a[l]%mod)*(a[l]%mod)%mod;
			return;
		}
		build(lson,l,mid);
		build(rson,mid+1,r);
		pushup(u);
	}
	void pushdown(int u){
		if(tree[u].lzy==0)return;
		int l=tree[u].l,r=tree[u].r;
		int lzy=tree[u].lzy;
		tree[lson].sqsum=(tree[lson].sqsum+2*lzy%mod*tree[lson].sum%mod+lzy%mod*lzy%mod*(mid-l+1)%mod)%mod;
		tree[rson].sqsum=(tree[rson].sqsum+2*lzy%mod*tree[rson].sum%mod+lzy%mod*lzy%mod*(r-mid)%mod)%mod;
		tree[lson].sum=(tree[lson].sum+lzy*(mid-l+1)%mod)%mod;
		tree[rson].sum=(tree[rson].sum+lzy*(r-mid)%mod)%mod;
		tree[lson].lzy=(tree[lson].lzy+lzy)%mod;
		tree[rson].lzy=(tree[rson].lzy+lzy)%mod;
		tree[u].lzy=0;
	}
	void update(int u,int L,int R,int x){
		int l=tree[u].l,r=tree[u].r;
		if(l>R||r<L)return;
		if(L<=l&&r<=R){
			tree[u].sqsum=(tree[u].sqsum+2*x%mod*tree[u].sum%mod+x%mod*x%mod*(r-l+1)%mod)%mod;
			tree[u].sum=(tree[u].sum+x*(r-l+1)%mod)%mod;
			tree[u].lzy=(tree[u].lzy+x)%mod;
			return;
		}
		pushdown(u);
		update(lson,L,R,x);
		update(rson,L,R,x);
		pushup(u);
	}
	int querysum(int u,int L,int R){
		int l=tree[u].l,r=tree[u].r;
		if(l>R||r<L)return 0;
		if(L<=l&&r<=R)return tree[u].sum%mod;
		pushdown(u);
		return (querysum(lson,L,R)+querysum(rson,L,R))%mod;
	}
	int querysqsum(int u,int L,int R){
		int l=tree[u].l,r=tree[u].r;
		if(l>R||r<L)return 0;
		if(L<=l&&r<=R)return tree[u].sqsum%mod;
		pushdown(u);
		return (querysqsum(lson,L,R)+querysqsum(rson,L,R))%mod;
	}
}t;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	t.build(1,1,n);
	while(q--){
		int op;
		cin>>op;
		if(op==1){
			int l,r,x;
			cin>>l>>r>>x;
			t.update(1,l,r,x);
		}else{
			int l,r;
			cin>>l>>r;
			int sum=t.querysum(1,l,r);
			int sqsum=t.querysqsum(1,l,r);
			int ans=(sum*sum%mod-sqsum%mod+mod)%mod*500000004%mod;
			cout<<ans<<'\n';
		}
	}
	return 0;
}