109徐守佳

用户名：dotcpp0787174

访问量：1101

签　名：

想AC的我戴上了WA面具

等　　级
排　　名	884
经　　验	3544
参赛次数	3
文章发表	30
年　　龄	20
在职情况	学生
学　　校	内江师范学院
专　　业	虹夏虹夏虹

　　自我简介：

TA的其他文章

[信息学奥赛一本通T1471-Phone List] Trie字典树做法
浏览：25

[信息学奥赛一本通T1684-Secret Message 秘密信息] 平平无奇的Trie树
浏览：25

[CSP-J2020] 优秀的拆分--DFS+剪枝
浏览：45

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

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

　　作者: 109徐守佳　　　　发表时间：2024-10-17 17:25:31 浏览：17　|　评论：0　

原题链接：信息学奥赛一本通T1550-花神游历各国

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

```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 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

1028

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

矩形面积交（C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （Java代码）

A+B for Input-Output Practice (VII) （C++代码）

求组合数（C语言代码）

剪刀石头布（C语言代码）

C语言训练-数字母（C语言代码）

Hello, world! （C语言代码）

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

1028

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

矩形面积交 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （Java代码）

A+B for Input-Output Practice (VII) （C++代码）

求组合数 （C语言代码）

剪刀石头布 （C语言代码）

C语言训练-数字母 （C语言代码）

Hello, world! （C语言代码）

　　评论区

矩形面积交（C语言代码）

求组合数（C语言代码）

剪刀石头布（C语言代码）

C语言训练-数字母（C语言代码）