109徐守佳

用户名：dotcpp0787174

访问量：1104

签　名：

想AC的我戴上了WA面具

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

　　自我简介：

TA的其他文章

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

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

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

你可能喜欢

[信息学奥赛一本通T1549-最大数] 线段树--单点修改区间查询

　　作者: 109徐守佳　　　　发表时间：2024-09-25 00:43:25 浏览：25　|　评论：0　

原题链接：信息学奥赛一本通T1549-最大数

```cpp
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N =  2 *1e5 + 10,M = 2 * 1e3 + 10,inf = 0x3f3f3f3f;

struct node
{
    int l,r; //每个节点的左边界和右边界
    int v; // 存储每个节点区间的最大值
}tr[4 * N]; //线段树开4倍大空间

void build(int u,int l,int r) //建立线段树
{
    tr[u] = {l,r}; //给每个节点区间赋值
    if(l==r) return; //左边界等于右边界退出
    int mid = l+r >> 1; //求区间中点
    build(u<<1,l,mid),build(u<<1|1,mid+1,r); //创建左孩子节点和右孩子节点
}

void pushup(int u) //更新节点最大值操作
{
    tr[u].v = max(tr[u<<1].v , tr[u<<1|1].v); 
    //从左孩子和右孩子中更新该区间的最大值
}

void modify(int u,int x,int v) //单点修改操作:从父节点开始找到x的位置修改为v
{
    if(tr[u].l == x && tr[u].r == x) tr[u].v = v; 
    //左孩子右孩子等于这个点说明找到了,赋值
    else
    {
        int mid = tr[u].l+tr[u].r >> 1; //取区间中点
        if(x <= mid) modify(u<<1,x,v); //如果单点在中点左边,往左孩子走,否则右
        else modify(u<<1|1,x,v);
        pushup(u); //随时更新区间最大值
    }
}

int quary(int u,int l,int r) //询问操作,返回[l,r]中的最大值
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].v; //如果该询问区间包含了左孩子和右孩子,直返回该区间存储的最大值
    int mid = tr[u].l+tr[u].r >> 1;
    int v = 0;
    if(l <= mid) v = quary(u<<1,l,r); 
    //左边界小于等于该区间的中点,继续递归,最大值可能在左孩子区间
    if(r > mid) v = max(v,quary(u<<1|1,l,r));
    //右边界大于等于该区间的中点,继续递归,最大值可能在右孩子区间
    return v;  //最终返回找到的最大值
}

void solve()
{
    int n=0,last=0;
    int m,p;
    cin>>m>>p;
    build(1,1,m);
    while (m--)
    {
        char op[2];
        int x;
        cin>>op>>x;
        if(op[0]=='Q')
        {
            last = quary(1,n-x+1,n); //询问返回最后x个元素的最大值
            cout<<last<<endl;
        }
        else
        {
            modify(1,n+1,(last + x) % p); //单点修改也可以新增,在n+1加一个数
            n++;
        }
    }
    
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    // int _; cin>>_; while(_--){}
    solve();
    return 0;
}
```

0.0分

1 人评分

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

109徐守佳

TA的其他文章

你可能喜欢

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

字符逆序（C语言代码）

Lucky Word （C++代码）

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

简单编码（C++代码）

[信息学奥赛一本通T1549-最大数] 线段树--单点修改区间查询

评论区

精彩推荐

【回文数(二)】（C语言代码）

求圆的面积（C语言代码）

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

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

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

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

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

敲七（C++代码）

整除的尾数（C语言代码）

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

109徐守佳

TA的其他文章

你可能喜欢

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

字符逆序 （C语言代码）

Lucky Word （C++代码）

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

简单编码 （C++代码）

[信息学奥赛一本通T1549-最大数] 线段树--单点修改区间查询

评论区

精彩推荐

【回文数(二)】 （C语言代码）

求圆的面积 （C语言代码）

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

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

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

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

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

敲七 （C++代码）

整除的尾数 （C语言代码）

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

字符逆序（C语言代码）

简单编码（C++代码）

　　评论区

【回文数(二)】（C语言代码）

求圆的面积（C语言代码）

敲七（C++代码）

整除的尾数（C语言代码）