线段树模版（懒标记 区间修改）

题目

蓝桥云第20场 宝玉出行

具体实现

#include <iostream>
#include<algorithm>
#include<string>
using namespace std;
int n, d, q;
const int N = 2e5 + 10;
string s;
struct node {
    int l, r;
    int maxx;
    int tag;
}tr[4 * N + 10];//大小为4*N
void pushup(int u) {
    tr[u].maxx = max(tr[u << 1].maxx, tr[u << 1 | 1].maxx);
}
void build(int u, int l, int r)
{
    if (l == r) // 叶子结点
    {
        tr[u].l = l;
        tr[u].r = r;
        tr[u].maxx = 0;
        tr[u].tag = 0;
    }
    else
    {
        tr[u].l = l;
        tr[u].r = r;
        tr[u].maxx = 0;
        tr[u].tag = 0;
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }
}
void pushdown(int u) { //下传标记函数
    if (tr[u].tag) {  //有懒标记才下传
        tr[u << 1].maxx += tr[u].tag, tr[u << 1 | 1].maxx += tr[u].tag;
        tr[u << 1].tag += tr[u].tag, tr[u << 1 | 1].tag += tr[u].tag;
        tr[u].tag = 0;  //懒标记记得清零
    }
}
void modify(int u, int l, int r, int q) // 区间修改
{
    if (tr[u].l >= l && tr[u].r <= r) //
    {
        tr[u].maxx += q;
        tr[u].tag += q;
        //cout << u << " " << tr[u].maxx<<" "<<tr[u].l<<" "<<tr[u].r << " " << tr[u].tag << "\n";
        return;
    }
    // 根据更改操作修改叶子结点的值，然后注意同时更新 tr[u] 维护的所有变量信息
    else
    {
        pushdown(u);//递归左右区间前要分裂
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (l <= mid) modify(u << 1, l, r, q);//虽然分裂一半但还是要传递原区间（易错点）
        if (r >= mid + 1) modify(u << 1 | 1, l, r, q);
        pushup(u);//递归操作，更新结果
    }
}
int kth(int u, int k) {//二分线段树，查找第一个大于k的序号
    if (tr[u].l == tr[u].r) {
        if (tr[u].maxx <= k)return -1;
        else return tr[u].l;
    }
    else {
        pushdown(u);
        if (tr[u << 1].maxx > k)return kth(u << 1, k);
        else return kth(u << 1 | 1, k);
    }
}
int a[N];
int main()
{
    cin >> n >> d;
    cin >> s;
    cin >> q;
    build(1, 1, n + 10);
    for (int i = 0; i < n; i++) {
        a[i] = s[i] - '0';
        if (a[i] == 1)modify(1, i + 1, min(i + d, n), 1);
        //cout << tr[1].maxx <<" "<<i<<"\n";
    }
    for (int i = 1; i <= q; i++) {
        int op, x;
        cin >> op >> x;
        if (op == 1) {
            if (a[x - 1] == 0)modify(1, x, min(x + d - 1, n), 1);
            else modify(1, x, min(x + d - 1, n), -1);
            a[x - 1] ^= 1;//翻转操作，影响后续查询和翻转
            //cout << tr[1].maxx << "\n";
        }
        else {
            cout << kth(1, x) << "\n";
        }
    }
    return 0;
}