記'1'為+1,'0'為-1;
可以發現
pre[i],suf[i]分別為前/后綴和
a[i]=max(pre[l.....i]);
b[i]=max(suf[i+1....r]);
ans=max(a[l]+b[l],a[l+1]+b[l+1],........a[r]+b[r]);
即ans=最大的不相交的(前綴和+后綴和)
證明：
首先下界是顯然的，即不可能比這個答案更小。
至于上界， 可以大力分類討論證明。
比如
假如存在一個后綴不合法
設ans=pre[l]+suf[r];
設這個不合法的后綴位置為k。
k>l時:
此時suf[r]顯然可以在保證pre[l]不變的情況下找到一個更大的取值，矛盾。
k<l時:
此時有一個顯然的結論是
t=sum[l+1..r-1]<=0
因為>0的話顯然可以再保證pre[l]不變的情況下找到一個更大的suf[r]。
再設p=sum[k..l-1]，p+t顯然大于0
顯然這時答案不會超過pre[l]-p+suf[r]+p+t=pre[l]+suf[r]+t
因為t<=0，不會更優
得證
最后，用線段樹維護即可
每一個節點保存對應區間的區間和，最大前綴，最大后綴，答案
#include<iostream>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define N 220000
#define eps 1e-7
#define inf 1e9+7
#define ll long long
using namespace std;
inline int read()
{char ch=0;int x=0,flag=1;while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*flag;
}
struct tree
{int tot,pre,suf,ans;
}node[N*4];
tree operator+(tree a,tree b)
{tree ans;ans.tot=a.tot+b.tot;ans.pre=max(a.pre,b.pre+a.tot);ans.suf=max(b.suf,a.suf+b.tot);ans.ans=max(a.pre+b.suf,max(a.ans+b.tot,b.ans+a.tot));return ans;
}
char s[N];
struct Segment_Tree
{#define lson o<<1#define rson o<<1|1#define mid ((l+r)>>1) inline void pushup(int o){node[o]=node[lson]+node[rson];}void build(int o,int l,int r){if(l==r){if(s[l-1]=='1')node[o]=(tree){1,1,1,1};else node[o]=(tree){-1,0,0,0};return;}build(lson,l,mid);build(rson,mid+1,r);pushup(o);}tree query(int o,int l,int r,int ql,int qr){if(ql<=l&&r<=qr)return node[o];bool flag1=ql<=mid,flag2=qr>mid;if(flag1&&flag2)return query(lson,l,mid,ql,qr)+query(rson,mid+1,r,ql,qr);else{if(flag1)return query(lson,l,mid,ql,qr);if(flag2)return query(rson,mid+1,r,ql,qr);}}
}T;
int main()
{int n=read(),m=read(),i,l,r;scanf("%s",s);T.build(1,1,n);for(i=1;i<=m;i++){l=read();r=read();printf("%d\n",T.query(1,1,n,l,r).ans);}return 0;
}
轉載于:https://www.cnblogs.com/Creed-qwq/p/10016092.html
總結
以上是生活随笔為你收集整理的正睿 2018 提高组十连测 Day4 T3 碳的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
