P3722 [AHOI2017/HNOI2017]影魔

题意：给出一个$1$到$n$的排列$a$，对于一对$i,j(1<=i<j<=n)$， 若对于任意$i<k<j$，都有$a[k]<min(a[i],a[j])$，那么价值为$p1$ 令$c=max\left\{a_k,k∈(i,j)\right\}$，若$min(a_i,a_j)<c<max(a_i,a_j)$，那么价值为$p2$ 多组询问所有满足$l<=i<j<=r$的$(i,j)$的价值之和 ------------ **树状数组（线段树）** **离线处理** 首先预处理出$i$左边右边**第一个大于$a_i$的位置** 分别记为$L_i,R_i$ 这个可以用**单调栈**实现 那么可以发现$i$的贡献： - 对于左端点在$L_i$，右端点在$R_i$的区间，有$p1$的贡献 - 对于左端点在$[L_i+1,i-1]$，右端点在$R_i$的区间，有$p2$的贡献 - 对于左端点在$L_i$，右端点在$[i+1,R_i-1]$的区间，有$p2$的贡献 把询问排好序，$i$从$1$到$n$扫 - 扫到$L_i$时，统计区间$[i+1,R_i-1]$的贡献 - 扫到$R_i$时，统计$L_i$和区间$[L_i+1,i-1]$的贡献 处理询问的时候用双指针，边修改边统计 对于一个询问的区间$[l,r]$，在扫到$l-1$时记录这个区间的贡献$sum1$，扫到$r$时记录这个区间的贡献$sum2$，那么答案就是$sum2-sum1$了 ``` #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; typedef long long ll; const int N=2e5+5; struct Q { int l,r,x,id,val; inline friend bool operator < (Q a,Q b) {return a.x<b.x;} }q[N<<1],p[N*3]; int n,m,p1,p2,cnt,a[N],stack[N],top,L[N],R[N]; ll c1[N],c2[N],ans[N]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline int lowbit(int x){return x&(-x);} inline void add(int x,ll k){for (reg int i=x;i<=n;i+=lowbit(i)) c1[i]+=k,c2[i]+=(ll)x*k;} inline ll query(int x,ll res=0){for (reg int i=x;i;i-=lowbit(i)) res+=(ll)(x+1)*c1[i]-c2[i]; return res;} int main() { n=read(),m=read(),p1=read(),p2=read(); for (reg int i=1;i<=n;a[i++]=read()); a[0]=a[n+1]=n+1; stack[++top]=0; for (reg int i=1;i<=n+1;i++) { while (top&&a[stack[top]]<a[i]) R[stack[top--]]=i; L[i]=stack[top]; stack[++top]=i; } for (reg int i=1;i<=m;i++) { int l=read(),r=read(); ans[i]=1ll*p1*(r-l); q[i]=(Q){l,r,l-1,i,-1}; q[i+m]=(Q){l,r,r,i,1}; } sort(q+1,q+2*m+1); for (reg int i=1;i<=n;i++) { if (L[i]&&R[i]<=n) p[++cnt]=(Q){L[i],L[i],R[i],cnt,p1}; if (L[i]<i-1&&R[i]<=n) p[++cnt]=(Q){L[i]+1,i-1,R[i],cnt,p2}; if (L[i]&&R[i]>i+1) p[++cnt]=(Q){i+1,R[i]-1,L[i],cnt,p2}; } sort(p+1,p+cnt+1); int now1=1,now2=1; while (!q[now1].x) ++now1; m<<=1; for (reg int i=1;i<=n,now1<=m;i++) { while (now2<=cnt&&p[now2].x==i) { add(p[now2].l,p[now2].val); add(p[now2].r+1,-p[now2].val); ++now2; } while (now1<=m&&q[now1].x==i) { ans[q[now1].id]+=q[now1].val*(query(q[now1].r)-query(q[now1].l-1)); ++now1; } } for (reg int i=1;i<=(m>>1);i++) printf("%lld\n",ans[i]); return 0; } ```