建站系统下载 discuz/热点事件

先用单调栈找出比$i$大的第一个数$l_i$ 和 $r_i$
然后$[i,i+1]$有p1的贡献 $[l_i,r_i]$有p1的贡献
$[l_i,x] \ x\in [i+1,r_i-1]$ 有p2的贡献
$[x,r_i] \ x\in [l_i+1,i-1]$ 有p2的贡献
放在平面上就是点和线段 矩形求和 扫描线

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;inline char nc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){char c=nc(),b=1;for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}const int N=200005;int n,a[N];namespace BIT{int maxn; ll c1[N],c2[N];inline void init(int n){maxn=n; for (int i=1;i<=n;i++) c1[i]=c2[i]=0;}inline void add(int x,int r){for (int i=x;i<=maxn;i+=i&-i)c1[i]+=r,c2[i]+=(ll)x*r;}inline void add(int l,int r,int t){add(l,t); add(r+1,-t);}inline ll sum(int x){ll ret1=0,ret2=0;for (int i=x;i;i-=i&-i)ret1+=c1[i],ret2+=c2[i];return ret1*(x+1)-ret2;}inline ll sum(int l,int r){return sum(r)-sum(l-1);}
}struct event{int f,x,y1,y2,z;event(int f=0,int x=0,int y1=0,int y2=0,int z=0):f(f),x(x),y1(y1),y2(y2),z(z) { }bool operator < (const event &B) const{return x==B.x?f<B.f:x<B.x;}
}ev[N<<3];
int tot;int p1,p2;
int sta[N],pnt;
int l[N],r[N];int Q,_l[N],_r[N];
ll ans[N];int main(){freopen("t.in","r",stdin);freopen("t.out","w",stdout);read(n); read(Q); read(p1); read(p2);for (int i=1;i<=n;i++) read(a[i]);for (int i=1;i<=Q;i++) read(_l[i]),read(_r[i]);pnt=0;for (int i=1;i<=n;i++){while (pnt && a[sta[pnt]]<a[i]) pnt--;l[i]=sta[pnt]; sta[++pnt]=i;}pnt=0;for (int i=n;i;i--){while (pnt && a[sta[pnt]]<a[i]) pnt--;r[i]=sta[pnt]; sta[++pnt]=i;}for (int i=1;i<=n;i++) if (!r[i]) r[i]=n+1;tot=0;for (int i=1;i<n;i++)ev[++tot]=event(1,i,i+1,i+1,p1);for (int i=1;i<=n;i++){if (l[i]!=0 && r[i]!=n+1)ev[++tot]=event(1,l[i],r[i],r[i],p1);if (l[i]!=0)if (i+1<=r[i]-1)ev[++tot]=event(1,l[i],i+1,r[i]-1,p2);}for (int i=1;i<=Q;i++)ev[++tot]=event(2,_l[i]-1,_l[i],_r[i],i),ev[++tot]=event(3,_r[i],_l[i],_r[i],i);BIT::init(n);sort(ev+1,ev+tot+1);for (int i=1;i<=tot;i++)if (ev[i].f==1)BIT::add(ev[i].y1,ev[i].y2,ev[i].z);else if (ev[i].f==2)ans[ev[i].z]-=BIT::sum(ev[i].y1,ev[i].y2);elseans[ev[i].z]+=BIT::sum(ev[i].y1,ev[i].y2);tot=0;for (int i=1;i<=n;i++)if (r[i]!=n+1)if (l[i]+1<=i-1)ev[++tot]=event(1,r[i],l[i]+1,i-1,p2);for (int i=1;i<=Q;i++)ev[++tot]=event(2,_l[i]-1,_l[i],_r[i],i),ev[++tot]=event(3,_r[i],_l[i],_r[i],i);BIT::init(n);sort(ev+1,ev+tot+1);for (int i=1;i<=tot;i++)if (ev[i].f==1)BIT::add(ev[i].y1,ev[i].y2,ev[i].z);else if (ev[i].f==2)ans[ev[i].z]-=BIT::sum(ev[i].y1,ev[i].y2);elseans[ev[i].z]+=BIT::sum(ev[i].y1,ev[i].y2);for (int i=1;i<=Q;i++)printf("%lld\n",ans[i]);return 0;
}