洛谷P8421 [THUPC 2022 决赛] rsraogps

洛谷P8421 [THUPC 2022 决赛] rsraogps

P8421 [THUPC 2022 决赛] rsraogps - 洛谷

因为从一个点最多会变化 \(\log V\) 次（这三种操作都是这样），考虑扫描线，这样每次更新前面答案贡献时，就有可能做到 \(\log V\) 的时复。

我们将答案拆成前缀和的形式：考虑扫描线到了 \(j\)，\(s_i\) 表示满足 \(l\le i,l \le r \le j\)，这样，答案被拆成了 \(s_j - s_{l-1}\)（扫描线 \(j=r\)）。

考虑扫描线 \(r \to r+1\)，改变了什么。

定义 \(A_{l,r},B_{l,r},C_{l,r}\) 表示区间的与、或、最大公约数。

\(s_i\) 会增加 \(\sum_{j=1}^i [j,r+1]\) 的区间贡献，我们注意到对于一段区间 \([j,r] \to [j,r+1]\) 如果其 \(A,B,C\) 的值均不变，那么对于 \([j,r-1],[j,r],[j,r+1]\) 之间增加的值是相同的，即 \(A\times B \times C\)。

如果其 \(A,B,C\) 任意一个改变了，那么从 \(r\) 向左直到 \(A,B,C\) 均不再改变，先增加之前的 \(s_i\)，然后打上新的增加值 \(add_i\)。

最后，对于 \(\sum_{j=1}^i [j,r+1]\) 的值，即 \(add_i\)，为 \(a,b,c\) 的一段前缀和。

\(\Large \mathscr{Code}\)

#include<bits/stdc++.h>
#define int unsigned
using namespace std;
const int N = 1e6+100;
int n,m,a[N],b[N],c[N],val[N],add[N],nt[N],T,ans[N*5];
vector<pair<int,int>> scan[N];
int query(int x){return val[x] + add[x]*(T-nt[x]);
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);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;i<=m;i++){int l,r;cin>>l>>r;scan[r].push_back({l,i});}for(int i=1;i<=n;i++){int tmp = i-1;while(tmp){int x = a[tmp]&a[tmp+1],y = b[tmp]|b[tmp+1],z = __gcd(c[tmp],c[tmp+1]);if(x==a[tmp] && y==b[tmp] && z==c[tmp]) break;a[tmp] = x,b[tmp] = y,c[tmp] = z;tmp--;}val[i] = query(i-1);for(int j=tmp+1;j<=i;j++){val[j] = query(j);nt[j] = T;add[j] = add[j-1]+a[j]*b[j]*c[j];}T++;for(auto e:scan[i]) ans[e.second] = query(i)-query(e.first-1);}for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';return 0;
}