HDU 3308 LCIS

旧城等待， 2022-03-29 06:28 129阅读 0赞

区间合并。给出一些数，记为a\[i\]，两种操作。U x y表示把a\[x\] 的值改为 y。Q x y表示求xy间的最长连续上升序列（LCIS）。这里的x y都是从0开始的。

其实吧，就是比较当前区间的左右子区间能否相连，也就是说要看a\[k\] 与 a\[k + 1\]的大小关系（k表示区间中点）。其他操作跟“正常”题一样。

#pragma comment(linker, "/STACK:1024000000,1024000000")
    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<vector>
    #include<queue>
    #include<cmath>
    ///LOOP
    #define REP(i, n) for(int i = 0; i < n; i++)
    #define FF(i, a, b) for(int i = a; i < b; i++)
    #define FFF(i, a, b) for(int i = a; i <= b; i++)
    #define FD(i, a, b) for(int i = a - 1; i >= b; i--)
    #define FDD(i, a, b) for(int i = a; i >= b; i--)
    ///INPUT
    #define RI(n) scanf("%d", &n)
    #define RII(n, m) scanf("%d%d", &n, &m)
    #define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)
    #define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p)
    #define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q)
    #define RFI(n) scanf("%lf", &n)
    #define RFII(n, m) scanf("%lf%lf", &n, &m)
    #define RFIII(n, m, k) scanf("%lf%lf%lf", &n, &m, &k)
    #define RFIV(n, m, k, p) scanf("%lf%lf%lf%lf", &n, &m, &k, &p)
    #define RS(s) scanf("%s", s)
    ///OUTPUT
    #define PN printf("\n")
    #define PI(n) printf("%d\n", n)
    #define PIS(n) printf("%d ", n)
    #define PS(s) printf("%s\n", s)
    #define PSS(s) printf("%s ", n)
    #define PC(n) printf("Case %d: ", n)
    ///OTHER
    #define PB(x) push_back(x)
    #define CLR(a, b) memset(a, b, sizeof(a))
    #define CPY(a, b) memcpy(a, b, sizeof(b))
    #define display(A, n, m) {REP(i, n){REP(j, m)PIS(A[i][j]);PN;}}
    #define lson l, m, rt << 1
    #define rson m + 1, r, rt << 1 | 1
    
    using namespace std;
    typedef long long LL;
    typedef pair<int, int> P;
    const int MOD = 9901;
    const int INFI = 1e9 * 2;
    const LL LINFI = 1e17;
    const double eps = 1e-6;
    const double pi = acos(-1.0);
    const int N = 111111;
    const int M = 22;
    const int move[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, 1, -1, -1, 1, -1, -1};
    
    int a[N], msum[N << 2], lsum[N << 2], rsum[N << 2], num, n;
    
    void pushup(int rt, int k, int m)
    {
        lsum[rt] = lsum[rt << 1];
        rsum[rt] = rsum[rt << 1 | 1];
        msum[rt] = max(msum[rt << 1], msum[rt << 1 | 1]);
        if(a[k] < a[k + 1])
        {
            if(lsum[rt] == (m - (m >> 1)))lsum[rt] += lsum[rt << 1 | 1];
            if(rsum[rt] == (m >> 1))rsum[rt] += rsum[rt << 1];
            msum[rt] = max(msum[rt], lsum[rt << 1 | 1] + rsum[rt << 1]);
        }
    }
    
    void build(int l, int r, int rt)
    {
        if(l == r)
        {
            RI(a[num++]);
            msum[rt] = rsum[rt] = lsum[rt] = 1;
            return;
        }
        int m = (l + r) >> 1;
        build(lson);
        build(rson);
        pushup(rt, m, r - l + 1);
    }
    
    void update(int p, int x, int l, int r, int rt)
    {
        if(l == r)
        {
            a[p] = x;
            return;
        }
        int m = (l + r) >> 1;
        if(p <= m)update(p, x, lson);
        else update(p, x, rson);
        pushup(rt, m, r - l + 1);
    }
    
    int query(int L, int R, int l, int r, int rt)
    {
        if(L <= l && r <= R)return msum[rt];
        int m = (l + r) >> 1, ans = 0;
        if(L <= m)ans = max(ans, query(L, R, lson));
        if(R > m)ans = max(ans, query(L, R, rson));
        if(a[m] < a[m + 1] && L <= m && m < R)
        {
            int tl = min(rsum[rt << 1], m - L + 1);
            int tr = min(lsum[rt << 1 | 1], R - m);
            ans = max(ans, tl + tr);
        }
        return ans;
    }
    
    int main()
    {
        //freopen("input.txt", "r", stdin);
    
        int t, m, x, y;
        char op[5];
        RI(t);
        while(t--)
        {
            RII(n, m);
            num = 1;
            build(1, n, 1);
            while(m--)
            {
                RS(op);
                RII(x, y);
                if(op[0] == 'Q')PI(query(x + 1, y + 1, 1, n, 1));
                else update(x + 1, y, 1, n, 1);
            }
        }
        return 0;
    }