[信息学奥赛一本通T1550-花神游历各国] 区间更新负优化

136 阅读 0 评论 0 点赞

# 区间更新改为区间每个点都改一次，属于是负优化了,能过就行

```cpp
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define all(v) v.begin(), v.end()
#define PII pair<int,int>
using namespace std;
const int N =  1 *1e6 + 10,M = 5 * 1e3 + 10,inf = 0x3f3f3f3f;

int n,m;
int a[N];
struct node
{
    int l,r;
    LL sum,maxx;
}tr[N*4];
void pushup(int u) //从子节点更新父节点信息
{
    tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
    tr[u].maxx = max(tr[u<<1].maxx,tr[u<<1|1].maxx);
}
void build(int u,int l,int r)
{
    if(l==r) tr[u] = {l,r,a[r],a[r]};
    else
    {
        tr[u] = {l,r};
        int mid = l + r >> 1;
        build(u<<1,l,mid) , build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void modify(int u,int l,int r)
{
    if(tr[u].l==tr[u].r) //每个点都改
    {
        tr[u].sum = sqrt(tr[u].sum);
        tr[u].maxx = sqrt(tr[u].maxx);
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        // 区间内最大值大于1就继续暴力开根号
        if(l <= mid && tr[u<<1].maxx > 1) modify(u<<1,l,r);
        if(r > mid && tr[u<<1|1].maxx > 1) modify(u<<1|1,l,r);
        pushup(u);
    }
}
LL query(int u,int l,int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    
    int mid = tr[u].l + tr[u].r >> 1;
    LL res = 0;
    if(l <= mid) res = query(u<<1,l,r);
    if(r > mid) res += query(u<<1|1,l,r);
    return res;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    cin>>m;
    while (m--)
    {
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1) cout<<query(1,l,r)<<endl;
        else modify(1,l,r);
    }
    
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
    // cin>>_;
    while(_--)
    {
        solve();
    }
    return 0;
}

/**
 *    author: Nijika_jia
 *    created: 2024.10.17 16:31:13
 */
```

0.0分

2 人评分

本文分类：题解列表
浏览次数：136 次浏览
发布日期：2024-10-17 17:25:31
本文链接：https://blog.dotcpp.com/a/106653

上一篇 > 清晰可见方法求解母牛数量(递归)
下一篇 > 使用暴力算法和二分解决给定定数

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

[信息学奥赛一本通T1550-花神游历各国] 区间更新负优化

评论列表共有 0 条评论

发表评论取消回复

[信息学奥赛一本通T1550-花神游历各国] 区间更新负优化

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复