最大数(线段树pushup操作)

超、凢脫俗 2022-09-04 11:57 148阅读 0赞

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    const int N = 200007;
    
    int m, p;
    
    struct Node
    { 
    	int l, r;
    	int v;
    }tr[N * 4];
    
    void pushup(int u)
    { 
    	tr[u].v = max(tr[u<<1].v, tr[u<<1|1].v);
    }
    
    void build(int u, int l, int r)
    { 
    	tr[u].l = l, tr[u].r = r;
    	if(l == r) return;
    	int mid = (l+r) >> 1;
    	build(u<<1, l, mid), build(u<<1|1, mid+1, r);
    }
    
    int query(int u, int l, int 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 = query(u<<1, l, r);
    	if(mid < r) v = max(v, query(u<<1|1, l, r));
    	return v;
    }
    
    void modify(int u, int x, int 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(mid >= x) modify(u<<1, x, v);
    		else modify(u<<1|1, x, v);
    		pushup(u);	
    	}
    
    	
    }
    
    int main()
    { 
    	int last = 0, n = 0;
    	cin >> m >> p;
    	build(1,1,m);
    	while(m--)
    	{ 
    		int x;
    		char op[2];
    		scanf("%s %d",op, &x);
    		if(*op=='Q')
    		{ 
    			last = query(1, n-x+1, n);
    			printf("%d\n", last);
    		}else
    		{ 
    			modify(1,++n,(last+x)%p);
    		}
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，148人围观）

还没有评论，来说两句吧...

相关阅读

相关【*2200线段树Pushup】CF1567 E

[Problem - E - Codeforces][] 题意： ![b7beb74d49e74c8897a1e2cd5f65c1f3.png][] 思路：维护这些信

冷不防/ 2024年03月17日 17:54/ 0 赞/ 41 阅读

相关 poj3264（线段数求最大最小值）

Balanced Lineup <table> <tbody> <tr> <td><strong>Time Limit:</strong> 500

忘是亡心i/ 2024年02月18日 19:13/ 0 赞/ 23 阅读

相关 nyoj 1185 最大最小值（线段树）

最大最小值时间限制： 1000 ms | 内存限制： 65535 KB 难度： 2 描述给出N个整数，执行M次询问。对于每次询问，首先输入三个整数C、L、R

迈不过友情╰/ 2024年02月17日 21:12/ 0 赞/ 51 阅读

相关 246 区间最大公约数（线段树）

1. 问题描述：给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一： C l r d，表示把 A\[l\]，A\[l+1\]，…，A\[r\]

素颜马尾好姑娘i/ 2022年09月08日 00:13/ 0 赞/ 201 阅读

相关 1275 最大数（不带有懒标记的线段树）

1. 问题描述：给定一个正整数数列 a1，a2，…，an，每一个数都在 0∼p−1 之间。可以对这列数进行两种操作：添加操作：向序列后添加一个数，序列长度变成 n+1

绝地灬酷狼/ 2022年09月07日 06:12/ 0 赞/ 133 阅读

相关最大数(线段树pushup操作)

include <iostream> include <cstdio> using namespace std; const

超、凢脫俗/ 2022年09月04日 11:57/ 0 赞/ 149 阅读

相关 1270 数列区间最大值（线段树）

1. 问题描述：输入一串数字，给你 M 个询问，每次询问就给你两个数字 X，Y，要求你说出 X 到 Y 这段区间内的最大数。输入格式第一行两个整数 N，M 表示数字

青旅半醒/ 2022年09月03日 14:17/ 0 赞/ 146 阅读

相关序列操作（线段树，模板）

n个数，m次操作若a==1，求区间b-c最大值若a==2，将a\[ b \]改为c include<iostream> include<cstdi

小鱼儿/ 2022年01月07日 13:53/ 0 赞/ 221 阅读

相关 246. 区间最大公约数(线段树+树状数组)

题目链接：[https://www.acwing.com/problem/content/247/][https_www.acwing.com_problem_content_

一时失言乱红尘/ 2021年11月05日 19:52/ 0 赞/ 322 阅读

相关线段树区间最大连续区间和模板

题目背景小新经常陪小白去公园玩，也就是所谓的遛狗啦… 题目描述在小新家附近有一条“公园路”，路的一边从南到北依次排着nn个公园，小白早就看花了眼，自己也不清楚

r囧r小猫/ 2021年11月05日 05:48/ 0 赞/ 368 阅读