题目链接:https://codeforces.com/gym/101982/attachments

要你求覆盖奇数次的矩形面积并,每次更新时减去原先的值即可实现奇数次有效,下推时为保证线段长度不变左儿子的值为x[mid]-x[l]再减原来的值,右儿子的值为x[r]-x[mid]再减原来的值

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define maxn 200005
struct seg{
ll l,r,h,s;
seg(){}
seg(ll l,ll r,ll h,ll s):l(l),r(r),h(h),s(s){};
bool operator <(const seg &a)const{
return h<a.h;
}
}se[maxn];
ll sum[maxn<<],lazy[maxn<<],x[maxn];
void pushup(ll rt)
{
sum[rt]=sum[rt<<]+sum[rt<<|];
}
void pushdown(ll rt,ll l,ll r)
{
if(lazy[rt])
{
lazy[rt<<]^=;
lazy[rt<<|]^=;
ll mid=l+r>>;
sum[rt<<]=x[mid]-x[l]-sum[rt<<];
sum[rt<<|]=x[r]-x[mid]-sum[rt<<|];
lazy[rt]=;
}
}
void update(ll L,ll R,ll l,ll r,ll rt)
{
if(L<=l&&R>=r)
{
lazy[rt]^=;
sum[rt]=x[r]-x[l]-sum[rt];
return ;
}
ll mid=l+r>>;
pushdown(rt,l,r);
if(L<mid)update(L,R,l,mid,rt<<);
//因为往右更新时是mid到r 不是mid+1到r 所以L<=mid 会造成死循环 如l=l r=2 L=2 R=3 mid=1
if(R>mid)update(L,R,mid,r,rt<<|);
pushup(rt);
}
int main()
{
int n,x1,x2,y1,y2,tot=;
cin>>n;
for(int i=;i<=n;i++)
{
cin>>x1>>y1>>x2>>y2;
x[tot]=x1;
se[tot++]=seg(x1,x2,y1,);
x[tot]=x2;
se[tot++]=seg(x1,x2,y2,-);
}
x[]=-;
sort(x+,x+tot);
sort(se+,se+tot);
int nx=unique(x,x+tot)-x;
ll ans=;
for(int i=;i<tot-;i++)
{
ll l=lower_bound(x,x+nx,se[i].l)-x;
ll r=lower_bound(x,x+nx,se[i].r)-x;
update(l,r,,nx,);
ans+=sum[]*(se[i+].h-se[i].h);
}
cout<<ans<<endl;
return ;
}

最新文章

  1. 空的安卓工程添加activity
  2. Arcgis报错: Bad login user Failed to execute (CreateEnterpriseGeodatabase).
  3. Leetcode 之Construct Binary Tree(52)
  4. java08 Set
  5. ios7新特性实践
  6. 学习使用React Native的心得体会
  7. 【CSS3】边框
  8. Scrum 冲刺 第一日
  9. Ansible实战演练
  10. NHibernate从入门到精通系列(3)——第一个NHibernate应用程序
  11. Android下资源使用的方式-android学习之旅(五十三)
  12. zuul进阶学习(二)
  13. phtoshop cs6 下载安装及破解方法(另附Photoshop CC 2018破解版图文教程)
  14. 框架中的导航框架 &amp; position定位
  15. POJ - 1836 Alignment (动态规划)
  16. Python swapcase
  17. 初步认识Angulajs
  18. mysql-libs版本冲突卸载不了
  19. View的measure机制
  20. HDU 4532 湫秋系列故事——安排座位 (组合+DP)

热门文章

  1. H3C 显示RIP当前运行状态及配置信息
  2. 2018-2-13-wpf-使用-Dispatcher.Invoke-冻结窗口
  3. java IO的概述和File方法
  4. java 利用反射创建对象
  5. P1058 车厢重组
  6. Linux 旗标实现
  7. tensorflow在文本处理中的使用——Word2Vec预测
  8. GetDc函数与GetWindowDC函数的区别
  9. HDU1251 统计难题[map的应用][Trie树]
  10. 以windows服务方式快速部署免安装版Postgres数据库