題目大意

有一個二進制數，讓你進行以下操作：

將一個區(qū)間的數字按升/降序排列

查詢一個區(qū)間的數字構成的數

---

解題思路

可以用線段樹來維護每一位，預處理出2的整次冪，上傳時把左兒子乘上右兒子長度次冪即可

---

code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 200210 #define wyc 1000000007 using namespace std; ll n,m,x,y,z,a[N],v[N]; char s[N]; struct node {node(ll lenn=0,ll numm=0,ll summ=0){len=lenn;num=numm;sum=summ;}ll len,num,sum; }; node merge(node a,node b) {node c;c.len=a.len+b.len;c.num=(a.num*v[b.len]%wyc+b.num)%wyc;c.sum=a.sum+b.sum;return c; } struct Tree {#define ls x*2#define rs x*2+1node s[N<<2];ll lazy[N<<2];void push_up(ll x){s[x]=merge(s[ls],s[rs]);return;}void get(ll x,ll y){lazy[x]=y;s[x].num=(v[s[x].len]+wyc-1)%wyc*y;s[x].sum=s[x].len*y;return;}void push_down(ll x){if(lazy[x]!=-1){get(ls,lazy[x]);get(rs,lazy[x]);lazy[x]=-1;}return;}void build(ll x,ll l,ll r){lazy[x]=-1;if(l==r){s[x]=node(1,a[l],a[l]);return;}ll mid=l+r>>1;build(ls,l,mid);build(rs,mid+1,r);push_up(x);return;}void change(ll x,ll L,ll R,ll l,ll r,ll y){if(L==l&&R==r){get(x,y);return;}ll mid=L+R>>1;push_down(x);if(r<=mid)change(ls,L,mid,l,r,y);else if(l>mid)change(rs,mid+1,R,l,r,y);else change(ls,L,mid,l,mid,y),change(rs,mid+1,R,mid+1,r,y);push_up(x);return;}node ask(ll x,ll L,ll R,ll l,ll r){if (L==l&&R==r)return s[x];ll mid=L+R>>1;push_down(x);if(r<=mid)return ask(ls,L,mid,l,r);else if(l>mid)return ask(rs,mid+1,R,l,r);else return merge(ask(ls,L,mid,l,mid),ask(rs,mid+1,R,mid+1,r));} }T; int main() {scanf("%s",s+1);n=strlen(s+1);v[0]=1;for(ll i=1;i<=n;++i){a[i]=s[i]-48;v[i]=v[i-1]*2%wyc;}T.build(1,1,n);scanf("%lld",&m);while(m--){scanf("%lld",&x);if(x==1){scanf("%lld%lld",&x,&y);z=T.ask(1,1,n,x,y).sum;if(!z||z==y-x+1)continue;T.change(1,1,n,x,y,0);T.change(1,1,n,x,x+z-1,1);}else if(x==2){scanf("%lld%lld",&x,&y);z=T.ask(1,1,n,x,y).sum;if(!z||z==y-x+1)continue;T.change(1,1,n,x,y,0);T.change(1,1,n,y-z+1,y,1);}else{scanf("%lld%lld",&x,&y);printf("%lld\n",T.ask(1,1,n,x,y).num%wyc);}}return 0; }

總結

以上是生活随笔為你收集整理的【线段树】二进制的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。