正題

題目鏈接:https://www.luogu.com.cn/problem/CF878E

---

題目大意

$n$個(gè)數(shù)字，每次可以把兩個(gè)相鄰的數(shù)字$x,y$變?yōu)?span id="ze8trgl8bvbq" class="katex--inline">$x+2y$。

$m$次詢(xún)問(wèn)一個(gè)區(qū)間合成一個(gè)數(shù)字后最大是多少。

---

解題思路

答案可以把每個(gè)數(shù)字變成$x_i^{c_i}$，其中$c_i\le c_{i?1}+1$。

我們可以把數(shù)字變成一個(gè)個(gè)聯(lián)通的塊，對(duì)于同一個(gè)塊中的，有$c_i=c_{i?1}+1$，考慮合并兩個(gè)塊的貢獻(xiàn)，如果前面的塊為正，那么這兩個(gè)塊一定合并更優(yōu)。

所以我們離線詢(xún)問(wèn)，枚舉右端點(diǎn)，加入一個(gè)數(shù)字后我們一直合并并且統(tǒng)計(jì)塊答案的前綴和，然后注意左端點(diǎn)的位置不能取整一個(gè)塊。

時(shí)間復(fù)雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define ll long long using namespace std; const ll N=1e5+10,inf=2e9+5,P=1e9+7; ll n,m,a[N],b[N],pw[N],f[N],ans[N]; ll fa[N],siz[N],s[N],sum[N]; vector<pair<ll,ll> > q[N]; ll find(ll x) {return (fa[x]==x)?x:(fa[x]=find(fa[x]));} void merge(ll x,ll y){fa[y]=x;if(siz[x]>30&&s[x]>0||s[x]+(s[y]<<siz[x])>=inf)s[x]=inf;else s[x]+=s[y]<<siz[x];f[x]=(f[x]+f[y]*pw[siz[x]])%P;siz[x]+=siz[y];return; } ll seek(ll l,ll r) {return (b[l]-b[r+1]*pw[r-l+1]%P+P)%P; } int main() {scanf("%lld%lld",&n,&m);pw[0]=1;for(ll i=1;i<=n;i++){scanf("%lld",&a[i]);f[i]=s[i]=a[i];fa[i]=i;siz[i]=1;pw[i]=(pw[i-1]<<1)%P; }for(ll i=n;i>=1;i--)b[i]=(b[i+1]*2+a[i])%P;for(ll i=1;i<=m;i++){ll l,r;scanf("%lld%lld",&l,&r);q[r].push_back(make_pair(l,i));}for(ll i=1;i<=n;i++){while(find(i)>1&&s[find(i)]>=0)merge(find(find(i)-1),find(i));sum[find(i)]=(sum[find(find(i)-1)]+f[find(i)])%P;for(ll j=0;j<q[i].size();j++){ll l=q[i][j].first,id=q[i][j].second;ans[id]=(sum[find(i)]-sum[find(l)]+P)*2%P;(ans[id]+=seek(l,find(l)+siz[find(l)]-1))%=P;}}for(ll i=1;i<=m;i++)printf("%lld\n",(ans[i]+P)%P);return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF878E-Numbers on the blackboard【并查集,贪心】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。