题解 | 1or0
1or0
https://www.nowcoder.com/practice/b08001c812604203acf0bc43e54d3bdf
#include<bits/stdc++.h> #define int long long using namespace std; int const N = 2e5+9; int const inf = 1e9+7; string s; int n,q; pair<int,int> block[N]; int a[N]; int cnt; signed main() { cin>>n; cin>>s; s = " " + s; int m = 0,last = -1,l = 1,r = 1; for(int i=1;i<=n;i++) { if(last == s[i] || last == -1) { last = s[i]; r = i; } else { if(last == '0') { block[++cnt] = make_pair(l,r); } last = s[i]; l = i,r = i; } } if(last == '0') block[++cnt] = make_pair(l,r); for(int i=1;i<=cnt;i++) { int len = block[i].second - block[i].first + 1; a[i] = a[i-1] + (len + 1) * len / 2; } cin>>q; for(int i=1;i<=q;i++) { int l,r; cin>>l>>r; if(r < block[1].first || l > block[cnt].second) { int len = r - l + 1; cout<<len * (len + 1) / 2<<endl; continue; } int pl = -1,pr = -1; int L = 1,R = cnt; while(L < R) { int m = (L + R + 1) >> 1; if(block[m].first > r) R = m - 1; else L = m; } pr = L; L = 1,R = cnt; while(L < R) { int m = (L + R) >> 1; if(block[m].second < l) L = m + 1; else R = m; } pl = R; int ans = 0; if(block[pl].first <= l && l <= block[pl].second) { int len = block[pl].second - l + 1; ans += len * (len + 1) / 2; pl++; } if(block[pr].first <= r && r <= block[pr].second) { int len = r - block[pr].first + 1; ans += len * (len + 1) / 2; pr--; } if(pl <= pr) ans += a[pr] - a[pl-1]; int len = r - l + 1; cout<<max((len + 1) * len / 2 - ans,0ll)<<endl; } return 0; } /* 1 1 2 2 + 1 3 3 + 2 +1 */
糖丸了,用二分求了一下左边界向右的第一个0段,右边界向左的第一个0段。
然后处理了下边界情况,即边界在一个0段中。
但是向右,向左两边遍历就可以预处理出i向左,向右的第一个0段。