首页 > 代码库 > Bzoj4826 [Hnoi2017]影魔
Bzoj4826 [Hnoi2017]影魔
Submit: 425 Solved: 244
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
HINT
Source
扫描线 主席树
这题好难啊，对着数据和题解肝了两天多才肝出来，好在成功1A（震惊！对着数据调的还好意思叫1A）
首先处理出每个点 i 左边和右边第一个比它大的点，分别记为L[i]和R[i]：
(L[i],R[i])这个点对有P1的贡献
(L[i], (i+1)到(R[i]-1) )这些点对有P2的贡献
( (L[i]+1)到(i-1) ，R[i] )这些点对有P2的贡献
对于每个i， (i,i+1)这个点对有P1的贡献
对于每个询问[a,b]，我们要求的是所有左端点在[a,b]范围内，右端点在[a,b]范围内的点对的贡献。
左端点范围可以用扫描线+主席树差分找到，然后在主席树上查右端点的范围，区间求和即可。
“( (L[i]+1)到(i-1) ，R[i] ) 点对” 起点是区间，终点是单点，不方便和其他的一起维护，就单独再开一棵主席树从右往左扫
标记永久化真好用。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 #define LL long long 7 using namespace std; 8 const int mxn=210010; 9 int read(){ 10 int x=0,f=1;char ch=getchar(); 11 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 12 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 13 return x*f; 14 } 15 struct node{ 16 int l,r; 17 LL smm,val; 18 }t[mxn*80]; 19 int rotL[mxn],rotR[mxn],sz=0; 20 void update(int L,int R,int v,int l,int r,int y,int &rt){ 21 if(L>R)return; 22 rt=++sz; 23 t[rt]=t[y]; 24 t[rt].smm+=(LL)v*(LL)(R-L+1); 25 if(L<=l && r<=R){ t[rt].val+=v;return;} 26 int mid=(l+r)>>1; 27 if(R<=mid)update(L,R,v,l,mid,t[y].l,t[rt].l); 28 else if(L>mid)update(L,R,v,mid+1,r,t[y].r,t[rt].r); 29 else update(L,mid,v,l,mid,t[y].l,t[rt].l),update(mid+1,R,v,mid+1,r,t[y].r,t[rt].r); 30 return; 31 } 32 LL query(int L,int R,int l,int r,int rt){ 33 if(!rt)return 0; 34 if(L<=l && r<=R)return t[rt].smm; 35 LL res=(LL)t[rt].val*(LL)(R-L+1); 36 int mid=(l+r)>>1; 37 if(R<=mid)return res+query(L,R,l,mid,t[rt].l); 38 else if(L>mid)return res+query(L,R,mid+1,r,t[rt].r); 39 else return res+query(L,mid,l,mid,t[rt].l)+query(mid+1,R,mid+1,r,t[rt].r); 40 } 41 // 42 struct Event{ 43 int x,l,r,v; 44 }e[mxn<<2];int ect=0; 45 void add_change(int x,int l,int r,int v){ 46 e[++ect].x=x; e[ect].l=l; e[ect].r=r; e[ect].v=v; 47 return; 48 } 49 int cmpL(Event a,Event b){return a.x<b.x; } 50 // 51 int n,m,a[mxn]; 52 int P1,P2; 53 int La[mxn],Ra[mxn]; 54 void solve(){ 55 int x,y; 56 while(m--){ 57 LL ans=0; 58 x=read();y=read(); 59 ans+=query(x,y,1,n,rotL[y]); 60 ans-=query(x,y,1,n,rotL[x-1]); 61 ans+=query(x,y,1,n,rotR[x]); 62 ans-=query(x,y,1,n,rotR[y+1]); 63 printf("%lld\n",ans); 64 } 65 return; 66 } 67 int main(){ 68 // freopen("in.txt","r",stdin); 69 int i,j,k; 70 n=read();m=read();P1=read();P2=read(); 71 for(i=1;i<=n;i++)a[i]=read(); 72 // 73 for(i=1;i<=n;i++){ 74 k=i-1; 75 while(k && a[k]<a[i])k=La[k]; 76 La[i]=k; 77 } 78 for(i=n;i;i--){ 79 k=i+1; 80 while(k<=n && a[k]<a[i])k=Ra[k]; 81 Ra[i]=k; 82 } 83 for(i=1;i<=n;i++){ 84 add_change(La[i],Ra[i],Ra[i],P1); 85 add_change(La[i],i+1,Ra[i]-1,P2); 86 add_change(Ra[i],La[i]+1,i-1,P2); 87 } 88 sort(e+1,e+ect+1,cmpL); 89 int hd=1; 90 for(i=1;i<=n;i++){ 91 rotL[i]=rotL[i-1]; 92 while(e[hd].x<=i && hd<=ect){ 93 if(e[hd].x && e[hd].l>i){ 94 update(max(1,e[hd].l),min(e[hd].r,n),e[hd].v,1,n,rotL[i],rotL[i]); 95 } 96 hd++; 97 } 98 if(i!=n){ 99 update(i+1,i+1,P1,1,n,rotL[i],rotL[i]);100 }101 }102 hd=ect;103 for(i=n;i;i--){104 rotR[i]=rotR[i+1];105 while(e[hd].x>=i){106 if(e[hd].r<i && e[hd].x<=n){107 update(max(1,e[hd].l),min(e[hd].r,n),e[hd].v,1,n,rotR[i],rotR[i]);108 }109 hd--;110 }111 }112 solve();113 return 0;114 }
Bzoj4826 [Hnoi2017]影魔
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。