【悬关】线段树求调
  • 板块CF1473D Program
  • 楼主kimi0705
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/7/30 18:07
  • 上次更新2023/11/3 06:52:53
查看原帖
【悬关】线段树求调
637788
kimi0705楼主2023/7/30 18:07
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int K = 1e3 + 10;
const int L = 1e4 + 10;
const int M = 1e5 + 10;
const int N = 1e6 + 10;
int t, n, q, l, r;
int arr[2 * M];
string s;
struct Tree {
    int l, r, maxx, minn;
} tree[8 * M];
void build (int l, int r, int id) {
    tree[id].l = l;
    tree[id].r = r;
    if (l == r) {
        tree[id].maxx = arr[l];
        tree[id].minn = arr[l];
        return;
    }
    int mid = (l + r) >> 1;
    build (l, mid, id * 2);
    build (mid + 1, r, id * 2 + 1);
    tree[id].maxx = max (tree[id * 2].maxx, tree[id * 2 + 1].maxx);
    tree[id].minn = min (tree[id * 2].minn, tree[id * 2 + 1].minn);
    return;
}
int Maxx (int l, int r, int id) {
    if(l > r) return INT_MIN;
    if (tree[id].r < l || r < tree[id].l) return INT_MIN;
    if (l <= tree[id].l && tree[id].r <= r) return tree[id].maxx;
    return max (Maxx (l, r, id * 2), Maxx (l, r, id * 2 + 1) );
}
int Minn (int l, int r, int id) {
    if(l > r) return INT_MAX;
    if (tree[id].r < l || r < tree[id].l) return INT_MAX;
    if (l <= tree[id].l && tree[id].r <= r) return tree[id].minn;
    return min (Minn (l, r, id * 2), Minn (l, r, id * 2 + 1) );
}
signed main() {
    //  freopen (".\\data\\in.txt", "r", stdin);
    //  freopen (".\\data\\out.txt", "w", stdout);
    ios::sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);
    cin >> t;
    while (t--) {
        cin >> n >> q >> s;
        s = " " + s;
        for (int i = 1; i <= n; i++) arr[i] = (s[i] == '+' ? 1 : -1);
        for (int i = 1; i <= n; i++) arr[i] += arr[i - 1];
        build(1, n, 1);
        while (q--) {
            cin >> l >> r;
            cout << max (Maxx (1, l - 1, 1), Maxx (r + 1, n, 1) - arr[r] + arr[l - 1]) - min(Minn (1, l - 1, 1), Minn (r + 1, n, 1) - arr[r] + arr[l - 1]) + 1 << '\n';
        }
    }
    return 0;
}
/*
    ┏━━┛   ┻━━━━━━━┛   ┻┓
    ┃           ┃
    ┃    ━━      ┃
    ┃   ┳━┛     ┗━┳    ┃
    ┃            ┃
    ┃     ┻      ┃
    ┃             ┃
    ┗━┓   ┏━━━━━━━━━━┛
      ┃   ┃   神兽保佑
      ┃   ┃   AC Accept 得分100!
      ┃   ┗━━━━━━━━━━━━━━━┓
      ┃            ┃
      ┃            ┃
      ┗━┓━┓━┏━┓━┳ ━━━┓━┓━┏━┓━┳
        ┃   ┫   ┫    ┃   ┫   ┫
        ┗━┻━┛━━━┗    ┗━┻━┛━━━┗
*/
2023/7/30 18:07
加载中...