思路：
动态开节点线段树；
等差序列求和于取大，是两个独立的子问题；
所以，建两颗线段树分开维护；
求和：等差数列的首项和公差直接相加即可；
取大：
对于线段树每个节点储存一条斜率为等差数列公差的线段；
当添加线段到已有线段的节点，下传一条线段，当前节点留下一条线段；
当要添加的线段完全覆盖或者被覆盖当前节点储存的线段时，选择更新或者不更新；
单点查询时，从根节点到叶节点的路径上去最大值；
来，上代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define ll long long
#define INF (1LL<<62) struct TreeNodeType {
ll a,b; bool if_; struct TreeNodeType *lc,*rc; TreeNodeType()
{
lc=NULL,rc=NULL,if_=false,a=,b=;
}
}; ll n,m; inline void in(ll &now)
{
ll if_z=;now=;
char Cget=getchar();
while(Cget>''||Cget<'')
{
if(Cget=='-') if_z=-;
Cget=getchar();
}
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
now*=if_z;
} class SumTreeType {
public:
struct TreeNodeType *root; SumTreeType(){} inline void tree_down(TreeNodeType *&now,ll l,ll r)
{
if(now->lc==NULL) now->lc=new TreeNodeType;
if(now->rc==NULL) now->rc=new TreeNodeType;
now->lc->a+=now->a,now->lc->b+=now->b;
now->rc->a+=now->a+((l+r>>)-l+)*now->b,now->rc->b+=now->b;
now->a=,now->b=;
} void tree_add(TreeNodeType *&now,ll l,ll r,ll li,ll ri,ll a,ll b)
{
if(now==NULL) now=new TreeNodeType;
if(l==li&&r==ri)
{
now->a+=a,now->b+=b;
return ;
}
ll mid=l+r>>;
if(now->a!=&&now->b!=) tree_down(now,l,r);
if(li>mid) tree_add(now->rc,mid+,r,li,ri,a,b);
else if(ri<=mid) tree_add(now->lc,l,mid,li,ri,a,b);
else
{
tree_add(now->lc,l,mid,li,mid,a,b);
tree_add(now->rc,mid+,r,mid+,ri,a+(mid-li+)*b,b);
}
} ll tree_query(TreeNodeType *&now,ll l,ll r,ll to)
{
if(now==NULL) return ;
if(l==r) return now->a;
if(now->a!=||now->b!=) tree_down(now,l,r);
ll mid=l+r>>;
if(to<=mid) return tree_query(now->lc,l,mid,to);
else return tree_query(now->rc,mid+,r,to);
}
};
class SumTreeType ai; class MaxTreeType {
public:
ll X; bool op; struct TreeNodeType *root; MaxTreeType(){} inline double com(ll a1,ll b1,ll a2,ll b2)
{
if(a1==a2) return ;
return (double)(a1-a2)/(double)(b2-b1);
} void tree_down(TreeNodeType *&now,ll l,ll r,ll a,ll b)
{
if(now==NULL)
{
now=new TreeNodeType;
now->if_=true;
now->a=a,now->b=b;
return ;
}
if(!now->if_)
{
now->a=a,now->b=b,now->if_=true;
return ;
}
double xx=com(now->a-l*now->b,now->b,a-l*b,b),mid=l+r>>;
if(xx<=l||xx>=r)
{
if((mid-l)*b+a>(mid-l)*now->b+now->a) now->a=a,now->b=b;
return ;
}
if(xx<=mid)
{
if(now->b<b)
{
tree_down(now->lc,l,mid,now->a,now->b);
now->a=a,now->b=b,now->if_=true;
}
else tree_down(now->lc,l,mid,a,b);
}
else
{
if(now->b<b) tree_down(now->rc,mid+,r,a+(mid-l+)*b,b);
else
{
tree_down(now->rc,mid+,r,now->a+(mid-l+)*now->b,now->b);
now->a=a,now->b=b,now->if_=true;
}
}
} void tree_add(TreeNodeType *&now,ll l,ll r,ll li,ll ri,ll a,ll b)
{
if(now==NULL) now=new TreeNodeType;
if(l==li&&r==ri)
{
if(!now->if_)
{
now->if_=true;
now->a=a,now->b=b;
}
else tree_down(now,l,r,a,b);
return ;
}
ll mid=l+r>>;
if(ri<=mid) tree_add(now->lc,l,mid,li,ri,a,b);
else if(li>mid) tree_add(now->rc,mid+,r,li,ri,a,b);
else
{
tree_add(now->lc,l,mid,li,mid,a,b);
tree_add(now->rc,mid+,r,mid+,ri,a+(mid-li+)*b,b);
}
} void tree_query(TreeNodeType *&now,ll l,ll r,ll to)
{
if(now==NULL) return ;
if(now->if_) X=max(X,now->a+(to-l)*now->b);
if(l==r) return ;
ll mid=l+r>>;
if(to<=mid) tree_query(now->lc,l,mid,to);
else tree_query(now->rc,mid+,r,to);
}
};
class MaxTreeType bi; int main()
{
in(n),in(m);ll op,u,v,a,b;
for(ll i=;i<=m;i++)
{
in(op);
if(op==)
{
in(u),in(v),in(b),in(a);
bi.tree_add(bi.root,,n,u,v,a,b);
}
else if(op==)
{
in(u),in(v),in(b),in(a);
ai.tree_add(ai.root,,n,u,v,a,b);
}
else if(op==)
{
in(u);
bi.X=-INF;
bi.tree_query(bi.root,,n,u);
if(bi.X==-INF) printf("NA\n");
else printf("%lld\n",bi.X+ai.tree_query(ai.root,,n,u));
}
}
return ;
}