Codeforces Educational Round 102 D.Program 线段树合并

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题目大意

给出一个字符串序列,字符串仅由-和+组成,一开始有个初始的值x为0,-表示x = x-1,+表示x = x+1。

每次询问给出一个l和r,表示忽视[l,r]区间内的字符串,剩下的操作进行执行,求问x在操作过程中不同的值的个数。

题解

一开始看成区间内不同数的个数了,十分钟打完板子才发现不对。

虽然不是区间内不同数的个数,但是也是一道线段树的题目,且看下面的分析。

首先我们注意到,数x每次无论变大还是变小,每次变化的绝对值一定为1。这样我们就能够用x到达的最大值mx减去x的最小值mi,之后加上1,即为最终的答案。

于是我们只需要维护某一段区间操作使x能够变到的最大值和最小值分别是多少。

但是这样会出现一个问题,区间合并的时候应该怎么做。因为左侧区间得出的最终值一定会影响右侧区间的结果,所以这给我们的合并造成了一定的麻烦的影响。

但是影响是能解决的,因为产生影响的只有区间操作产生的对于这个区间的x最终结果的影响,所以我们只需要记录一下区间操作对x的最终结果的影响就好了。

这样我们就需要记录以下三个参数:

struct tree{
    int l,r,rval,mx,mi;
    tree operator + (const tree &x)const{
        tree res;
        res.mx = max(mx,rval + x.mx);
        res.mi = min(mi,rval + x.mi);
        res.rval = rval + x.rval;
        return res;
    }
    void init(){
        mx = 0;
        mi = INF;
        rval = 0;
    }
}tr[maxn<<2];

重载的operator +,就是区间的合并操作。

然后我们用线段树求解即可,具体求解方法就是,分别求出忽视的区间的左边和右边的操作区间的影响(struct结构),然后进行合并即可。

注意最小值小于0或者最大值大于0的情况,需要给答案+1,因为一开始x就是0。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int t;
int n,m;
string s;
int a[maxn];
const int INF = 1e7;
map<int,int>mp;
struct tree{
    int l,r,rval,mx,mi;
    tree operator + (const tree &x)const{
        tree res;
        res.mx = max(mx,rval + x.mx);
        res.mi = min(mi,rval + x.mi);
        res.rval = rval + x.rval;
        return res;
    }
    void init(){
        mx = 0;
        mi = INF;
        rval = 0;
    }
}tr[maxn<<2];
void push_up(int now){
    tr[now].mx = max(tr[now<<1].mx,tr[now<<1].rval+tr[now<<1|1].mx);
    tr[now].mi = min(tr[now<<1].mi,tr[now<<1].rval+tr[now<<1|1].mi);
    tr[now].rval = tr[now<<1].rval + tr[now<<1|1].rval;
}
void build(int now,int l,int r){
    tr[now].l = l;
    tr[now].r = r;
    tr[now].rval = 0;
    tr[now].mx = 0;
    tr[now].mi = INF;
    if(l == r){
        tr[now].rval = tr[now].mx = tr[now].mi = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(now<<1,l,mid);
    build(now<<1|1,mid+1,r);
    push_up(now);
    return;
}
tree query(int now,int l,int r){
    if(tr[now].l >= l && tr[now].r <= r){
        return tr[now];
    }
    tree res;
    res.init();
    int mid = (tr[now].l + tr[now].r) >> 1;
    if(r <= mid)
        res = query(now<<1,l,r);
    if(l > mid)
        res = query(now<<1|1,l,r);
    else if(l <= mid && r > mid)
        res = query(now<<1,l,r) + query(now<<1|1,l,r);
    return res;
}
struct que{
    int l,r;
    bool operator < (const que &b)const{
        return this->r < b.r || (this->r == b.r && this->l < b.l);
    }
}q[maxn];
tree ansl,ansr,ans;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--){
        cin >> n >> m;
        cin >> s;
        int now = 0;
        for(int i = 0;i < n;++i){
            if(s[i] == '-')
                a[i+1] = -1;
            else a[i+1] = 1;
        }
        build(1,1,n);
        for(int i = 1;i <= m;++i){
            cin >> q[i].l >> q[i].r;
            ansl.init();
            ansr.init();
            if(q[i].l == 1 && q[i].r == n){
                cout << "1\n";
                continue;
            }
            else if(q[i].l == 1){
                ans = query(1,q[i].r+1,n);
            }
            else if(q[i].r == n){
                ans = query(1,1,q[i].l - 1);
            }
            else{
                ans = query(1,1,q[i].l-1) + query(1,q[i].r+1,n);
            }
            cout << ans.mx - ans.mi + 1 + (ans.mi > 0 || ans.mx < 0) << "\n";
        }
    }
    return 0;
}


Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00