前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >P1198 [JSOI2008]最大数 线段树入门

P1198 [JSOI2008]最大数 线段树入门

作者头像
用户2965768
发布2019-10-22 19:57:58
3780
发布2019-10-22 19:57:58
举报
文章被收录于专栏:wym

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/qq_41603898/article/details/102325619

代码语言:javascript
复制
#include <bits/stdc++.h>
#define ll long long
const int maxn = 200005;
using namespace std;
ll mod;
struct N{
	ll val,mx;
}no[maxn<<2];
void build(int p,int l,int r){
	no[p].val = -1e18;
	no[p].mx = -1e18;
	if(l==r)return ;
	int mid = (l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}
void update(int p,int l,int r,int id,ll val){
	if(l>r)return ;
	if(l==r){
		no[p].val = val;
		no[p].mx = val;
		return ;
	}
	int mid = (l+r)>>1;
	if(id<=mid)update(p<<1,l,mid,id,val);
	else if(id>mid)update(p<<1|1,mid+1,r,id,val);
	no[p].mx = max(no[p<<1].mx,no[p<<1|1].mx)%mod;
}
ll query(int p,int l,int r,int L,int R){
	if(l>r)return -1e18;
	if(L<=l&&R>=r){
		return no[p].mx;
	}
	int mid = (l+r)>>1;
	long long as = -1e18;
	if(L<=mid)as = max(as,query(p<<1,l,mid,L,R));
	if(R>mid)as = max(as,query(p<<1|1,mid+1,r,L,R));
	return as;
}
int main()
{
	int n = 0,m;
	char op[2];
	ll t=0,q;
	scanf("%d %lld",&m,&mod);
	build(1,1,maxn);
	for(int i=1;i<=m;i++){
		scanf("%s",op);
		if(op[0]=='Q'){
			int l;	scanf("%d",&l);
			t = query(1,1,maxn,n-l+1,n);
			printf("%lld\n",t);
		}else {
			scanf("%lld",&q);
			n++;
			update(1,1,maxn,n,(q+t)%mod);
		}
	}
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/10/07 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档