题意：对一个点进行修改，然后进行查询符合条件的子串。思路：单点修改+查询，很容易想到线段树，用线段树来存，考虑每一次修改后进行合并，然后看能不能合并于是用3个数组来表示，分别表示该节点编号下的区间内最长的01串的前后缀的长度。
点击查看代码
#include <iostream>
#include <stack>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
#include <climits>
#include <string.h>
#include <map>
#include <queue>
#include <list>
#include <cmath>
#include <iomanip>
#define int long long
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lc u<<1
#define rc u<<1|1
#define gcd __gcd
#define double long double
#define endl "\n"
#define INF LLONG_MAX
#define mod 1000000007
#define N 200005
const double PI = 3.14159265358979323846;
using namespace std;
int n, m;
int a[N], sum[N*4], lsum[N*4], rsum[N*4];//分别代表区间内最大的01字串一个前缀区间最大的01字串一个后缀区间最大的01字串
void push_up(int u, int l, int r)
{
int mid = l + r >> 1;
int L = mid - l + 1, R = r - mid;//左右孩子长
lsum[u] = lsum[lc], rsum[u] = rsum[rc], sum[u] = max(sum[lc], sum[rc]);//先从左右孩子身上找最值
if (a[mid] != a[mid + 1])//考虑连接情况
{
sum[u] = max(sum[u], rsum[lc] + lsum[rc]);//维护最大值
if (sum[lc] == L)lsum[u] = L + lsum[rc];//可以前面加上后面的前缀和长度
if (sum[rc] == R)rsum[u] = R + rsum[lc];//后面可以加上前面的后缀和长度
}
}
void build(int u, int l, int r)
{
sum[u] = 1;lsum[u] = 1;rsum[u] = 1;//初始化
if (l == r)return;
int mid = l + r >> 1;
build(lc, l, mid); build(rc, mid + 1, r);
push_up(u, l, r);
}
void update(int u, int l, int r, int idx)
{
if (l == r && l == idx)
{
a[l] ^= 1;
return;
}
int mid = l + r >> 1;
if (idx <= mid)update(lc, l, mid, idx);
else update(rc, mid + 1, r, idx);
push_up(u, l, r);
}
signed main() {
ios;
cin >> n >> m;
build(1, 1, n);
while (m--)
{
int x; cin >> x;
update(1, 1, n, x);
cout << sum[1] << endl;
}
return 0;
}