題目鏈接：影魔

　　這道題就是去年序列的弱化版啊……

　　我們枚舉最大值的位置\(i\)，找出左邊第一個(gè)比\(a_i\)大的位置\(l\)，右邊第一個(gè)比\(a_i\)大的位置\(r\)，然后我們分開考慮一下\(p_1\)和\(p_2\)的貢獻(xiàn)。

　　首先由于\(a_i\)為最大值，那么左端點(diǎn)不會小于\(l\)，右端點(diǎn)不會大于\(r\)。

　　容易發(fā)現(xiàn)只有左端點(diǎn)為\(l\)，右端點(diǎn)為\(r\)才會產(chǎn)生\(p_1\)的貢獻(xiàn)。

　　然后產(chǎn)生\(p_2\)貢獻(xiàn)的有兩種：一種是左端點(diǎn)為\(l\)，右端點(diǎn)在區(qū)間\((i,r)\)中；另一種是左端點(diǎn)區(qū)間\((l,i)\)中，右端點(diǎn)為\(r\)。

　　還有一種情況需要考慮，就是左端點(diǎn)和右端點(diǎn)差為\(1\)，會產(chǎn)生\(p_1\)的貢獻(xiàn)。對每個(gè)詢問直接計(jì)算就可以了。

　　所以這個(gè)問題可以抽象到二維平面上。有一些點(diǎn)和一些線段都有權(quán)值，每次詢問某個(gè)矩形內(nèi)部的權(quán)值和。

　　于是離線排序+掃描線+樹狀數(shù)組即可。

　　下面貼代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) #define maxn 200010using namespace std; typedef long long llg;struct data{int l,r,x,b,z;data(int A=0,int B=0,int C=0,int D=0,int E=0):l(A),r(B),x(C),b(D),z(E){}bool operator < (const data &h)const{return x<h.x;} }s1[maxn<<1],s2[maxn*3]; int n,m,p1,p2,S[maxn],top,ls; int a[maxn],le[maxn],ri[maxn]; llg ans[maxn],c1[maxn],c2[maxn];int getint(){int w=0;bool q=0;char c=getchar();while((c>'9'||c<'0')&&c!='-') c=getchar();if(c=='-') c=getchar(),q=1;while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();return q?-w:w; }void add(int x,int y){for(int i=x;i<=n;i+=i&(-i)) c1[i]+=y,c2[i]+=1ll*x*y;} llg sum(int x){llg t=0;for(int i=x;i;i-=i&(-i)) t+=(x+1)*c1[i]-c2[i];return t; }int main(){File("sf");scanf("%d %d %d %d",&n,&m,&p1,&p2);a[0]=a[n+1]=n+1; S[top=1]=0;for(int i=1;i<=n+1;i++){if(i<=n) a[i]=getint();while(a[S[top]]<a[i]) ri[S[top--]]=i;le[i]=S[top]; S[++top]=i;}for(int i=1,l,r;i<=m;i++){l=getint(),r=getint(); ans[i]+=(r-l)*p1;s1[i]=data(l,r,l-1,i,-1);s1[i+m]=data(l,r,r,i,1);}sort(s1+1,s1+m*2+1);for(int i=1;i<=n;i++){if(le[i] && ri[i]<=n) s2[++ls]=data(le[i],le[i],ri[i],0,p1);if(le[i] && ri[i]>i+1) s2[++ls]=data(i+1,ri[i]-1,le[i],0,p2);if(ri[i]<=n && i>le[i]+1) s2[++ls]=data(le[i]+1,i-1,ri[i],0,p2);}sort(s2+1,s2+ls+1); int n1=1,n2=1;while(!s1[n1].x) n1++;for(int i=1;n1<=m*2 && i<=n;i++){while(n2<=ls && s2[n2].x==i){add(s2[n2].r+1,-s2[n2].z);add(s2[n2].l,s2[n2].z),n2++;}while(n1<=m*2 && s1[n1].x==i){ans[s1[n1].b]+=s1[n1].z*(sum(s1[n1].r)-sum(s1[n1].l-1));n1++;}}for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/lcf-2000/p/6789680.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 4826 【HNOI2017】 影魔的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。