欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[线段树] [洛谷] P1531 I Hate It

程序员文章站 2022-03-22 13:12:38
...

[线段树] [洛谷] P1531 I Hate It

线段树的区间查询和单点更新

复习敲一下

//#pragma GCC optimize(2)
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;

const int MAXN = 1e6 + 10;

int arr[MAXN] ;

int tree[MAXN];

int N, M;

void init(int now, int l, int r)
{
    if(l == r)
    {
    	tree[now] = arr[l];
    	return ;
	}

    int mid = l + (r - l) / 2;

    init(now * 2, l, mid);
	
	init(now * 2 + 1, mid + 1, r);

    tree[now] = max(tree[now * 2], tree[now * 2 + 1]);

}

void change(int now, int l, int r, int find, int key)
{
	if(r < find || l > find)
		return ;
	if(l == r)
	{
		if(tree[now] < key)
			tree[now] = key;
		return ;
	}
	
	int mid = l + (r - l) / 2;
	
	change(now * 2, l, mid, find, key);
	
	change(now * 2 + 1, mid + 1, r, find, key);
	
	tree[now] = max(tree[now * 2], tree[now * 2 + 1]);
}

int qury(int now, int l, int r, int x, int y)
{
	if(l > y || r < x)
		return 0;
	if(x <= l && y >= r)
	{
		return tree[now];
	}
	
	int ans = 0;
	
	int mid = l + (r - l) / 2;
	
	ans = max(ans, qury(now * 2, l, mid, x, y) );
	
	ans = max(ans, qury(now * 2 + 1, mid + 1, r, x, y) );
	
	return ans;
}

int main()
{
    ios::sync_with_stdio(false);

    cin.tie(0);     cout.tie(0);

    cin>>N>>M;

    for(int i = 1; i <= N; i++)
        cin>>arr[i];

    init(1, 1, N);

    while(M--)
    {
    	char oprt;
    	
    	int x, y;
    	
    	cin>>oprt>>x>>y;
    	
    	if(oprt == 'Q')
    	{
    		cout<<qury(1, 1, N, x, y)<<endl;
    		
		}
    	
    	else
    	{
    		change(1, 1, N, x, y);
		}
	}

    return 0;
}