題目描述：

小火車沉迷垃圾手游不能自拔，正在玩碧藍航線，可惜小火車的艦（lao）隊（po）練度太低打不過副本，所以他只好去刷其余的副本來升級。
總共有 n 個副本編號從 1 到 n ，每個副本有個難度值 a_i，小火車每天按照順序刷連續的一段副本，第 j 天會刷的副本必須落在 l 到 r 之間。但是他是個很懶的人，每天一開始他的懶惰值為 0，當他刷完一個副本以后懶惰值就會異或上 a_i ，小火車希望懶惰值一直保持單調不下降，請問每天他都有多少種刷副本的方法？

題解：

如果我們能夠求出每個位置最遠可以延伸到哪里，那么這題就簡單了。
注意到異或上某個數后異或和會變小，當且僅當這個數最高位的$1$把原來這個位上的$1$給消掉了，所以我們可以對每個位單獨考慮，看每個位最近的這個位置是什么，然后取每個位的$\min$。具體可以對每個位二分實現。

代碼：

#include<bits/stdc++.h> using namespace std; #define LL long long #define pa pair<int,int> const int Maxn=100010; const int inf=1000000000; int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*f; } int n,a[Maxn],fir[Maxn],b[Maxn],d[Maxn][30],sum[2][30][Maxn]; //sum[i][j][k]第j位 前k個1個數奇偶性為i 有多少個最高位為j int lc[Maxn<<5],rc[Maxn<<5],s1[Maxn<<5],tot=0,root[Maxn]; LL s2[Maxn<<5]; void insert(int &u,int l,int r,int p) {if(!u)u=++tot;s1[u]++;s2[u]+=(LL)p;if(l==r)return;int mid=l+r>>1;if(p<=mid)insert(lc[u],l,mid,p);else insert(rc[u],mid+1,r,p); } void merge(int &u1,int u2) {if(!u1){u1=u2;return;}if(!u2)return;s1[u1]+=s1[u2],s2[u1]+=s2[u2];merge(lc[u1],lc[u2]),merge(rc[u1],rc[u2]); } int ans1;LL ans2; void query(int r1,int r2,int l,int r,int k) {if(l==r){ans1+=s1[r1]-s1[r2];ans2+=s2[r1]-s2[r2];return;}int mid=l+r>>1;if(k<=mid)query(lc[r1],lc[r2],l,mid,k);else{ans1+=s1[lc[r1]]-s1[lc[r2]],ans2+=s2[lc[r1]]-s2[lc[r2]];query(rc[r1],rc[r2],mid+1,r,k);} } int main() {n=read();for(int i=1;i<=n;i++){a[i]=read();fir[i]=-1;for(int j=29;j>=0;j--)if((1<<j)&a[i]){fir[i]=j;break;}}for(int i=29;i>=0;i--){int now=0;for(int j=1;j<=n;j++){if((1<<i)&a[j])now^=1;d[j][i]=now;for(int k=0;k<30;k++)sum[0][i][j]=sum[0][i][j-1],sum[1][i][j]=sum[1][i][j-1];if(fir[j]==i)sum[now][i][j]++;}}for(int i=1;i<=n;i++){b[i]=n;for(int j=29;j>=0;j--){if(!((1<<j)&a[i])){int t=d[i][j];int l=i+1,r=n;while(l<=r){int mid=l+r>>1;if(sum[t][j][mid]>sum[t][j][i])r=mid-1;else l=mid+1;}b[i]=min(b[i],r);}else{int t=(d[i][j]^1);int l=i+1,r=n;while(l<=r){int mid=l+r>>1;if(sum[t][j][mid]>sum[t][j][i])r=mid-1;else l=mid+1;}b[i]=min(b[i],r);}}}root[0]=0;for(int i=1;i<=n;i++)insert(root[i],1,n,b[i]),merge(root[i],root[i-1]);LL ans=0;int q=read();while(q--){LL l=read(),r=read();l=(l+ans)%n+1,r=(r+ans)%n+1;if(l>r)swap(l,r);ans1=ans2=0;query(root[r],root[l-1],1,n,r);ans=ans2+(LL)r*(r-l+1-ans1)-(LL)(l-1+r-1)*(r-l+1)/2LL;printf("%lld\n",ans);} }

總結

以上是生活随笔為你收集整理的loj#6100. 「2017 山东二轮集训 Day1」第一题 主席树+二分的全部內容，希望文章能夠幫你解決所遇到的問題。

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