我们发现维护左边的0和右边的1就行了
线段树区间维护一下
#include<bits/stdc++.h> #define rep(i,a,n) for(int i=a;i<=n;++i) #define per(i,a,n) for(int i=n;i>=a;--i) #define pb push_back #define fi first #define se second #define io std::ios::sync_with_stdio(false) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int P = 1e9+7, INF = 0x3f3f3f3f; inline int lson(int x){return x*2;} inline int rson(int x){return x*2+1;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; } ll qpow(ll a,ll n) { ll r=1%P; for (a%=P; n; a=a*a%P,n>>=1)if(n&1)r=r*a%P; return r; } const int maxn=3e5+10; int sum[4*maxn][2]; int summ[4*maxn]; void pushup(int id) { int ls=lson(id); int rs=rson(id); summ[id]=summ[ls]+summ[rs]; summ[id]+=min(sum[ls][1],sum[rs][0]); sum[id][1]=sum[ls][1]+sum[rs][1]-min(sum[ls][1],sum[rs][0]); sum[id][0]=sum[ls][0]+sum[rs][0]-min(sum[ls][1],sum[rs][0]); } void add(int id,int l,int r,int ql,int qr,int x) { if(l==r) { sum[id][x]++; return ; } int mid=(l+r)/2; if(ql>mid) add(rson(id),mid+1,r,ql,qr,x); else add(lson(id),l,mid,ql,qr,x); pushup(id); } pair<int,pair<int,int> > query(int id,int l,int r,int ql,int qr) { if(l>=ql&&r<=qr) { return {summ[id],{sum[id][1],sum[id][0]}}; } if(r<ql||l>qr) return {0,{0,0}};//然后很好奇的发现pair居然能这么写，以后妈妈再也不用担心我的make_pair打成make_piar了 int mid=(l+r)/2; auto x=query(lson(id),l,mid,ql,qr); auto y=query(rson(id),mid+1,r,ql,qr); pair<int,pair<int,int> > p; p.fi=x.fi+y.fi; p.fi+=min(x.se.fi,y.se.se); p.se.fi=x.se.fi+y.se.fi-min(x.se.fi,y.se.se); p.se.se=x.se.se+y.se.se-min(x.se.fi,y.se.se); return p; } int main() { int n; cin>>n; for(int i=1;i<=n;i++) { int x; cin>>x; add(1,1,n,i,i,x); } int q; cin>>q; while(q--) { int x,y; cin>>x>>y; cout<<query(1,1,n,x,y).fi<<endl; } }