P8421 [THUPC2022 决赛] rsraogps

有点套路的数据结构。

观察到询问的形式，很容易想到离线然后扫描线计算 $l\le i$ 的答案 $s_i$，答案为 $s_r-s_{l-1}$。

注意到关键性质，设 $a_l’=\odot_{i=l}^r a_i$，那么对于每个 $a_l’$，在整个扫描线的过程中只会被修改 $\log V$ 次。$b_l’,c_l’$ 同理。所以对于这一部分直接暴力修改即可。具体的，我们维护对于 $s_i=sum+val\times t$，$sum$ 为上一次修改的前缀和，$val$ 为当前值，$t$ 为时间戳，这样就很好维护了。时间复杂度 $\mathcal O(n\log n+m)$。

Code

#include<iostream>
#include<cstdio>
#include<vector>
#define fi first
#define se second
using namespace std;
using uint=unsigned int;
using PII=pair<uint,uint>;
const int N=1e6+10,M=5e6+10;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m;
uint a[N],b[N],c[N];
uint sum[N],val[N],t[N],ans[M];
vector<PII>q[N];
uint gcd(uint x,uint y){return x?gcd(y%x,x):y;}
uint get(int x,int y){return sum[x]+val[x]*(y-t[x]+1);}
int main()
{
    read(n,m);
    for(int i=1;i<=n;i++)read(a[i]);
    for(int i=1;i<=n;i++)read(b[i]);
    for(int i=1;i<=n;i++)read(c[i]);
    for(int i=1,l,r;i<=m;i++)read(l,r),q[r].push_back({l,i});
    for(int i=1;i<=n;i++)
    {
        int j=i-1;
        while(j)
        {
            uint na=a[j]&a[j+1],nb=b[j]|b[j+1],nc=gcd(c[j],c[j+1]);
            if(na==a[j]&&nb==b[j]&&nc==c[j])break;
            a[j]=na,b[j]=nb,c[j]=nc;
            j--;
        }
        sum[i]=get(i-1,i-1);
        do
        {
            j++;
            sum[j]=get(j,i-1);
            val[j]=val[j-1]+a[j]*b[j]*c[j];
            t[j]=i;
        }while(j<i);
        for(auto x:q[i])ans[x.se]=get(i,i)-get(x.fi-1,i);
    }
    for(int i=1;i<=m;i++)printf("%u\n",ans[i]);
    return 0;
}