写给自己看，记自己错的几个点
#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <iostream> using namespace std; typedef long long ll; const int MAXN = int (1e5) + 5; const int INF = (1 << 30); #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r #define rclen (curlen >> 1) #define lclen (curlen - rclen) #define getMid ((l + r) >> 1) int arr[MAXN]; int llen[MAXN << 2]; int rlen[MAXN << 2]; int maxlen[MAXN << 2]; void push_up(int rt, int l, int r) { int curlen = r - l + 1; llen[rt] = llen[rt << 1]; rlen[rt] = rlen[rt << 1 | 1]; maxlen[rt] = max(maxlen[rt << 1], maxlen[rt << 1 | 1]);//不是max(llen[rt], rlen[rt]) int m = getMid; if (arr[m] < arr[m + 1]) { if (llen[rt] == lclen) llen[rt] += llen[rt << 1 | 1]; if (rlen[rt] == rclen) rlen[rt] += rlen[rt << 1]; int t = rlen[rt << 1] + llen[rt << 1 | 1]; maxlen[rt] = max(t, max(maxlen[rt << 1], maxlen[rt << 1 | 1]));//不是max(t, max(llen[rt], rlen[rt])) } } void build(int rt, int l, int r) { if (l == r) { scanf("%d", &arr[l]); llen[rt] = rlen[rt] = maxlen[rt] = 1; return; } int m = getMid; build(lson); build(rson); push_up(rt, l, r); } void updata(int val, int L, int R, int rt, int l, int r) { if (L <= l && r <= R) { arr[l] = val; llen[rt] = rlen[rt] = maxlen[rt] = 1; return; } int m = getMid; if (L <= m) updata(val, L, R, lson); if (R > m) updata(val, L, R, rson); push_up(rt, l, r); } int query(int L, int R, int rt, int l, int r) { if (L <= l && r <= R) return maxlen[rt]; int m = getMid; int a = 0, b = 0; if (L <= m) a = query(L, R, lson); if (R > m) b = query(L, R, rson); int ans = max(a, b);//不是相加 if (arr[m] < arr[m + 1]) { int t = min(rlen[rt << 1], m - L + 1) + min(llen[rt << 1 | 1], R - m); //两个min是确保查询范围不越界 ans = max(ans, t); } return ans; } int main(void) { freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); /*ios::sync_with_stdio(false); cin.tie(0);*/ char op[2]; int T, n, m, a, b; scanf("%d", &T); while (T--) { scanf("%d %d", &n, &m); build(1, 0, n - 1); while (m--) { scanf("%s %d %d", op, &a, &b); if (op[0] == 'Q') printf("%d\n", query(a, b, 1, 0, n - 1)); else updata(b, a, a, 1, 0, n - 1); } } return 0; }
