正題

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

---

題目大意

長度為$n$的$0/1$串要求支持

修改一個(gè)位置

求區(qū)間$[l,r]$有多少個(gè)子區(qū)間重排后的二進(jìn)制數(shù)可以被三整除

$1\le n\le 10^5$

---

解題思路

首先有$2^{2k}\%3=1(k\in Z)$和$2^{2k+1}\%3=2(k\in Z)$。
分三種情況考慮

• 有$1$個(gè)$1$那么顯然無論如何都不可以被三整除
• 有$2k$個(gè)$1$那么我們之間都排在最后面就好了。
• 有$2k+1$個(gè)$1$（$k$不能為$0$），那么有一種方案就是把某個(gè)在奇數(shù)位置的$1$放到偶數(shù)位置就可以了，此時(shí)需要區(qū)間的長度至少為$2k+3$。

然后具體分析一下相當(dāng)于一個(gè)區(qū)間$1$的個(gè)數(shù)不能為$1$且如果是奇數(shù)個(gè)那么必須至少有兩個(gè)$0$。

看起來很復(fù)雜可以反過來做分成以下情況

區(qū)間全是$1$且長度為奇數(shù)

區(qū)間有一個(gè)$0$且長度為偶數(shù)

區(qū)間只有一個(gè)$1$

由于$2$和$3$會(huì)重復(fù)一種只有一個(gè)$1$和一個(gè)$0$的情況所以需要加回這個(gè)方案

第四種是最好維護(hù)的，順便用樹狀數(shù)組記錄就好了

然后前三種我們對(duì)于$0/1$的位置分別開一個(gè)$set$來查詢某個(gè)位置前驅(qū)/后繼的0/1。

然后第三種情況我們對(duì)于每個(gè)$1$考慮左右的$0$區(qū)間然后記錄在樹狀數(shù)組$1$的位置

對(duì)于第二種情況我們考慮對(duì)于每個(gè)$0$考慮左右的$1$然后記錄在那個(gè)$0$的位置

對(duì)于第一種情況我們之間記錄到區(qū)間最左端的$0$處。

然后統(tǒng)計(jì)答案的時(shí)候要記得把邊界的情況考慮

寫起來有點(diǎn)麻煩

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

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<set> #define lowbit(x) (x&-x) #define ll long long using namespace std; const ll N=1e5+10; ll n,m,a[N],t[N],p[N]; set<ll> s[2]; void Change(ll x,ll val){while(x<=n){t[x]+=val;x+=lowbit(x);}return; } ll Ask(ll x){ll ans=0;while(x){ans+=t[x];x-=lowbit(x);}return ans; } ll Left(ll op,ll x) {return (*--s[op].upper_bound(x));} ll Right(ll op,ll x) {return (*s[op].lower_bound(x));} ll Count(ll n) {return (n+1)/2*(n+2-(n&1))/2;} ll Caunt(ll n) {return n*(n+1)/2;} ll Calc(ll L,ll R) {return (L/2+1)*((R+1)/2)+((L+1)/2)*(R/2+1);} void Updata(ll x){if(x<1||x>n)return;if(p[x])Change(x,-p[x]);if(a[x]){ll L=(x-Left(1,x-1)-1),R=(Right(1,x+1)-x-1);p[x]=(L+1)*(R+1)-1;}else{ll L=(x-Left(0,x-1)-1),R=(Right(0,x+1)-x-1);p[x]=Calc(L,R)+Count(R);}if(x<n&&a[x]!=a[x+1])p[x]--;Change(x,p[x]);return; } ll Get(ll x,ll l,ll r){ll L=max(Left(0,x-1),l-1),R=min(Right(0,x+1),r+1);L=x-L-1;R=R-x-1;return Calc(L,R); } ll Qet(ll x,ll l,ll r){ll L=max(Left(1,x-1),l-1),R=min(Right(1,x+1),r+1);L=x-L-1;R=R-x-1;return (L+1)*(R+1)-1; } signed main() {scanf("%lld",&n);s[0].insert(0);s[0].insert(n+1);s[1].insert(0);s[1].insert(n+1);for(ll i=1;i<=n;i++)scanf("%lld",&a[i]),s[a[i]].insert(i);for(ll i=1;i<=n;i++)Updata(i);scanf("%lld",&m);while(m--){ll op,l,r,x;scanf("%lld",&op);if(op==1){scanf("%lld",&x);s[a[x]].erase(x);a[x]=!a[x];s[a[x]].insert(x);Updata(x);Updata(Left(0,x-1));Updata(Left(1,x-1));Updata(Right(0,x+1));Updata(Right(1,x+1));}else{scanf("%lld%lld",&l,&r);ll ans=(r-l+1)*(r-l+2)/2;if(Left(1,r)<l){printf("%lld\n",ans);continue;}if(Left(0,r)<l){ans-=Count(r-l+1);printf("%lld\n",ans);continue;}ans-=Ask(r)-Ask(l-1);if(r<n&&a[r]!=a[r+1])ans--;ll Ll=Left(0,l-1),Rr=Right(0,r+1),Lr=Left(0,r),Rl=Right(0,l);ans=ans+Get(Rl,1,n)-Get(Rl,l,r);if(Lr!=Rl)ans=ans+Get(Lr,1,n)-Get(Lr,l,r);if(a[r+1])ans=ans+Count(Rr-Lr-1)-Count(r-Lr);if(a[l])ans=ans-Count(Rl-l);Ll=Left(1,l),Rr=Right(1,r),Lr=Left(1,r),Rl=Right(1,l);ans=ans+Qet(Rl,1,n)-Qet(Rl,l,r);if(Lr!=Rl)ans=ans+Qet(Lr,1,n)-Qet(Lr,l,r); // if(!a[r])ans=ans+Caunt(Rr-Rl-1)-Caunt(r-Rl); // if(!a[l])ans=ans-Caunt(Lr-l);printf("%lld\n",ans);}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P4428-[BJOI2018]二进制【树状数组,set】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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