洛谷P6492

youyong1 / 2024-10-11 / 原文

题意：对一个点进行修改，然后进行查询符合条件的子串。思路：单点修改+查询，很容易想到线段树，用线段树来存，考虑每一次修改后进行合并，然后看能不能合并于是用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;
}