[题解]51nod1488帕斯卡小三角

人傻常数大说的就是我…… 单调栈做法这辈子都学不会的 写的线段树维护凸包……合并两个凸包的时候Jarvis步进法暴力 采用归并排序的方式建树是$O(nlogn)$的然后询问两个log常数较小可以通过本题 玩火胡乱用了反向迭代器……调了半年，反向迭代器++=正向迭代器--…… 过段时间填坑，先贴代码 ```C #include<cstdio> #include<algorithm> #include<vector> #define TIL v[p].rbegin()->p #define LTIL (++v[p].rbegin())->p using namespace std;const int N=1e5+10;typedef double db;typedef long long ll; int n;int m;int va[N];int sum[N]; struct poi {int x;int y;friend bool operator <(poi a,poi b){return (a.x==b.x)?a.y>b.y:a.x<b.x;}} a[N],tr[N]; struct data { poi p;db k;data (const poi& a,db va){p=a;k=va;} friend bool operator <(data a,data b){return a.k<b.k;} }; inline db ck(const poi& x,const poi& y){return ((db)x.y-y.y)/((db)x.x-y.x);} struct linetree { vector <data> v[4*N]; inline void build(int p,int l,int r) { if(r-l==1){v[p].push_back(data(a[l],1e11));return;} int mid=(l+r+1)/2;build(p<<1,l,mid);build(p<<1|1,mid,r); merge(a+l,a+mid,a+mid,a+r,tr+l);v[p].push_back(data(tr[l],1e11)); for(int i=l+1;i<r;i++) { if(tr[i].x==tr[i-1].x)continue; if(v[p].size()<=1){v[p].push_back(data(tr[i],ck(TIL,tr[i])));continue;} while(v[p].size()>1&&v[p].rbegin()->k<ck(LTIL,tr[i]))v[p].pop_back(); v[p].push_back(data(tr[i],ck(TIL,tr[i]))); }for(int i=l;i<r;i++)a[i]=tr[i]; } inline ll solve(int p,int l,int r,ll k) { vector <data> :: reverse_iterator it=lower_bound(v[p].rbegin(),v[p].rend(),data((poi){0,0},k)); if(it==v[p].rend())--it;return it->p.y-(ll)it->p.x*k; } inline ll query(int p,int l,int r,int dl,int dr,int k) { if(dl==l&&dr==r){return solve(p,l,r,k);}int mid=(l+r+1)/2;ll res=0; if(dl<mid)res=max(res,query(p<<1,l,mid,dl,min(dr,mid),k)); if(mid<dr)res=max(res,query(p<<1|1,mid,r,max(dl,mid),dr,k));return res; } }lt; int main() { scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&va[i]); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+va[i]; for(int i=1;i<=n;i++)a[i]=(poi){va[i],sum[i]-va[i]*i}; lt.build(1,1,n+1);scanf("%d",&m); for(int i=1,x,y;i<=m;i++) { scanf("%d%d",&x,&y); ll nans=sum[y]-lt.query(1,1,n+1,max(y-x+1,1),y+1,x-y); printf("%lld\n",nans); }return 0; } ```