[CC-STREETTA]The Street
题目大意:
给定两个长度为\(n(n\le10^9)\)的数列\(A\)和\(B\),开始数列\(A\)中每一项值为\(-\infty\),数列\(B\)中每一项值为\(0\)。\(m(m\le3\times10^5)\)次操作,操作包含以下\(3\)种:
- 数列\(A\)区间加一条等差数列。
- 数列\(B\)区间对一个等差数列取\(\max\)。
- 询问\(A_i+B_i\)。
思路:
每个结点维护一个解析式\(kx+b\)。
对于数列\(A\),使用李超树维护最大值。
对于数列\(B\),直接合并两个解析式。
时间复杂度\(\mathcal O(m\log n)\)。
源代码:
#include<cstdio>
#include<cctype>
#include<climits>
#include<algorithm>
inline int getint() {
register char ch;
register bool neg=false;
while(!isdigit(ch=getchar())) neg|=ch=='-';
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return neg?-x:x;
}
typedef long long int64;
const int SIZE=9e6;
struct Node {
int64 a,b;
void operator += (const Node &rhs) {
a+=rhs.a;
b+=rhs.b;
}
};
int64 calc(const Node &s,const int &x) {
return s.a*x+s.b;
}
class SegmentTree1 {
#define mid ((b+e)>>1)
private:
Node node[SIZE];
int left[SIZE],right[SIZE];
int sz,new_node() {
node[++sz]=(Node){0,LLONG_MIN};
return sz;
}
public:
int root;
void modify(int &p,const int &b,const int &e,const int &l,const int &r,Node s) {
p=p?:new_node();
if(b==l&&e==r) {
if(calc(node[p],b)<calc(s,b)) std::swap(node[p],s);
if(calc(node[p],e)>=calc(s,e)) return;
const double c=1.*(s.b-node[p].b)/(node[p].a-s.a);
if(c<=mid) {
modify(left[p],b,mid,b,mid,node[p]);
node[p]=s;
}
if(c>mid) modify(right[p],mid+1,e,mid+1,e,s);
return;
}
if(l<=mid) modify(left[p],b,mid,l,std::min(mid,r),s);
if(r>mid) modify(right[p],mid+1,e,std::max(mid+1,l),r,s);
}
int64 query(int &p,const int &b,const int &e,const int &x) {
p=p?:new_node();
int64 ret=calc(node[p],x);
if(b==e) return ret;
if(x<=mid) ret=std::max(ret,query(left[p],b,mid,x));
if(x>mid) ret=std::max(ret,query(right[p],mid+1,e,x));
return ret;
}
#undef mid
};
SegmentTree1 t1;
class SegmentTree2 {
#define mid ((b+e)>>1)
private:
Node node[SIZE];
int left[SIZE],right[SIZE];
int sz,new_node() {
return ++sz;
}
public:
int root;
void modify(int &p,const int &b,const int &e,const int &l,const int &r,const Node &s) {
p=p?:new_node();
if(b==l&&e==r) {
node[p]+=s;
return;
}
if(l<=mid) modify(left[p],b,mid,l,std::min(mid,r),s);
if(r>mid) modify(right[p],mid+1,e,std::max(mid+1,l),r,s);
}
int64 query(int &p,const int &b,const int &e,const int &x) {
p=p?:new_node();
int64 ret=calc(node[p],x);
if(b==e) return ret;
if(x<=mid) ret+=query(left[p],b,mid,x);
if(x>mid) ret+=query(right[p],mid+1,e,x);
return ret;
}
#undef mid
};
SegmentTree2 t2;
int main() {
const int n=getint(),m=getint();
for(register int i=0;i<m;i++) {
const int opt=getint();
if(opt==1) {
const int u=getint(),v=getint(),a=getint(),b=getint();
t1.modify(t1.root,1,n,u,v,(Node){a,b-(int64)u*a});
}
if(opt==2) {
const int u=getint(),v=getint(),a=getint(),b=getint();
t2.modify(t2.root,1,n,u,v,(Node){a,b-(int64)u*a});
}
if(opt==3) {
const int i=getint();
const int64 a=t1.query(t1.root,1,n,i),b=t2.query(t2.root,1,n,i);
if(a==LLONG_MIN) {
puts("NA");
} else {
printf("%lld\n",a+b);
}
}
}
return 0;
}