P3722 [AH2017/HNOI2017]影魔 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
该如何·思考这一题,一开始发现是蒙蔽的(毫无思路)‘
首先将题意改成人话:如果l~r中l,r是最大值和次大值,那么会有p1的价值
如果l~r中有一个是最大值,那么有p2的贡献
其实这个题有一个很重要的条件就是k为1- n的全排列,意思就是互不相同!!!
也就意味着p1贡献时区间内的次次大值是固定的,p2贡献时,区间内的次大值是固定的
于是我们转换思想,考虑每一个数作为次大值和次次大值的贡献
什么意思呢?
每一个ki都从左边找一个第一个比自己大的值,从右边找一个第一个比自己大的值
那么ki就对L~R就有p1的贡献,而L+1~i-1到R有p2的贡献,L到i+1~R-1有p2的贡献
这个应该很好想吧
但是求出L,R后呢,怎么办?
询问一段区间意思就是区间内的数对区间做出的贡献
那么我们就可以在求这一个区间时,先减去之前的数对后面的贡献,最后再加上这个区间新的贡献和
什么意思呢,有点像天天爱跑步,到某一结点,先记录已经产生的值,算完子树后再一减,就是子树所贡献的值了
大概是这一个思路,然后就需要对区间排序,保持单调性,离线处理,至于区间查询和区间修改,可以选择最为简单的树状数组。
/* 10 5 2 3 7 9 5 1 3 10 6 8 2 4 1 7 1 9 1 3 5 9 1 5 */ //code by SPzos #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<map> #include<cmath> #define int long long #define fo(i,j,k) for(register int i=j;i<=k;++i) #define fd(i,j,k) for(register int i=j;i>=k;--i) #define fh(i,x) for(register int i=head[x];i;i=e[i].nxt) #define fv(i,x) for(register int i=0;i<v[x].size();++i) using namespace std; const int N=1000010; inline int read(){ int ret=0,f=0;char ch=getchar(); while(ch<'0' || ch>'9'){if(ch=='-') f=1;ch=getchar();} while(ch>='0' && ch<='9'){ret=(ret<<1)+(ret<<3)+ch-(1<<4)-(1<<5);ch=getchar();} return f?-ret:ret; } struct node{ int l,r,x,id,v; bool operator < (const node &tt) const{ return x<tt.x; } }s1[N],s2[N]; int n,m,p1,p2,st[N],top,ans[N],k[N],L[N],R[N],tot,c1[N],c2[N]; inline int lowbit(int x){ return x&(-x); } inline void add(int x,int y){ if(x) for(int i=x;i<=n;i+=lowbit(i)) c1[i]+=y,c2[i]+=(x*y); } inline int query(int x){ int sum=0; for(int i=x;i>0;i-=lowbit(i)) sum+=(x+1)*c1[i]-c2[i]; return sum; } signed main(){ n=read();m=read();p1=read();p2=read(); k[0]=k[n+1]=n+1;st[++top]=0; fo(i,1,n) k[i]=read(); fo(i,1,n+1){ while(k[st[top]]<k[i]) R[st[top]]=i,--top; L[i]=st[top];st[++top]=i; } fo(i,1,m){ int x=read(),y=read(); ans[i]+=(y-x)*p1; s1[i]=node{x,y,x-1,i,-1}; s1[i+m]=node{x,y,y,i,1}; } sort(s1+1,s1+1+m*2); fo(i,1,n){ if(L[i]>=1 && R[i]<=n) s2[++tot]=node{L[i],L[i],R[i],0,p1}; if(L[i]>=1 && R[i]-1>i) s2[++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(s2+1,s2+1+tot);int n1=1,n2=1; while(!s1[n1].x) n1++; for(int i=1;n1<=m*2 && 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<=2*m && s1[n1].x==i){ ans[s1[n1].id]+=s1[n1].v*(query(s1[n1].r)-query(s1[n1].l-1)); ++n1; } } fo(i,1,m) printf("%lld\n",ans[i]); return 0; }