网站开发个人感想,创意定制,网站开发难点,留言页面设计模板正题
题目链接:https://www.luogu.com.cn/problem/P4428 题目大意
长度为nnn的0/10/10/1串要求支持
修改一个位置求区间[l,r][l,r][l,r]有多少个子区间重排后的二进制数可以被三整除 1≤n≤1051\leq n\leq 10^51≤n≤105 解题思路
首先有22k%31(k∈Z)2^{2k}\%31(k\in Z)22k…正题
题目链接:https://www.luogu.com.cn/problem/P4428 题目大意
长度为nnn的0/10/10/1串要求支持
修改一个位置求区间[l,r][l,r][l,r]有多少个子区间重排后的二进制数可以被三整除
1≤n≤1051\leq n\leq 10^51≤n≤105 解题思路
首先有22k%31(k∈Z)2^{2k}\%31(k\in Z)22k%31(k∈Z)和22k1%32(k∈Z)2^{2k1}\%32(k\in Z)22k1%32(k∈Z)。 分三种情况考虑
有111个111那么显然无论如何都不可以被三整除有2k2k2k个111那么我们之间都排在最后面就好了。有2k12k12k1个111kkk不能为000那么有一种方案就是把某个在奇数位置的111放到偶数位置就可以了此时需要区间的长度至少为2k32k32k3。
然后具体分析一下相当于一个区间111的个数不能为111且如果是奇数个那么必须至少有两个000。
看起来很复杂可以反过来做分成以下情况
区间全是111且长度为奇数区间有一个000且长度为偶数区间只有一个111由于222和333会重复一种只有一个111和一个000的情况所以需要加回这个方案
第四种是最好维护的顺便用树状数组记录就好了
然后前三种我们对于0/10/10/1的位置分别开一个setsetset来查询某个位置前驱/后继的0/1。
然后第三种情况我们对于每个111考虑左右的000区间然后记录在树状数组111的位置
对于第二种情况我们考虑对于每个000考虑左右的111然后记录在那个000的位置
对于第一种情况我们之间记录到区间最左端的000处。
然后统计答案的时候要记得把边界的情况考虑
写起来有点麻烦
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#includeset
#define lowbit(x) (x-x)
#define ll long long
using namespace std;
const ll N1e510;
ll n,m,a[N],t[N],p[N];
setll s[2];
void Change(ll x,ll val){while(xn){t[x]val;xlowbit(x);}return;
}
ll Ask(ll x){ll ans0;while(x){anst[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 (n1)/2*(n2-(n1))/2;}
ll Caunt(ll n)
{return n*(n1)/2;}
ll Calc(ll L,ll R)
{return (L/21)*((R1)/2)((L1)/2)*(R/21);}
void Updata(ll x){if(x1||xn)return;if(p[x])Change(x,-p[x]);if(a[x]){ll L(x-Left(1,x-1)-1),R(Right(1,x1)-x-1);p[x](L1)*(R1)-1;}else{ll L(x-Left(0,x-1)-1),R(Right(0,x1)-x-1);p[x]Calc(L,R)Count(R);}if(xna[x]!a[x1])p[x]--;Change(x,p[x]);return;
}
ll Get(ll x,ll l,ll r){ll Lmax(Left(0,x-1),l-1),Rmin(Right(0,x1),r1);Lx-L-1;RR-x-1;return Calc(L,R);
}
ll Qet(ll x,ll l,ll r){ll Lmax(Left(1,x-1),l-1),Rmin(Right(1,x1),r1);Lx-L-1;RR-x-1;return (L1)*(R1)-1;
}
signed main()
{scanf(%lld,n);s[0].insert(0);s[0].insert(n1);s[1].insert(0);s[1].insert(n1);for(ll i1;in;i)scanf(%lld,a[i]),s[a[i]].insert(i);for(ll i1;in;i)Updata(i);scanf(%lld,m);while(m--){ll op,l,r,x;scanf(%lld,op);if(op1){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,x1));Updata(Right(1,x1));}else{scanf(%lld%lld,l,r);ll ans(r-l1)*(r-l2)/2;if(Left(1,r)l){printf(%lld\n,ans);continue;}if(Left(0,r)l){ans-Count(r-l1);printf(%lld\n,ans);continue;}ans-Ask(r)-Ask(l-1);if(rna[r]!a[r1])ans--;ll LlLeft(0,l-1),RrRight(0,r1),LrLeft(0,r),RlRight(0,l);ansansGet(Rl,1,n)-Get(Rl,l,r);if(Lr!Rl)ansansGet(Lr,1,n)-Get(Lr,l,r);if(a[r1])ansansCount(Rr-Lr-1)-Count(r-Lr);if(a[l])ansans-Count(Rl-l);LlLeft(1,l),RrRight(1,r),LrLeft(1,r),RlRight(1,l);ansansQet(Rl,1,n)-Qet(Rl,l,r);if(Lr!Rl)ansansQet(Lr,1,n)-Qet(Lr,l,r);
// if(!a[r])ansansCaunt(Rr-Rl-1)-Caunt(r-Rl);
// if(!a[l])ansans-Caunt(Lr-l);printf(%lld\n,ans);}}return 0;
}
