本来是个很简单的题目,难住我的主要是这么几点

1.它所有的点都是坐标,不是实际的砖块,1,3指的是1-2 2-3的砖块。。。后来就是用1 代表1-2 ,2代表2-3.。。。。,这样的话,每次读入的数据,都把r--

就行,然后在实际的砖块数就是 x[r+1]-x[l]。

2.我动手太快,没想清楚它是叠层型,即每次读入砖块坐标,都是往原有砖块的基础上++,这样的话,懒惰标记,就也一定是每次++,这里我WA了好久,一开始没想清楚,没按叠层来更新懒惰标记。。

3.有个地方超级难以想到,就是在最后query木板能承载多少砖块的时候,用个flag标记好已经完全清空的node,因为询问有多次,下次再遇到这个node的时候,直接return 0,我一开始没想明白,觉得这个去掉也没关系。。后来发现,因为延迟标记的问题某个节点如果被清空,其子节点可能尚未更新,而且延迟非常严重,可能连初始的砖块都还没更新,弄个极端的例子,直接初始落下砖块1-8,然后只有最顶上的节点有砖块,底下全没有,这个时候你开始插入板子,第一次访问1-8,肯定是正确的结果,再次插板访问1-8中的某一个节点,比如5-8,此时它连上一次的砖块落下那个延迟标记都还没更新,你即便pushdown了,也是第一次插板1-8之前的状态了,绝逼是错的啊。所以我试了好多次,终于明白这个确实是关键。

4.其实离散化反而在这个题目里面很不起眼了,就是最普通的离散化,而且中间不必手动插点也能过。。当然还是手动插一插比较好

5.这个题目卡内存超级BT啊。。我就多开了那么一些,就MLE,少开了一点,就SF越界,我简直无语啊。。

改来改去,代码写的真心挫。。。求不喷。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define N 110010
using namespace std;
long long d[N*];
bool flag[N*];
int pd[N*];
int a[N],b[N];
int x[N*];
struct node
{
int ax;
int bx;
int h;
int id;
long long ans;
} bd[N];
void getup(int rt)
{
d[rt]=d[rt<<]+d[rt<<|];
}
void build(int rt,int l,int r)
{
d[rt]=;
flag[rt]=false;
pd[rt]=;
if (l>=r)
{
return;
}
int mid=(l+r)>>;
build(lson);
build(rson);
//getup(rt);
}
void pushdown(int rt,int l,int r)
{
if (l>=r) return;
int ll=rt<<,rr=rt<<|;
int mid=(l+r)>>;
pd[ll]+=pd[rt];
pd[rr]+=pd[rt];
d[ll]+=(long long)pd[rt]*(x[mid+]-x[l]);
d[rr]+=(long long)pd[rt]*(x[r+]-x[mid+]);
pd[rt]=;
}
void fix(int L,int R,int col,int rt,int l,int r)
{ if (L<=l && r<=R)
{
d[rt]+=(long long)(x[r+]-x[l]);
pd[rt]+=col;
return;
}
pushdown(rt,l,r);
int mid=(l+r)>>;
if (L<=mid) fix(L,R,col,lson);
if (R>mid) fix(L,R,col,rson);
getup(rt);
}
long long query(int L,int R,int rt,int l,int r)
{ if (flag[rt]) return ;//这里是关键,详见要点3
if (L<=l && r<=R)
{
flag[rt]=true;
long long temp;
temp=d[rt];
d[rt]=;
pd[rt]=;
return temp;
}
pushdown(rt,l,r);
int mid=(l+r)>>;
long long ret=;
if (L<=mid) ret+=query(L,R,lson);
if (R>mid) ret+=query(L,R,rson);
getup(rt);
return ret;
}
int bs(int data,int l,int r)
{
int mid;
while (l<r)
{
mid=(l+r)>>;
if (x[mid]==data) return mid;
if (x[mid]<data) l=mid+;
else
r=mid;
}
return l;
}
bool cmp(node a,node b)
{
return a.h>b.h;
}
bool cmp2(node a,node b)
{
return a.id<b.id;
}
int main()
{
int n,m;
while (scanf("%d%d",&n,&m)!=EOF)
{
int i,j;
int mcur=;
for (i=; i<=n; i++)
{
scanf("%d%d",&a[i],&b[i]);
if (a[i]>b[i])
{
int tt=a[i];
a[i]=b[i];
b[i]=tt;
}
//b[i]--;
x[++mcur]=a[i];
x[++mcur]=b[i];
}
for (j=; j<=m; j++)
{
scanf("%d%d%d",&bd[j].ax,&bd[j].bx,&bd[j].h);
bd[j].id=j;
if (bd[j].ax>bd[j].bx)
{
int t2=bd[j].ax;
bd[j].ax=bd[j].bx;
bd[j].bx=t2;
}
//bd[j].bx--;
x[++mcur]=bd[j].ax;
x[++mcur]=bd[j].bx;
}
sort(x+,x++mcur);
int cur=;
for (i=; i<=mcur; i++)
{
if (x[i]!=x[i-]) x[++cur]=x[i];
}
int temp=cur; for (i=; i<=temp; i++)
{
if (x[i]-x[i-]>) x[++cur]=x[i-]+;
//if (x[i]-x[i-1]>2) x[++cur]=x[i]-1;
} sort(x+,x++cur); //for (i=1; i<=cur; i++)
// cout<<i<<" "<<x[i]<<endl; build(,,cur);
int fa,fb;
for (i=; i<=n; i++)
{
fa=bs(a[i],,cur);
fb=bs(b[i],,cur);
if (fa>fb){
int t3=fa;
fa=fb;
fb=t3;
}
if (fb>fa) fb--;
fix(fa,fb,,,,cur);
}
//cout<<"Pass"<<endl;
sort(bd+,bd++m,cmp);
for (i=; i<=m; i++)
{
fa=bs(bd[i].ax,,cur);
fb=bs(bd[i].bx,,cur);
if (fa>fb){
int t4=fa;
fa=fb;
fb=t4;
}
if(fb>fa) fb--;
long long tt=query(fa,fb,,,cur);
bd[i].ans=tt;
}
//cout<<"Pass2"<<endl;
sort(bd+,bd++m,cmp2);
for (j=; j<=m; j++)
{
printf("%lld\n",bd[j].ans);
}
putchar('\n');
}
return ;
}

最新文章

  1. CSS移动端多行显示多余省略号
  2. Jenkins启动时报错:java.net.BindException: Address already in use: bind 解决方法
  3. 将Eclipse代码导入到AndroidStudio的两种方式
  4. GO語言基礎教程:數據類型,變量,常量
  5. 指针二次释放(_BLOCK_TYPE_IS_VALID)
  6. 上传项目的更改 info.plist文件
  7. linux高可用集群(HA)原理详解(转载)
  8. poj 2253 Frogger(最短路 floyd)
  9. Java程序打包
  10. UISwitch 监听响应
  11. H5单页面架构:requirejs + angular + angular-route
  12. Docker部署脚本
  13. 饮冰三年-人工智能-Python-30 python开发中常见的错误
  14. SpringBoot整合篇
  15. linux grep (linux查找关键字在php出现的次数)
  16. 【推荐】使用Ultrapico Expresso学习正则表达式
  17. 抽屉之Tornado实战(7)--form表单验证
  18. c++之enum的好处与 define 的区别
  19. css绘制特殊图形,meida查询,display inline-box间隙问题以及calc()函数
  20. 【来龙去脉系列】深入理解DIP、IoC、DI以及IoC容器

热门文章

  1. 012.Delphi插件之QPlugins,多实例内嵌窗口服务
  2. 4 GC算法与种类
  3. 吴裕雄 Bootstrap 前端框架开发——Bootstrap 字体图标(Glyphicons):glyphicon glyphicon-stop
  4. 创建springboot2.1项目运行报错
  5. Linux学习《第五章 用户身份与文件权限》
  6. 验证试验 更改了从机CAN通信的MAC地址 从机新挂CAN网络 上电自检通过
  7. springboot启动时候的一个注意事项——不同包下有同样名字的class类
  8. C++面试常见问题——03String类的实现
  9. NOIP2016天天爱跑步解题思路
  10. Ajax学习系列——Ajax介绍及优缺点