洛谷 P3246 [HNOI2016]序列 —— 莫队+dp

This way

题意:

洛谷 P3246 [HNOI2016]序列 —— 莫队+dp

题解:

第一次做到莫队+dp的题目,是我菜了,我还在用5个变量维护每次的增减,,唉
如何从(l,r)推到(l,r+1),我们知道右端点往右移了一格,就是l~r中的最小值,假设它的位置是p1,它增加了(p1-l+1)*a[p1],然后p1~r中的最小值p2,增加了(p2-p1)*a[p2]…依次类推
那么我们用dp[i]表示到了第i个位置的增加的答案,那么

dp[i]=dp[lef[i]]+a[i](ilef[i])dp[i]=dp[lef[i]]+a[i]*(i-lef[i])


然后要查询的话,只需要找到l~r中的最小值的位置p,答案就加上

dp[r]dp[p]+a[p](pl+1)dp[r]-dp[p]+a[p]*(p-l+1)


然后从右往左类似
p[i][j]表示用ST表记录的最小值的位置
Log[i]就是log(i)
lef[i],rig[i]就表示这个点的左右最远到达的地方
pos就是计算莫队的区块的

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=1e5+5; ll a[N]; struct node {     int l,r,id; }q[N]; int pos[N]; ll ans[N]; bool cmp(node x,node y) {     return pos[x.l]<pos[y.l]||pos[x.l]==pos[y.l]&&x.r<y.r; } int p[N][21],st[N],top,lef[N],rig[N]; ll dpl[N],dpr[N]; int Log[N]; int cmp2(int x,int y){return a[x]<=a[y]?x:y;} int query(int l,int r){     int bit=Log[r-l+1];     return cmp2(p[l][bit],p[r-(1<<bit)+1][bit]); } int main() {     int n,m;     scanf("%d%d",&n,&m);     for(int i=1;i<=n;i++)scanf("%lld",&a[i]),p[i][0]=i;     for(int i=2;i<=n;i++)         Log[i]=Log[i>>1]+1;     for(int j=1;(1<<j)<=n;j++)         for(int i=1;i+(1<<j)-1<=n;i++)             p[i][j]=cmp2(p[i][j-1],p[i+(1<<j-1)][j-1]);     for(int i=1;i<=n;i++){         while(top&&a[st[top]]>a[i])             top--;         lef[i]=st[top];         st[++top]=i;     }     st[0]=n+1;     top=0;     for(int i=n;i;i--){         while(top&&a[st[top]]>=a[i])             top--;         rig[i]=st[top];         st[++top]=i;     }     for(int i=1;i<=n;i++)         dpr[i]=dpr[lef[i]]+a[i]*(i-lef[i]);     for(int i=n;i;i--)         dpl[i]=dpl[rig[i]]+a[i]*(rig[i]-i);     int blog=sqrt(n);     for(int i=1;i<=n;i++)         pos[i]=(i-1)/blog+1;     for(int i=1;i<=m;i++)         scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;     sort(q+1,q+1+m,cmp);     int l=q[1].l,r=q[1].l-1;     ll sum=0;     for(int i=1;i<=m;i++){         while(r<q[i].r){             r++;             int pp=query(l,r);             sum+=dpr[r]-dpr[pp]+a[pp]*(pp-l+1);         }         while(l>q[i].l){             l--;             int pp=query(l,r);             sum+=dpl[l]-dpl[pp]+a[pp]*(r-pp+1);         }         while(l<q[i].l){             int pp=query(l,r);             sum-=dpl[l]-dpl[pp]+a[pp]*(r-pp+1);             l++;         }         while(r>q[i].r){             int pp=query(l,r);             sum-=dpr[r]-dpr[pp]+a[pp]*(pp-l+1);             r--;         }         ans[q[i].id]=sum;     }     for(int i=1;i<=m;i++)printf("%lldn",ans[i]);     return 0; } /* 5 4 5 2 4 1 3 1 5 1 3 3 5 2 5 */  

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 洛谷 P3246 [HNOI2016]序列 —— 莫队+dp

提供最优质的资源集合

立即查看 了解详情