Gorgeous Sequence(线段树)

快来打我* 2021-11-01 15:52 279阅读 0赞

题目链接:[http://acm.hdu.edu.cn/showproblem.php?pid=5306][http_acm.hdu.edu.cn_showproblem.php_pid_5306]  
Problem Description  
There is a sequence a of length n. We use ai to denote the i-th element in this sequence. You should do the following three types of operations to this sequence.

0 x y t: For every x≤i≤y, we use min(ai,t) to replace the original ai’s value.  
1 x y: Print the maximum value of ai that x≤i≤y.  
2 x y: Print the sum of ai that x≤i≤y.

Input  
The first line of the input is a single integer T, indicating the number of testcases.

The first line contains two integers n and m denoting the length of the sequence and the number of operations.

The second line contains n separated integers a1,…,an (∀1≤i≤n,0≤ai<231).

Each of the following m lines represents one operation (1≤x≤y≤n,0≤t<231).

It is guaranteed that T=100, ∑n≤1000000, ∑m≤1000000.

Output  
For every operation of type 1 or 2, print one line containing the answer to the corresponding query.

Sample Input

1  
5 5  
1 2 3 4 5  
1 1 5  
2 1 5  
0 3 5 3  
1 1 5  
2 1 5

Sample Output

5  
15  
3  
12

分析：  
tle到wa有tle 又wa。终于ac。  
55555555  
不知道被运算过程中爆int，折腾了多少次了。在已经要把这个题存档的时候，突然看到大佬程序中乘了1LL。遂改，秒过。留下了菜鸡的泪水。

参考博客：[https://blog.csdn.net/baidu\_36797646/article/details/82853316][https_blog.csdn.net_baidu_36797646_article_details_82853316]  
[https://www.cnblogs.com/shenben/p/6641984.html][https_www.cnblogs.com_shenben_p_6641984.html]  
[https://blog.csdn.net/nbl97/article/details/76696784][https_blog.csdn.net_nbl97_article_details_76696784]  
个人觉得这三篇博客的可读性还是比较高的。

同时建议：看一下：2016年国家队论文 吉如一 区间最值操作与历史最值问题

这个题目，有两个查询操作，一个改值操作。我们考虑如何用线段树来维护最大值，和。  
对于一个序列来说，我们维护和 和最大值并不是很难的操作。重点便是如何改值。  
在这里，我们同时维护最大值，次大值，最大值的个数。  
对于一个t而言，如果他大于当前结点的最大值了，那么必然直接return。  
如果t大于次大值，那么很明显这个结点里面的最大值都变成了t。同时可利用最大值个数修改sum。  
如果t小于此大值，则要递归两个孩子。

思路很简单，代码还是很多，bug还是找不到。留下了菜鸡的泪水。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    const int N = 1000010;
    
    ll sum[N << 2];
    int max_val[N << 2],seg_val[N << 2],num[N << 2];
    int T,a[N],n,m;
    
    void Tap_down(int id,int rmax)
    {
        if(max_val[id] <= rmax) return ;
        //这里注意，我一开始把rmax和max_val[id]写反了，好菜呀
        sum[id] = sum[id] - (max_val[id] - rmax) * (ll)num[id];
        max_val[id] = rmax;
    }
    void Push_down(int id)
    {
       Tap_down(id << 1,max_val[id]);
       Tap_down(id << 1 | 1,max_val[id]);
    }
    
    void Push_up(int id)
    {
        max_val[id] = max(max_val[id << 1],max_val[id << 1 | 1]);
        sum[id] = sum[id << 1] + sum[id << 1 | 1];
        if(max_val[id << 1] == max_val[id << 1 | 1])
        {
            seg_val[id] = max(seg_val[id << 1],seg_val[id << 1 | 1]);
            num[id] = num[id << 1] + num[id << 1 | 1]; return ;
        }
        if(max_val[id] == max_val[id << 1])
        {
            seg_val[id] = max(seg_val[id << 1],max_val[id << 1 | 1]); num[id] = num[id << 1]; return ;
        }
        seg_val[id] = max(seg_val[id << 1 | 1],max_val[id << 1]); num[id] = num[id << 1 | 1];
    }
    
    void Build_Tree(int id,int l,int r)
    {
        max_val[id] = -1; seg_val[id] = -1;
        num[id] = 0; sum[id] = 0;
        if(l == r)
        {
            max_val[id] = a[l]; sum[id] = a[l]; num[id] = 1;
            return ;
        }
        int mid = (l + r) >> 1;
        Build_Tree(id << 1,l,mid);Build_Tree(id << 1 | 1,mid + 1,r);
        Push_up(id);
    }
    
    void Update(int id,int L,int R,int l,int r,int v)
    {
        if(v >= max_val[id]) return ;
        if(l <= L && r >= R && seg_val[id] < v)
        {
            sum[id] = sum[id] - (max_val[id] - v) * (ll)num[id];
            max_val[id] = v;
            return ;
        }
        Push_down(id);
        int mid = (L + R) >> 1;
        if(l <= mid) Update(id << 1,L,mid,l,r,v);
        if(r > mid) Update(id << 1 | 1,mid + 1,R,l,r,v);
        Push_up(id);
    }
    
    ll Query_sum(int id,int L,int R,int l,int r)
    {
        if(l <= L && r >= R) return sum[id];
        Push_down(id);
        int mid = (L + R) >> 1;
        ll ans = 0;
        if(l <= mid) ans += Query_sum(id << 1,L,mid,l,r);
        if(r > mid) ans += Query_sum(id << 1 | 1,mid + 1,R,l,r);
        return ans;
    }
    
    int Query_max(int id,int L,int R,int l,int r)
    {
        if(l <= L && r >= R) return max_val[id];
        int mid = (L + R) >> 1; Push_down(id);
        int ans = 0;
        if(l <= mid) ans = max(ans,Query_max(id << 1,L,mid,l,r));
        if(r > mid) ans = max(ans,Query_max(id << 1 | 1,mid + 1,R,l,r));
        return ans;
    }
    
    void init()
    {
        for(int i = 0; i <= n << 2; i ++)
            {
                sum[i] = num[i] = 0;
                max_val[i] = -1; seg_val[i] = -1;
            }
    }
    
    int main()
    {
        scanf("%d",&T);
        while(T --)
        {
            scanf("%d%d",&n,&m);
            for(int i = 1; i <= n; i ++)
                scanf("%d",&a[i]);
            //init();
            Build_Tree(1,1,n);
            while(m --)
            {
                int op,x,y; scanf("%d%d%d",&op,&x,&y);
                if(op == 1)
                  printf("%d\n",Query_max(1,1,n,x,y));
                if(op == 2)
                  printf("%lld\n",Query_sum(1,1,n,x,y));
                if(op == 0)
                {
                    int t; scanf("%d",&t);
                    Update(1,1,n,x,y,t);
                }
            }
        }
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5306]: http://acm.hdu.edu.cn/showproblem.php?pid=5306
[https_blog.csdn.net_baidu_36797646_article_details_82853316]: https://blog.csdn.net/baidu_36797646/article/details/82853316
[https_www.cnblogs.com_shenben_p_6641984.html]: https://www.cnblogs.com/shenben/p/6641984.html
[https_blog.csdn.net_nbl97_article_details_76696784]: https://blog.csdn.net/nbl97/article/details/76696784