刷题总结——影魔(HNOI2017 BZOJ4826 线段树+扫描线)
题目:
Description
Input
Output
Sample Input
7 9 5 1 3 10 6 8 2 4
1 7
1 9
1 3
5 9
1 5
Sample Output
39
4
13
16
HINT
Source
题解:
引用下lcf2000的题解,%%%%%%%%
我们枚举最大值的位置i,找出左边第一个比ai大的位置l,右边第一个比ai大的位置r,然后我们分开考虑一下p1和p2的贡献。
首先由于ai为最大值,那么左端点不会小于l,右端点不会大于r。
容易发现只有左端点为l,右端点为r才会产生p1的贡献然后产生p2贡献的有两种:一种是左端点为l,右端点在区间(i,r)中;另一种是左端点区间(l,i)中,右端点为r。
还有一种情况需要考虑,就是左端点和右端点差为1,会产生p1的贡献。对每个询问直接计算就可以了。
所以这个问题可以抽象到二维平面上。有一些点和一些线段都有权值,每次询问某个矩形内部的权值和。
于是离线排序+扫描线+树状数组即可。
自己再说一两句吧···
这道题最先开始要想到的是每次考虑对答案贡献的时候首先要想到的是枚举中间的点···而不是两旁·····
其实这种考虑贡献对象的思路在很多地方都有用到···比如有时做与树有关的题很多时候我们考虑对答案贡献都是考虑每一条边·····希望下次遇到这种题能记住这种思想···
然后就是转二维平面····这个其实比较好想···毕竟看到了点对嘛···
想到转二维那么扫描线和线段树(我是用线段树写的··对带区间修改的树状数组不是太熟···)就是顺理成章的的事情了···
然而转二维时有个细节要注意····一个点可能没有左边第一个比自己大的位置l,或者没有右边第一个比自己大的位置r,如果仅仅是这二者中间少了一个···它也是会对答案产生贡献的···比如7 9 10中的9·····md因为这一点被样例卡着过不去23333
然后就是排序了···修改一定要排在询问前面当高度相同时··这点在cdq分治时其实经常提到·····一定要注意了
最后吐槽一句洛谷为毛要卡线段树啊艹···现在哪有放树状数组不放线段树的···还是bzoj不坑···
代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
using namespace std;
const int N=2e5+;
struct node
{
int x,y,h,v,id;
}q[N*];
int n,m,p1,p2,stack[N],top,num[N],Le[N],Ri[N],cnt,tag[N*];
long long ans[N],tree[N*];
inline int R()
{
char c;int f=;
for(c=getchar();c<''||c>'';c=getchar());
for(;c<=''&&c>='';c=getchar())
f=(f<<)+(f<<)+c-'';
return f;
}
inline bool cmp(node a,node b)
{
if(a.h==b.h) return a.id<b.id;
return a.h<b.h;
}
inline void add(int k,int l,int r,int v)
{
tree[k]+=(long long)(r-l+)*v;
tag[k]+=v;
}
inline void pushdown(int k,int l,int r,int mid)
{
if(tag[k])
{
add(k*,l,mid,tag[k]);
add(k*+,mid+,r,tag[k]);
tag[k]=;
}
}
inline void modify(int k,int l,int r,int x,int y,int v)
{
if(l>=x&&r<=y)
{
add(k,l,r,v);
return;
}
int mid=(l+r)/;
pushdown(k,l,r,mid);
if(x<=mid) modify(k*,l,mid,x,y,v);
if(y>mid) modify(k*+,mid+,r,x,y,v);
tree[k]=tree[k*]+tree[k*+];
}
inline long long query(int k,int l,int r,int x,int y)
{
if(l>=x&&r<=y)
return tree[k];
int mid=(l+r)/;
pushdown(k,l,r,mid);long long temp=;
if(x<=mid) temp+=query(k*,l,mid,x,y);
if(y>mid) temp+=query(k*+,mid+,r,x,y);
return temp;
}
int main()
{
//freopen("a.in","r",stdin);
n=R(),m=R(),p1=R(),p2=R();int a,b;
for(int i=;i<=n;i++) num[i]=R();
for(int i=;i<=n;i++)
{
while(top&&num[i]>num[stack[top]]) Ri[stack[top]]=i,top--;
if(top) Le[i]=stack[top];
stack[++top]=i;
}
for(int i=;i<=m;i++)
{
a=R(),b=R();ans[i]=(long long)(b-a)*p1;
q[++cnt].x=a,q[cnt].y=b,q[cnt].h=a-,q[cnt].v=-;q[cnt].id=i;
q[++cnt].x=a,q[cnt].y=b,q[cnt].h=b,q[cnt].v=;q[cnt].id=i;
}
for(int i=;i<=n;i++)
{
if(Ri[i]&&Le[i])
{
q[++cnt].x=Le[i],q[cnt].y=Le[i],q[cnt].h=Ri[i],q[cnt].v=p1;
if(Le[i]<i-) q[++cnt].x=Le[i]+,q[cnt].y=i-,q[cnt].h=Ri[i],q[cnt].v=p2;
if(Ri[i]>i+) q[++cnt].x=i+,q[cnt].y=Ri[i]-,q[cnt].h=Le[i],q[cnt].v=p2;
}
else if(Ri[i])
{
if(i>) q[++cnt].x=,q[cnt].y=i-,q[cnt].h=Ri[i],q[cnt].v=p2;
}
else if(Le[i])
{
if(i<n) q[++cnt].x=i+,q[cnt].y=n,q[cnt].h=Le[i],q[cnt].v=p2;
}
}
sort(q+,q+cnt+,cmp);
for(int i=;i<=cnt;i++)
{
if(q[i].id)
ans[q[i].id]+=(long long)q[i].v*query(,,n,q[i].x,q[i].y);
else
modify(,,n,q[i].x,q[i].y,q[i].v);
}
for(int i=;i<=m;i++)
printf("%lld\n",ans[i]);
return ;
}
最新文章
- [tp3.2.1]数据模型 - 简单的模型连接
- 学习记录 java 哈希
- sql server 查询数据库所有的表名+字段
- PHP自定义函数使用外部变量
- Hadoop2.0新特性-持续追加【干货】
- Android学习过程
- .Net remoting, Webservice,WCF,Socket区别
- PsExec.exe执行远程程序
- win7下Apache2.4安装、配置及服务自启动
- 分享一个图片上传插件(TP5.0)
- Jquery+Ajax限制查询间隔
- windows消息简单应用实例
- xamarin android checkbox自定义样式
- 数据库连接池(c3p0)
- MS SQL 监控磁盘空间告警
- ";《算法导论》之‘排序’";:线性时间排序
- gcc 找不到 boot python 链接库的问题: /usr/bin/ld: cannot find -lboost_python
- ONI无法启动: Uh oh! Unable to launch Neovim...
- 内部排序->;插入排序->;其它插入排序->;表插入排序
- pre强制 自动换行