[AH/HNOI2017]影魔
teafrogsf
2018-04-12 11:00:11
感觉这题还挺有意思的，不过估计是HNOI2017第二容易的题目。
**UPD：原来的解释有点错误，修正一下。**
发现两个限制条件很麻烦，不妨先不考虑右端点元素，找到当前元素$a[i]$的右方后继（可等于$a[i]$）$a[k]$。则从$[i,i+1]$到$[i,k)$这些区间都满足p2的贡献要求，而$[i,k]$则满足p1的贡献要求。而每次询问则要求当前区间所有子区间的答案，于是我们可以用线段树维护区间右端点的贡献，更新时将$(i,k)$加上p2,将$[k,k]$加上$p1$就可以了。查询是可以直接查询$(L+1,R)$的答案的。
但是这样还有些问题，我们可能会算入L左边区间的贡献。所以只需要将询问区间按L从大到小排序就可以了。计算后继可以用单调栈来维护，当然你也可以浪费一点复杂度来$\rm lower\_bound$。
至于左边的区间怎么办？将区间和询问反向就可以了。**注意反向后询问的变化。**
**但我们注意到右端点的值可能对答案有影响：比如$[i,k]$这个区间在反向计算时是增加了p2的无意义贡献的。我们要在这里减掉。$**
还有就是要开$\rm long\ long$。
```cpp
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define neko 200010
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~i))
#define rf(i,a,b) for(register int i=(a);i>=(b);i=~(-i))
struct node
{
int l,r,id;
}q[neko];
int n,m;
typedef long long ll;
ll p1,p2,a[neko],ans[neko],stk[neko],suc[neko],Sum[neko<<2],Add[neko<<2];
using namespace std;
namespace Seg
{
#define ori tagl,tagr
#define mid ((l+r)>>1)
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define pushup(root) Sum[root]=Sum[root<<1]+Sum[root<<1|1]
void pushdown(int root,int l,int r)
{
if(Add[root])
{
Sum[root<<1]+=1ll*(mid-l+1)*Add[root];
Sum[root<<1|1]+=1ll*(r-mid)*Add[root];
Add[root<<1]+=Add[root];
Add[root<<1|1]+=Add[root];
Add[root]=0;
}
}
ll query(int root,int l,int r,int tagl,int tagr)
{
if(l>=tagl&&r<=tagr)return Sum[root];
pushdown(root,l,r);
ll tmp=0;
if(tagl<=mid)tmp+=query(lson,ori);
if(tagr>mid)tmp+=query(rson,ori);
return tmp;
}
void update(int root,int l,int r,int tagl,int tagr,int x)
{
if(l>=tagl&&r<=tagr){Add[root]+=x,Sum[root]+=(r-l+1)*x;return;}
pushdown(root,l,r);
if(tagl<=mid)update(lson,ori,x);
if(tagr>mid)update(rson,ori,x);
pushup(root);
}
#undef ori
#undef mid
#undef lson
#undef rson
}
namespace Cons
{
using namespace Seg;
bool cmp(node a,node b)
{return a.l<b.l;}
void init()
{memset(Sum,0,sizeof(Sum)),memset(Add,0,sizeof(Add));}
void calc()
{
int top=0,now=m;stk[0]=n+1;
init();
rf(i,n,1)
{
while(top&&a[stk[top]]<a[i])--top;
suc[i]=stk[top];
stk[++top]=i;
}
rf(i,n,1)
{
if(suc[i]>i)update(1,1,n+1,i+1,suc[i],p2),update(1,1,n+1,suc[i],suc[i],p1-2*p2);
while(q[now].l==i)ans[q[now].id]+=query(1,1,n+1,i+1,q[now].r),--now;
}
}
}
using namespace Cons;
int main()
{
scanf("%d%d%lld%lld",&n,&m,&p1,&p2);
f(i,1,n)scanf("%lld",&a[i]);//a[n+1]=1e9;
f(i,1,m)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
sort(q+1,q+m+1,cmp),calc();
reverse(a+1,a+n+1);
f(i,1,m)swap(q[i].l,q[i].r),q[i].l=n-q[i].l+1,q[i].r=n-q[i].r+1;
sort(q+1,q+m+1,cmp),calc();
f(i,1,m)printf("%lld\n",ans[i]);return 0;
}
```