谁还能优化？！
2026-07-01 22:11:11
发布于：浙江
A93312.「AHOI / HNOI2017」影魔
#include<cstdio>
#include<algorithm>
#define RG register
#define LL long long
#define MAXN 500010
using namespace std;
struct node{
int l,r,x,id,v;
node(){}
node(int l_,int r_,int x_,int id_,int v_):l(l_),r(r_),x(x_),id(id_),v(v_){}
bool operator <(const node &t)const{return x<t.x;}
}s1[MAXN<<1],s2[MAXN3];
int n,m,p1,p2,k[MAXN],q[MAXN],top,L[MAXN],R[MAXN];
LL ans[MAXN],c1[MAXN],c2[MAXN];
inline int lowbit(int x){return x&-x;}
inline void add(int x,int y){
if(!x)return;
for(RG int i=x;i<=n;i+=lowbit(i))c1[i]+=y,c2[i]+=1LLxy;
}
inline LL sum(int x){
LL res=0;
for(RG int i=x;i;i-=lowbit(i))res+=1LL(x+1)c1[i]-c2[i];
return res;
}
int main(){
RG int x,y,tot=0,n1=1,n2=1;
scanf("%d%d%d%d",&n,&m,&p1,&p2);
k[0]=k[n+1]=n+1;q[++top]=0;
for(RG int i=1;i<=n;++i)scanf("%d",&k[i]);
for(RG int i=1;i<=n+1;++i){
while(k[q[top]]<k[i])R[q[top]]=i,--top;
L[i]=q[top];q[++top]=i;
}
for(RG int i=1;i<=m;++i){
scanf("%d%d",&x,&y);
ans[i]=1LL(y-x)p1;
s1[i]=node(x,y,x-1,i,-1);
s1[i+m]=node(x,y,y,i,1);
}
sort(s11+(m<<1)+1);
for(RG int i=1;i<=n;++i){
if(L[i]>=1&&R[i]<=n)s2[++tot]=node(L[i],L[i],R[i],0,p1);
if(L[i]>=1&&R[i]>i2[++tot]=node(i+1,R[i]-1,L[i],0,p2);
if(L[i]+1<i&&R[i]<=n)s2[++tot]=node(L[i]+1,i-1,R[i],0,p2);
}
sort(s22+tot+1);
while(!s1[n1].x)++n1;
for(RG int i=1;n1<=m2&&i<=n;++i){
while(n2<=tot&&s2[n2].x==i){
add(s2[n2].l,s2[n2].v);
add(s2[n2].r+1,-s2[n2].v);
++n2;
}
while(n1<=m2&&s1[n1].x==i){
ans[s1[n1].id]+=1LLs1[n1].v*(sum(s1[n1].r)-sum(s1[n1].l-1));
++n1;
}
}
for(RG int i=1;i<=m;++i)printf("%lld\n",ans[i]);
return 0;
}
这里空空如也
有帮助，赞一个