洛谷3722 [ah2017_hnoi2017]影魔

恶心数据结构题的简单方法

Posted by yjjr's blog on February 26, 2018

标签:扫描线,树状数组,单调栈

题目

题目传送门

题目背景

影魔,奈文摩尔,据说有着一个诗人的灵魂。 事实上,他吞噬的诗人灵魂早已成千上万。

千百年来,他收集了各式各样的灵魂,包括诗人、 牧师、 帝王、 乞丐、 奴隶、 罪人,当然,还有英雄。

题目描述

每一个灵魂,都有着自己的战斗力,而影魔,靠这些战斗力提升自己的攻击。

奈文摩尔有 n 个灵魂,他们在影魔宽广的体内可以排成一排,从左至右标号 1 到 n。第 i个灵魂的战斗力为 k[i],灵魂们以点对的形式为影魔提供攻击力,对于灵魂对 i, j(i<j)来说,若不存在 ks大于 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]。

输入输出格式

输入格式

输入文件名为 sf.in。

第一行 n,m,p1,p2

第二行 n 个数: k[1],k[2],…,k[n]

接下来 m 行, 每行两个数 a,b, 表示询问区间[a,b]中的灵魂对会为影魔提供多少攻击力。

输出格式

输出文件名为 sf.out

共输出 m 行,每行一个答案,依次对应 m 个询问。

输入输出样例

输入样例#1

10 5 2 3
7 9 5 1 3 10 6 8 2 4
1 7
1 9
1 3
5 9
1 5

输出样例#1

30
39
4
13
16

说明

30%: 1<= n,m <= 500。

另 30%: p1=2* p2。

100%:1 <= n,m <= 200000; 1 <= p1,p2 <= 1000。

题意

给定长度为n的序列ai和q个询问

每个询问有两个端点l,r

如果两个端点分别是这个区间的最大值和次大值,有p1的贡献,否则如果其中一个端点是这个区间的最大值,有p2的贡献

问所有被区间完全包含的区间的贡献和

分析

一开始看这题,网上全是线段树做法的题解,还有主席树的,果然每年只要AHOI参加的那个省省选题都很考验码力

新版AHOI数据结构大赛


回归正题,我用的是树状数组+扫描线+单调栈的做法

我们考虑对答案产生贡献的情况

对于点x,找出左右各比它大的第一个点所在位置le,ri

  • 只有左端点为le,右端点为ri才会产生p1的贡献

  • 左端点在(le,x),右端点为ri产生p2的贡献

  • 左端点在le,右端点在(x,ri)产生p2的贡献

  • 左右端点差值为1的情况产生p1的贡献(可以O(1)计算,之后就不再多讨论了)

那么我们可以抽象到二维平面上,分别把矩形和询问排序,做一遍扫描线,使用树状数组快速求和维护

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=2e5+6;
int n,m,p1,p2,S[maxn]={0},top=1,ls,a[maxn],le[maxn],ri[maxn],n1=1,n2=1;
ll ans[maxn],c1[maxn],c2[maxn];
struct node{int l,r,x,b,z;}s1[maxn<<1],s2[maxn<<2];
inline bool operator < (node a,node b){return a.x<b.x;}//将矩形和点按x升序排列
void modify(int x,int y){if(x)for(int i=x;i<=n;i+=i&(-i))c1[i]+=y,c2[i]+=1ll*x*y;}//树状数组修改
inline ll query(int x){
	ll re=0;
	for(int i=x;i;i-=i&(-i))re+=(x+1)*c1[i]-c2[i];
	return re;
}//树状数组求和
int main()
{
	n=read(),m=read(),p1=read(),p2=read();
	a[0]=a[n+1]=n+1;
	rep(i,1,n)a[i]=read();
	rep(i,1,n+1){
		while(a[S[top]]<a[i])ri[S[top--]]=i;
		le[i]=S[top];S[++top]=i;
	}//单调栈求左右各比a[i]大的第一个点所在位置
	rep(i,1,m){
		int l=read(),r=read();ans[i]+=(r-l)*p1;
		s1[i]=(node){l,r,l-1,i,-1};
		s1[i+m]=(node){l,r,r,i,1};
	}//将询问离线存储
	sort(s1+1,s1+m+m+1);
	rep(i,1,n){
		if(le[i]&&ri[i]<=n)s2[++ls]=(node){le[i],le[i],ri[i],0,p1};
		if(le[i]&&ri[i]>i+1)s2[++ls]=(node){i+1,ri[i]-1,le[i],0,p2};
		if(le[i]+1<i&&ri[i]<=n)s2[++ls]=(node){le[i]+1,i-1,ri[i],0,p2};
	}//建立矩形
	sort(s2+1,s2+ls+1);
	while(!s1[n1].x)n1++;
	rep(i,1,n){
		if(n1>m+m)break;
		while(n2<=ls&&s2[n2].x==i){
			modify(s2[n2].r+1,-s2[n2].z);
			modify(s2[n2].l,s2[n2].z),n2++;
		}
		while(n1<=m+m&&s1[n1].x==i){
			ans[s1[n1].b]+=s1[n1].z*(query(s1[n1].r)-query(s1[n1].l-1));
			n1++;
		}
	}//扫描线求询问的矩形面积和
	rep(i,1,m)printf("%lld\n",ans[i]);
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr