week18-22 RMQ

week18参见week16 对修改和查询操作做了平衡；
看了下十佳 都拿暴力过了握草。。。？？？
那我还平衡啥。。。
week19加入了线段树
因为week18的数据量是10^{4,week19到了10}6了。
它是减少了区间数因为RMQ是按照满二叉树遍历嘛
但是我Ｔ了个爽。。。
千万不要用ｃｉｎ啊啊啊！！！

#include<iostream>
#include<cmath>
#include<limits.h>
#include<stdio.h>
using namespace std;
#define MAXN 1000009
#define rson m+1,r,rt<<1|1
#define lson l,m,rt<<1
int w[MAXN],ans[4*MAXN];
void pushup(int rt)
{
    ans[rt]=min(ans[rt<<1],ans[rt<<1|1]);//取最小值
}
void build(int l,int r,int rt=1)
{
    if(l==r)
    {
        ans[rt]=w[l];
        return ;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);//用子节点计算父节点
}
int query(int L,int R,int l,int r,int rt=1)
{
    if(L<=l&&r<=R) return ans[rt];//如果查询区间与当前区间相同
    int m=(l+r)>>1,ret=INT_MAX;//分解询问区间
    if(L<=m) ret=min(query(L,R,lson),ret);
    if(m<R) ret=min(query(L,R,rson),ret);
    return ret;
}
void update(int L,int c,int l,int r,int rt=1)//最值的update
{
    if(L==l&&l==r)//到达更新位置
    {
        ans[rt]=c;
        return ;
    }//返回后再更新父节点
    int m=(l+r)>>1;
    if(L<=m) update(L,c,lson);
    else update(L,c,rson);
    pushup(rt);
}
int main()
{
    int i,n,m,op,x,y;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&w[i]);
    scanf("%d",&m);
    build(1,n);
    while(m--)
    {
        scanf("%d%d%d",&op,&x,&y);
        if(op==0) printf("%d\n",query(x,y,1,n));
        else update(x,y,1,n);
    }
    return 0;
}

week20线段树区间修改-加入懒惰
思路同上题。但是呢举个栗子 区间分解下来之后加lazy tag
查询时如果遭遇lazy tag再继续修改
然后这题数据太小暴力也能过就不看了
week21区间离散化预处理
我先去上课了回来就敲
week22回顾week20，解决懒惰标记的互相覆盖

Paste_Image.png

今天能把21和22敲出来就很感人了