首页 > 代码库 > bzoj4826 [Hnoi2017]影魔
bzoj4826 [Hnoi2017]影魔
Description
影魔,奈文摩尔,据说有着一个诗人的灵魂。事实上,他吞噬的诗人灵魂早已成千上万。千百年来,他收集了各式各样的灵魂,包括诗人、牧师、帝王、乞丐、奴隶、罪人,当然,还有英雄。每一个灵魂,都有着自己的战斗力,而影魔,靠这些战斗力提升自己的攻击。奈文摩尔有 n 个灵魂,他们在影魔宽广的体内可以排成一排,从左至右标号 1 到 n。第 i个灵魂的战斗力为 k[i],灵魂们以点对的形式为影魔提供攻击力,对于灵魂对 i,j(i<j)来说,若不存在 k[s](i<s<j)大于 k[i]或者 k[j],则会为影魔提供 p1 的攻击力(可理解为:当 j=i+1 时,因为不存在满足 i<s<j 的 s,从而 k[s]不存在,这时提供 p1 的攻击力;当 j>i+1 时,若max{k[s]|i<s<j}<=min{k[i],k[j]} , 则 提 供 p1 的 攻 击 力 ); 另 一 种 情 况 , 令 c 为k[i+1],k[i+2],k[i+3]......k[j-1]的最大值,若 c 满足:k[i]<c<k[j],或者 k[j]<c<k[i],则会为影魔提供 p2 的攻击力,当这样的 c 不存在时,自然不会提供这 p2 的攻击力;其他情况的点对,均不会为影魔提供攻击力。影魔的挚友噬魂鬼在一天造访影魔体内时被这些灵魂吸引住了,他想知道,对于任意一段区间[a,b],1<=a<b<=n,位于这些区间中的灵魂对会为影魔提供多少攻击力,即考虑 所有满足a<=i<j<=b 的灵魂对 i,j 提供的攻击力之和。顺带一提,灵魂的战斗力组成一个 1 到 n 的排列:k[1],k[2],...,k[n]。
Input
第一行 n,m,p1,p2
第二行 n 个数:k[1],k[2],...,k[n]
接下来 m 行,每行两个数 a,b,表示询问区间[a,b]中的灵魂对会为影魔提供多少攻击力。
1 <= n,m <= 200000;1 <= p1,p2 <= 1000
Output
共输出 m 行,每行一个答案,依次对应 m 个询问。
Sample Input
10 5 2 3
7 9 5 1 3 10 6 8 2 4
1 7
1 9
1 3
5 9
1 5
7 9 5 1 3 10 6 8 2 4
1 7
1 9
1 3
5 9
1 5
Sample Output
30
39
4
13
16
39
4
13
16
正解：主席树+单调栈。
考虑每个点为最大值时能产生的贡献。
设当前点为$p$，左边比$p$大的第一个点为$x$，右边比$p$大的第一个点为$y$，$x$和$y$可以用单调栈求出。
那么只有$(x,y)$能产生$p1$的贡献，$(x,[p+1,y-1])$和$(y,[x+1,p-1])$能产生$p2$的贡献，这可以看成很多点对。
为了方便，我们把$p1$产生贡献的点对分成$(x,y)$和$(y,x)$，$p2*2$。
于是我们找出所有这些点对，把这些点对按照横坐标排序。
然后从前往后建主席树，区间修改+标记永久化即可。
查询的时候直接查询对应区间，即$[a,b]$线段树中的$[a,b]$之和，直接除以$2$，然后再加上$(b-a)*p1$。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <complex> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cstdio> 8 #include <vector> 9 #include <cmath>10 #include <queue>11 #include <stack>12 #include <map>13 #include <set>14 #define inf (1<<30)15 #define N (300010)16 #define il inline17 #define RG register18 #define ll long long19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)20 21 using namespace std;22 23 struct data{ ll c,p,l,r; }q[4*N];24 25 ll sum[40*N],lazy[40*N],ls[40*N],rs[40*N],rt[N],sz;26 ll lst[N],nxt[N],st[N],k[N],n,m,p1,p2,x,cnt,top;27 28 il ll gi(){29 RG ll x=0,q=1; RG char ch=getchar();30 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();31 if (ch==‘-‘) q=-1,ch=getchar();32 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();33 return q*x;34 }35 36 il ll cmp(const data &a,const data &b){ return a.p<b.p; }37 38 il void update(RG ll x,RG ll &y,RG ll l,RG ll r,RG ll xl,RG ll xr,RG ll v){39 lazy[y=++sz]=lazy[x],ls[y]=ls[x],rs[y]=rs[x];40 if (xl<=l && r<=xr){ sum[y]=sum[x]+(r-l+1)*v,lazy[y]+=v; return; }41 RG ll mid=(l+r)>>1;42 if (xr<=mid) update(ls[x],ls[y],l,mid,xl,xr,v);43 else if (xl>mid) update(rs[x],rs[y],mid+1,r,xl,xr,v);44 else update(ls[x],ls[y],l,mid,xl,mid,v),update(rs[x],rs[y],mid+1,r,mid+1,xr,v);45 sum[y]=sum[ls[y]]+sum[rs[y]]+(r-l+1)*lazy[y]; return;46 }47 48 il ll query(RG ll x,RG ll y,RG ll l,RG ll r,RG ll xl,RG ll xr,RG ll la){49 if (xl<=l && r<=xr) return sum[y]-sum[x]+(r-l+1)*la;50 RG ll mid=(l+r)>>1; la+=lazy[y]-lazy[x];51 if (xr<=mid) return query(ls[x],ls[y],l,mid,xl,xr,la);52 else if (xl>mid) return query(rs[x],rs[y],mid+1,r,xl,xr,la);53 else return query(ls[x],ls[y],l,mid,xl,mid,la)+query(rs[x],rs[y],mid+1,r,mid+1,xr,la);54 }55 56 il void work(){57 n=gi(),m=gi(),p1=gi(),p2=gi();58 for (RG ll i=1;i<=n;++i){59 k[i]=gi();60 while (top && k[st[top]]<k[i]) nxt[st[top--]]=i;61 lst[i]=st[top],st[++top]=i;62 }63 while (top) nxt[st[top--]]=n+1;64 for (RG ll i=1;i<=n;++i){65 if (lst[i] && nxt[i]<=n){66 q[++cnt]=(data){1,lst[i],nxt[i],nxt[i]};67 q[++cnt]=(data){1,nxt[i],lst[i],lst[i]};68 }69 if (lst[i] && nxt[i]-i>1)70 q[++cnt]=(data){2,lst[i],i+1,nxt[i]-1};71 if (nxt[i]<=n && i-lst[i]>1)72 q[++cnt]=(data){2,nxt[i],lst[i]+1,i-1};73 }74 sort(q+1,q+cnt+1,cmp);75 for (RG ll i=1;i<=cnt;++i){76 while (x<q[i].p) rt[x+1]=rt[x],++x;77 update(rt[x],rt[x],1,n,q[i].l,q[i].r,(q[i].c==1 ? p1 : 2*p2));78 }79 while (x<n) rt[x+1]=rt[x],++x;80 for (RG ll i=1;i<=m;++i){81 RG ll a=gi(),b=gi();82 printf("%lld\n",query(rt[a-1],rt[b],1,n,a,b,0)/2+(b-a)*p1);83 }84 return;85 }86 87 int main(){88 File("sf");89 work();90 return 0;91 }
bzoj4826 [Hnoi2017]影魔
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。