求助做法或思路

hh20080501hh @ 2024-03-27 16:02:13

by bamboo12345 @ 2024-03-27 16:13:04

序列是 1 inf 1 inf 1 inf……这样构造是不是就挂了

by hh20080501hh @ 2024-03-27 16:22:42

@bamboo1030 应该不会挂吧，因为我维护了次大值，可以直接返回最大值个数

by bamboo12345 @ 2024-03-27 16:28:44

@hh20080501hh 那我稍微弄一下呗

1 inf 2 inf-1 3 inf-3……

by bamboo12345 @ 2024-03-27 16:29:08

打错了是 inf-2 但是大概是那个意思

by hh20080501hh @ 2024-03-27 16:29:28

附上代码，方便大家卡我QAQ

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+10 , INF = 1e9;

int n , m;
int a[N];

struct node 
{
    int l , r;
    int mx , semx , cntmx;
    int mn , semn , cntmn;
    int add;
}tr[N<<2];

void pushup (node &rt , node l , node r)
{
    if (l.mx==r.mx) //处理最大值 
    {
        rt.mx = l.mx , rt.cntmx = l.cntmx+r.cntmx;
        rt.semx = max(l.semx , r.semx);
    }
    else if (l.mx>r.mx)
    {
        rt.mx = l.mx , rt.cntmx = l.cntmx;
        rt.semx = max(l.semx , r.mx);
    }
    else 
    {
        rt.mx = r.mx , rt.cntmx = r.cntmx;
        rt.semx = max(r.semx , l.mx);
    }
    if (l.mn==r.mn) //处理最小值
    {
        rt.mn = l.mn , rt.cntmn = l.cntmn+r.cntmn;
        rt.semn = min(l.semn , r.semn);
    } 
    else if (l.mn<r.mn)
    {
        rt.mn = l.mn , rt.cntmn = l.cntmn;
        rt.semn = min(l.semn , r.mn);
    }
    else 
    {
        rt.mn = r.mn , rt.cntmn = r.cntmn;
        rt.semn = min(r.semn , l.mn);
    }
}
void pushup (int u)
{
    pushup (tr[u] , tr[u<<1] , tr[u<<1|1]);
}

void build (int u , int l , int r)
{
    if (l==r)
    {
        tr[u] = {l , r , a[l] , -INF , 1 , a[l] , INF , 1 , 0};
    }
    else 
    {
        tr[u].l = l , tr[u].r = r;
        int mid = (l+r)>>1;
        build (u<<1 , l , mid) , build (u<<1|1 , mid+1 , r);
        pushup (u);
    }
}

void update (int u , int c) //偷懒少写几次更新 
{
    tr[u].add += c;
    tr[u].mn += c , tr[u].mx += c;
    tr[u].semn += c , tr[u].semx += c;  
}

void pushdown (int u)
{
    if (tr[u].add)
    {
        update (u<<1 , tr[u].add) , update (u<<1|1 , tr[u].add);
        tr[u].add = 0;
    }
}

void modify (int u , int l , int r , int c)
{
    if (tr[u].l>=l && tr[u].r<=r)
    {
        update (u , c);
    }
    else 
    {
        pushdown (u);
        int mid = (tr[u].l+tr[u].r)>>1;
        if (l<=mid)
        {
            modify (u<<1 , l , r , c);
        }
        if (r>mid)
        {
            modify (u<<1|1 , l , r , c);
        }
        pushup (u);
    }
}

int query (int u , int l , int r , int c)
{
    if (tr[u].l>=l && tr[u].r<=r)
    {
        if (tr[u].mn>=c) return tr[u].r-tr[u].l+1;
        if (tr[u].mx<c) return 0;
        if (tr[u].mx>=c && tr[u].semx<c) return tr[u].cntmx;
        if (tr[u].mn<c && tr[u].semn>=c) return tr[u].r-tr[u].l+1-tr[u].cntmn;
    }
    pushdown (u);
    int mid = (tr[u].l+tr[u].r)>>1;
    int res = 0;
    if (l<=mid)
    {
        res += query (u<<1 , l , r , c);
    }
    if (r>mid)
    {
        res += query (u<<1|1 , l , r , c);
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;
    for (int i=1 ; i<=n ; i++)
    {
        cin >> a[i];
    }

    build (1 , 1 , n);

    while (m--)
    {
        string s;
        int l , r , c;
        cin >> s >> l >> r >> c;
        if (s=="A")
        {
            cout << query (1 , l , r , c) << '\n';
        }
        else 
        {
            modify (1 , l , r , c);
        }
    }
    return 0;
}

by hh20080501hh @ 2024-03-27 16:32:36

@bamboo1030 稍等一下，我拍一下试试

by hh20080501hh @ 2024-03-27 16:40:40

@bamboo1030 确实被卡掉了，跑了3s

by bamboo12345 @ 2024-03-27 16:43:56

@hh20080501hh 主要是你这个其实递归的层数没有保证啊和区间颜色数挂钩的 所以其实如果你按上面的序列全部询问 [1, n] 会卡满

by bamboo12345 @ 2024-03-27 16:44:29

直接退化 O(n)

by hh20080501hh @ 2024-03-27 16:46:39

@bamboo1030 也就是说这道题必须用分块吗？