109徐守佳

用户名：dotcpp0787174

访问量：976

签　名：

想AC的我戴上了WA面具

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

　　自我简介：

TA的其他文章

[蓝桥杯2017年第八届真题-油漆面积] 扫描线
浏览：38

二分直接用现成的STL:lower_bound/upper_bound(新增手写二分)
浏览：59

[信息学奥赛一本通T1247-河中跳房子] 二分答案
浏览：40

你可能喜欢

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

　　作者: 109徐守佳　　　　发表时间：2024-10-17 17:25:31 浏览：16　|　评论：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语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C二级辅导-统计字符（C语言代码）

C二级辅导-进制转换（C语言代码）

点我有惊喜！你懂得！

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

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

评论区

精彩推荐

母牛的故事（C语言代码）

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

哥德巴赫曾猜测（C语言代码）

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

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

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

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

用筛法求之N内的素数。（C语言代码）详解………………

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

Manchester- A+B for Input-Output Practice (IV)

109徐守佳

TA的其他文章

你可能喜欢

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

C二级辅导-统计字符 （C语言代码）

C二级辅导-进制转换 （C语言代码）

点我有惊喜！你懂得！

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

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

评论区

精彩推荐

母牛的故事 （C语言代码）

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

哥德巴赫曾猜测 （C语言代码）

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

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

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

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

用筛法求之N内的素数。 （C语言代码） 详解………………

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

Manchester- A+B for Input-Output Practice (IV)

C二级辅导-统计字符（C语言代码）

C二级辅导-进制转换（C语言代码）

　　评论区

母牛的故事（C语言代码）

哥德巴赫曾猜测（C语言代码）

用筛法求之N内的素数。（C语言代码）详解………………