自动搬运

查看原文

来自洛谷，原作者为

	gxy001 ......

搬运于2025-08-24 22:38:54，当前版本为作者最后更新于2022-08-05 17:02:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先考虑离线扫描线，扫描 $r$，然后对每个 $i$ 维护 $l\le i$ 的答案之和 $s_i$，这样答案就可以写为 $s_r-s_{l-1}$。

我们设 $A_i=a_i\operatorname{bitand} \cdots\operatorname{bitand} a_r$，$B_i=b_i\operatorname{bitor} \cdots\operatorname{bitor} b_r$，$C_i=\gcd(c_i,\cdots,c_r)$。

然后考虑 $r$ 向右移 $1$，这个时候 $s_i$ 的变化量，如果 $A_i,B_i,C_i$ 都没有发生变化，那么 $s_i$ 的变化量也和上次右移的时候一致，所以我们可以把每个 $s_i$ 写成 $p_ir+q_i$ 的形式，那么需要修改 $p_i,q_i$ 的 $i$ 就只有 $A_i,B_i,C_i$ 发生变化的部分，由于 $A_i,B_i,C_i$ 都只会发生 $O(\log v)$ 次修改（$v$ 是值域），所以总变化次数只有 $O(n\log v)$ 次，暴力修改即可。

查询是 $O(1)$ 的，所以总时间复杂度 $O(n\log v+m)$。

#include<iostream>
#include<vector>
#include<utility>
using std::cin;
using std::cout;
#define int unsigned
int n,m,a[1000010],b[1000010],c[1000010];
int gcd(int x,int y){
	return x?gcd(y%x,x):y;
}
std::vector<std::pair<int,int>> vec[1000010];
int ans[5000010];
int T;
int val[1000010],ad[1000010],nt[1000010];
int query(int p){
	return val[p]+ad[p]*(T-nt[p]);
}
signed main(){
	std::ios::sync_with_stdio(false),cin.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	for(int i=1;i<=n;i++) cin>>c[i];
	for(int i=1,l,r;i<=m;i++) cin>>l>>r,vec[r].emplace_back(l,i);
	for(int i=1;i<=n;i++){
		int p=i-1;
		while(p!=0){
			int u=a[p]&a[p+1];
			int v=b[p]|b[p+1];
			int w=gcd(c[p],c[p+1]);
			if(u==a[p]&&v==b[p]&&w==c[p]) break;
			a[p]=u,b[p]=v,c[p]=w;
			--p;
		}
		val[i]=query(i-1);
		for(int j=p+1;j<=i;j++){
			val[j]=query(j);
			ad[j]=ad[j-1]+a[j]*b[j]*c[j];
			nt[j]=T;
		}
		++T;
		for(auto [l,id]:vec[i]) ans[id]=query(i)-query(l-1);
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
	return 0;
}