最新消息:热烈庆祝IT小记上线!

HDU 1754 I Hate It

Description

很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。 
这让很多学生很反感。 

不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。
 

Input

本题目包含多组测试,请处理到文件结束。 
在每个测试的第一行,有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。 
学生ID编号分别从1编到N。 
第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。 
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ,和两个正整数A,B。 
当C为'Q'的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。 
当C为'U'的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。 
 

Output

对于每一次询问操作,在一行里面输出最高成绩。
 

Sample Input

5 6 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 2 9 Q 1 5
 

Sample Output

5 6 5

9

单点更新求区间最值,splay练手题

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int maxn = 2e5 + 10;
int n, m, l, r, root, a[maxn];
char s[10];

struct Splays
{
	const static int maxn = 2e5 + 10;
	const static int INF = 0x7FFFFFFF;
	int ch[maxn][2], F[maxn], sz;
	int A[maxn], C[maxn], B[maxn];
	int Node(int f, int c) { ch[sz][0] = ch[sz][1] = 0; F[sz] = f; A[sz] = C[sz] = c; return sz++; }
	void clear(){ sz = 1; ch[0][0] = ch[0][1] = F[0] = 0; C[0] = -INF; }
	void rotate(int x, int k)
	{
		int y = F[x]; ch[y][!k] = ch[x][k]; F[ch[x][k]] = y;
		if (F[y]) ch[F[y]][y == ch[F[y]][1]] = x;
		F[x] = F[y];    F[y] = x;	ch[x][k] = y;
		C[x] = C[y];	C[y] = max(A[y], max(C[ch[y][0]], C[ch[y][1]]));
	}
	void Splay(int x, int r)
	{
		for (int fa = F[r]; F[x] != fa;)
		{
			if (F[F[x]] == fa) { rotate(x, x == ch[F[x]][0]); return; }
			int y = (x == ch[F[x]][0]), z = (F[x] == ch[F[F[x]]][0]);
			y^z ? (rotate(x, y), rotate(x, z)) : (rotate(F[x], z), rotate(x, y));
		}
	}
	void build(int f, int&x, int l, int r)
	{
		if (l > r) return;
		int mid = l + r >> 1;
		B[mid] = x = Node(f, a[mid]);
		build(x, ch[x][0], l, mid - 1);
		build(x, ch[x][1], mid + 1, r);
		C[x] = max(A[x], max(C[ch[x][0]], C[ch[x][1]]));
	}
	void change(int &x, int l, int r)
	{
		Splay(B[l], x);	x = B[l];
		A[x] = r;
		C[x] = max(r, max(C[ch[x][0]], C[ch[x][1]]));
	}
	void find(int &x, int l, int r)
	{
		Splay(B[l - 1], x);	x = B[l - 1];
		Splay(B[r + 1], ch[x][1]);	ch[x][1] = B[r + 1];
		printf("%d\n", C[ch[ch[x][1]][0]]);
	}
}solve;

int main()
{
	while (scanf("%d%d", &n, &m) != EOF)
	{
		solve.clear();	a[0] = a[n + 1] = -0x7FFFFFFF; root = 0;
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
		solve.build(0, root, 0, n + 1);
		while (m--)
		{
			scanf("%s%d%d", s, &l, &r);
			if (s[0] == 'Q') solve.find(root, l, r);
			else solve.change(root, l, r);
		}
	}
	return 0;
}


猜您喜欢

备案号:苏ICP备12016861号-4