题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=100010;

int a[N];
int n,m;
struct node
{
    int l,r;
    int v;//求区间的最大值 
}t[4*N];



void pushup(int u)//由子节点的信息来推父节点的信息 
 {
    t[u].v=max(t[u<<1].v,t[u<<1|1].v);
 }

 void build(int u,int l,int r)
 {
    t[u]={l,r};
    if(l==r) return;
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u); 
 }

 int query(int u,int l,int r)
 {
    if(t[u].l>=l&&t[u].r<=r) return t[u].v;

    int mid=t[u].l+t[u].r>>1;
    int v=0;
    if(l<=mid) v=query(u<<1,l,r);
    if(r>mid) v=max(v,query(u<<1|1,l,r));
    return v;
 }
 void modify(int u,int x,int v)
 {
    if(t[u].l==x&&t[u].r==x) t[u].v=v;
    else
    {
        int mid=t[u].l+t[u].r>>1;
        if(x<=mid) modify(u<<1,x,v);
        else
        modify(u<<1|1,x,v);
        pushup(u); 
     }
 }

int main()
{

    scanf("%d%d",&n,&m);
    build(1,1,n);
    int t=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        modify(1,t+1,a[i]);
        t++;
    }
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",query(1,a,b));
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla