P8421 [THUPC2022 决赛] rsraogps

gxy001 · 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;
}