week18参见week16 对修改和查询操作做了平衡；
看了下十佳 都拿暴力过了握草。。。？？？
那我还平衡啥。。。
week19加入了线段树
因为week18的数据量是104,week19到了106了。
它是减少了区间数因为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敲出来就很感人了
