[THUPC2022 决赛] rsraogps
题目描述
给序列 \(a_1,\dots,a_n\)，\(b_1,\dots,b_n\)，\(c_1,\dots,c_n\)，
定义区间 \([l,r]\) 的价值为 \(a_l,\dots,a_r\) 按位与，\(b_l,\dots,b_r\) 按位或，\(c_l,\dots,c_r\) 的最大公因数，这三者的乘积；
\(m\) 次查询，每次查询给出区间 \([l,r]\)，查询满足 \(l\le l'\le r'\le r\) 的 \([l',r']\) 的价值之和。
提示
\(1\le n\le 10^6\)
\(1\le m\le 5\times 10^6\)
\(1\le a_i,b_i,c_i\le n\)
\(1\le l\le r\le n\)
建议使用高效的输入输出方式。
考虑扫描线，当 \(r\) 固定后，维护 \(w_l=[l,r]\) 的价值。
发现对于一个 \(w_i\)，他最多会改变 \(\log n\) 次，因为或，与，gcd 都是至多变动 \(\log n\) 次的。
而且 \(w_i\) 会改变的一定是一段后缀，而扫描线下来后，我们要求 \(w\) 的历史版本和 的区间和。
像吉司机线段树一样维护一个 \(t_i\) 表示 \(w_i\) 上一次改变时间是什么时候，以及这一个版本前的历史版本和 的前缀和。
由于改变的是后缀，我们可以直接修改前缀和，询问时用前缀和回答。
维护除了之前版本的历史版本和，还要维护当前版本的历史版本和，也就是 \(\sum_{j=l}^r(i-t_j+1)w_j\)，维护 \(t_jw_j\) 的前缀和和 \(w_j\) 的前缀和即可。
#include<bits/stdc++.h>
using namespace std;
#define int unsigned
const int N=1e6+5;
vector<int>qr[N];
int l[N*5],ans[N*5],a[N],b[N],c[N],d[N],f[N],g[N],h[N],n,m,t[N];
int gcd(int x,int y)
{
if(!y)
return x;
return gcd(y,x%y);
}
int read()
{
int s=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s;
}
signed main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=n;i++)
b[i]=read();
for(int i=1;i<=n;i++)
c[i]=read(),t[i]=1;
for(int i=1;i<=m;i++)
l[i]=read(),qr[read()].push_back(i);
for(int i=1;i<=n;i++)
{
int ls=0;
for(int j=i-1;j;j--)
{
if((a[j]&a[i])==a[j]&&(b[j]|b[i])==b[j]&&c[i]%c[j]==0)
ls=j,j=1;
}
for(int j=ls+1;j<=i;j++)
{
if(j^i)
{
f[j]+=(i-t[j])*a[j]*b[j]*c[j];
a[j]&=a[i];
b[j]|=b[i];
c[j]=gcd(c[j],c[i]);
}
g[j]=g[j-1]+f[j];
h[j]=h[j-1]+a[j]*b[j]*c[j];
d[j]=d[j-1]+(t[j]=i)*a[j]*b[j]*c[j];
}
for(int j=0;j<qr[i].size();j++)
{
int l=::l[qr[i][j]];
ans[qr[i][j]]=g[i]-g[l-1]+(i+1)*(h[i]-h[l-1])-d[i]+d[l-1];
}
}
for(int i=1;i<=m;i++)
printf("%u\n",ans[i]);
}