砍树(2)
小A是小B家的园丁。小B的家里有n棵树，第i棵树的横坐标为i。一天，小B交给小A一个任务，让他降低自己家中的某些树木的高度。这个任务对小A来说十分简单，因为他有一把极其锋利的斧头和一门独门砍树秘籍，能够轻易地砍断任何参天大树。小A的砍树方法有3种，都是沿着一条y=kx+b的直线砍一段区间的树，相同的方法k值相同。只用了一个下午，小A就完成了小B的任务。第二天，小B来视察小A的任务完成情况。小B想知道小A是否真的用心砍树，于是提出了q个询问，每次询问一段区间中最低的树的高度。小A当然是不会记住树木的砍伐情况的，他只知道自己按什么顺序，使用了什么方法，砍了哪个连续区间的树，而且区间都是互不包含的。现在小A想请你帮帮他，回答小B的询问。
输入格式：
第一行三个整数k1，k2，k3表示小A三种砍树方法的斜率值；
第二行一个数n，表示一共有n棵树；
第三行n个数hi，分别表示n棵树的高度；
第四行一个数m，表示小A一共进行了m次操作；
接下来m行，每行四个数L，R，p，b，表示用第p种方法，即用y=kp+b的直线砍[L，R]区间的树；
接下来一行一个数q，表示小B的询问数；
接下来q行，每行两个数L，R，表示询问[L，R]区间中最低的树的高度。
输出格式：
一共q行，每行一个数h表示对应的回答。
样例输入：
1 0 -1
4
10 30 20 1
2
3 4 2 5
1 3 3 10
2
1 2
2 3
样例输出：
８
５
数据范围：
n<=1000000,m<=500000
时间限制：
3s
空间限制：
64M
提示：
如下图，红色即为树的剩余部分。
本题是考代码能力的线段树，砍树和区间求最值都要求用logn维护
lazy标记略难，用三个数组表示三个kx+b的常数的最小值，这样到查询之前统一处理就可以根据以下性质进行推导，先递归他的儿子再取两个儿子中的小，边界是仅一个，此时根据上面传下来的函数计算即可。
区间求最小仅是传懒标记比较特殊，其他也没什么。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using
namespace
std;
#define PER(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
int
k[3];
int
val[2100005];
int
b[2100005][3];
int
h[1100005];
int
l[2100005];
int
r[2100005];
int
n,m,q;
int
lb,rb,p,bb;
const
int
INF=100000000;
//建树操作
int
build(
int
ll,
int
rr,
int
no)
{
int
mid=(ll+rr)>>1;l[no]=ll;r[no]=rr;
b[no][0]=b[no][1]=b[no][2]=INF;//0、1、2是三种type
if
(ll==rr){
return
val[no]=h[ll];}
int
lc=no<<1,rc=lc+1;
return
val[no]=min(build(ll,mid,lc),build(mid+1,rr,rc));
}
void
add(
int
no,
int
x,
int
y,
int
p,
int
bb)
{
if
(l[no]==x&&r[no]==y){b[no][p]=min(b[no][p],bb);
return
;}//添加时记录懒标记
int
mid=(l[no]+r[no]) >> 1,lc=no*2,rc=lc+1;
if
(x>mid) {add(rc,x,y,p,bb);
return
;}
if
(y<=mid) {add(lc,x,y,p,bb);
return
;}
add(lc,x,mid,p,bb);add(rc,mid+1,y,p,bb);
return
;
}
void
dfs(
int
no)
{
int
lc=no*2,rc=lc+1;
if
(l[no]!=r[no])
{
PER(i,0,2){
int
wa=b[no][i];
b[lc][i]=min(b[lc][i],wa);
b[rc][i]=min(b[rc][i],wa);
}
dfs(lc);dfs(rc);
val[no]=min(val[lc],val[no]);
val[no]=min(val[rc],val[no]);
}
else
{
PER(i,0,2)
{
int
wa=b[no][i];
if
(wa!=INF)
//错误瓶颈判断该函数是否存在，数据结果可能很大，要么把INF设得很大
val[no]=min(val[no],k[i]*r[no]+wa);
}
}
}
int
doit(
int
no,
int
x,
int
y)//区间查询，线段树版
{
if
(l[no]==x&&r[no]==y)
return
val[no];
int
mid=(l[no]+r[no])>>1;
int
lc=no*2,rc=lc+1;
if
(y<=mid)
return
doit(lc,x,y);
if
(x>mid)
return
doit(rc,x,y);
return
min(doit(lc,x,mid),doit(rc,mid+1,y));
}
int
main()
{
scanf
(
"%d%d%d"
,&k[0],&k[1],&k[2]);
scanf
(
"%d"
,&n);
PER(i,1,n)
scanf
(
"%d"
,&h[i]);
build(1,n,1);
scanf
(
"%d"
,&m);
while
(m--)
{
scanf
(
"%d%d%d%d"
,&lb,&rb,&p,&bb);
add(1,lb,rb,p-1,bb);
}
scanf
(
"%d"
,&q);
dfs(1);
while
(q--)
{
scanf
(
"%d%d"
,&lb,&rb);
printf
(
"%d\n"
,doit(1,lb,rb));
}
}
