10.22 树状数组

https://codeforces.com/contest/1838/problem/D
都在代码里了
const int INF = 1e9;
struct Info{//定义一个结构体
int mn;
Info() : mn(INF) {}//调用这个自定义函数就把mn变成极大值
Info(int mn) : mn(mn) {}//调用这个自定义函数就把mn变成你输入的值
};

using Tag = int;

Info operator+(const Info &a, const Info &b){//排序
return {min(a.mn, b.mn)};
}

void apply(Info &x, Tag &a, Tag f){
x.mn += f;
a += f;
}

template<class Info, class Tag>
struct LazySegmentTree{
int n;
vector info;//树状数组
vector tag;//懒标记

LazySegmentTree() {}

LazySegmentTree(int n, Info _init = Info()){
    init(vector<Info>(n, _init));
}

LazySegmentTree(const vector<Info> &_init){
    init(_init);
}

void init(const vector<Info> &_init){//建立树状数组
    n = (int)_init.size();
    info.assign((n << 2) + 1, Info());
    tag.assign((n << 2) + 1, Tag());
    function<void(int, int, int)> build = [&](int p, int l, int r){
        if (l == r){
            info[p] = _init[l - 1];
            return;
        }
        int m = (l + r) / 2;
        build(2 * p, l, m);
        build(2 * p + 1, m + 1, r);
        pull(p);
    };
    build(1, 1, n);
}

void pull(int p){
    info[p] = info[2 * p] + info[2 * p + 1];
}

void apply(int p, const Tag &v){
    ::apply(info[p], tag[p], v);
}

void push(int p){
    apply(2 * p, tag[p]);
    apply(2 * p + 1, tag[p]);
    tag[p] = Tag();
}

void modify(int p, int l, int r, int x, const Info &v){//区间变值
    if (l == r){
        info[p] = v;
        return;
    }
    int m = (l + r) / 2;
    push(p);
    if (x <= m){
        modify(2 * p, l, m, x, v);
    } 
    else{
        modify(2 * p + 1, m + 1, r, x, v);
    }
    pull(p);
}

void modify(int p, const Info &v){//单点变值
    modify(1, 1, n, p, v);
}

Info query(int p, int l, int r, int x, int y){
    if (l > y || r < x){
        return Info();
    }
    if (l >= x && r <= y){
        return info[p];
    }
    int m = (l + r) / 2;
    push(p);
    return query(2 * p, l, m, x, y) + query(2 * p + 1, m + 1, r, x, y);
}

Info query(int l, int r){
    return query(1, 1, n, l, r);
}

void modify(int p, int l, int r, int x, int y, const Tag &v){
    if (l > y || r < x){
        return;
    }
    if (l >= x && r <= y){
        apply(p, v);
        return;
    }
    int m = (l + r) / 2;
    push(p);
    modify(2 * p, l, m, x, y, v);
    modify(2 * p + 1, m + 1, r, x, y, v);
    pull(p);
}

void modify(int l, int r, const Tag &v){
    return modify(1, 1, n, l, r, v);
}

int find_first(int p, int l, int r, int L, int R, const function<bool(const Info&)> &f, Info &pre){
    if (l > R || r < L){
        return r + 1;
    }
    if (l >= L && r <= R){
        if (!f(pre + info[p])){
            pre = pre + info[p];
            return r + 1;
        }
        if (l == r) return r;
        int m = (l + r) / 2;
        push(p);
        int res;
        if (f(pre + info[2 * p])){
            res = find_first(2 * p, l, m, L, R, f, pre);
        }
        else{
            pre = pre + info[2 * p];
            res = find_first(2 * p + 1, m + 1, r, L, R, f, pre);
        }
        return res;
    }
    int m = (l + r) / 2;
    push(p);
    int res = m + 1;
    if (L <= m){
        res = find_first(2 * p, l, m, L, R, f, pre);
    }
    if (R > m && res == m + 1){
        res = find_first(2 * p + 1, m + 1, r, L, R, f, pre);
    }
    return res;
}

int find_first(int l, int r, const function<bool(const Info&)> &f){//找到第一个满足条件的（加一个自己设置的函数）
    Info pre = Info();
    return find_first(1, 1, n, l, r, f, pre);
}

int find_last(int p, int l, int r, int L, int R, const function<bool(const Info&)> &f, Info &suf){
    if (l > R || r < L){
        return l - 1;
    }
    if (l >= L && r <= R){
        if (!f(info[p] + suf)){
            suf = info[p] + suf;
            return l - 1;
        }
        if (l == r) return r;
        int m = (l + r) / 2;
        push(p);
        int res;
        if (f(info[2 * p + 1] + suf)){
            res = find_last(2 * p + 1, m + 1, r, L, R, f, suf);
        }
        else{
            suf = info[2 * p + 1] + suf;
            res = find_last(2 * p, l, m, L, R, f, suf);
        }
        return res;
    }
    int m = (l + r) / 2;
    push(p);
    int res = m;
    if (R > m){
        res = find_last(2 * p + 1, m + 1, r, L, R, f, suf);
    }
    if (L <= m && res == m){
        res = find_last(2 * p, l, m, L, R, f, suf);
    }
    return res;        
}

int find_last(int l, int r, const function<bool(const Info&)> &f){//找到最后一个满足条件的（加一个自己设置的函数）
    Info suf = Info();
    return find_last(1, 1, n, l, r, f, suf);
}

};

void solve()
{
int n,q;
cin>>n>>q;
string s;
vector init(n);
sets1,s2;
cin>>s;
s=" "+s+" ";
int sum=0;
if(n%2)
{
while(q--)
{
int x;
cin>>x;
cout<<"NO"<<endl;
}
}
for(int i=1;i<=n;i++)
{
if(s[i]'(' && s[i-1]'(') s1.insert(i-1);
if(s[i]')' && s[i-1]')') s2.insert(i-1);
if(s[i]'(') sum++;
else sum--;
init[i-1]={sum};//init里全部是前缀和
}
LazySegmentTree<Info, Tag> seg(init);//建树 自定义了树的名字叫做seg
while(q--)
{
int x;
cin>>x;
if(s[x]'(' && s[x-1]'(') s1.erase(x-1);
if(s[x]'(' && s[x+1]'(') s1.erase(x);
if(s[x]')' && s[x-1]')') s2.erase(x-1);
if(s[x]')' && s[x+1]==')') s2.erase(x);

    if(s[x]=='(') 
    {
        s[x]=')';
        sum-=2;
        seg.modify(x,n,-2);
    }
    else
    {
        s[x]='(';
        sum+=2;
        seg.modify(x,n,2);
    }

    if(s[x]=='(' && s[x-1]=='(') s1.insert(x-1);
    if(s[x]=='(' && s[x+1]=='(') s1.insert(x);
    if(s[x]==')' && s[x-1]==')') s2.insert(x-1);
    if(s[x]==')' && s[x+1]==')') s2.insert(x);
    
    auto f1 = [&](const Info &info){//自己写一个内置函数判断
        return info.mn < 0;//这里前面肯定出现了连续的')' 
    };

    auto f2 = [&](const Info &info){
        return info.mn < sum;//这里后面肯定出现了连续的'('
    };

    int pos1=seg.find_first(1,n,f1);
    int pos2=seg.find_last(1,n,f2);
    bool ok=1;
    if(pos1!=n+1)//找到了
    {
        auto it=s1.lower_bound(pos1);
        if(it==s1.begin()) ok=0;//只要第一个大于pos1(不可能等于嘛)不是第一个数 就意味着前面还有合法点
    }
    if(pos2!=0)//找到了
    {
        auto it=s2.lower_bound(pos2);
        if(it==s2.end()) ok=0;
    }
    if(ok) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

}