仍然是一道cdq模版。。

那么对于一个询问,容斥一下分成四个,变成问(1,1)~(x,y),那么对于x,y,修改只有x'<=x&&y'<=y,才对询问有影响,那么加上读入顺序,就是一个三维偏序了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std; struct node
{
int tp,x,y,v,be;//第一维时间已经有序
//tp=0 表示修改 v为修改的值
//tp=-1、1询问 v为所求值
}a[];int len;
void ins(int tp,int x,int y,int v,int be)
{
len++;
a[len].tp=tp;
a[len].x=x;a[len].y=y;
a[len].v=v;a[len].be=be;
} //---------------------------------- int n,s[];
int lowbit(int x){return x&-x;}
void add(int x,int k)
{
while(x<=n)
{
s[x]+=k;
x+=lowbit(x);
}
}
int getsum(int x)
{
int ans=;
while(x>=)
{
ans+=s[x];
x-=lowbit(x);
}
return ans;
} //---------------树状数组----------------- node t[];
void cdq(int l,int r)
{
if(l==r)return ;
int mid=(l+r)/;
cdq(l,mid);
cdq(mid+,r); int i=l,j=mid+,p=l;
while(i<=mid&&j<=r)
{
if(a[i].x<=a[j].x)
{
if(a[i].tp==)add(a[i].y,a[i].v);
t[p++]=a[i++];
}
else
{
if(a[j].tp!=)a[j].v+=getsum(a[j].y);
t[p++]=a[j++];
}
}
while(i<=mid)
{
if(a[i].tp==)add(a[i].y,a[i].v);
t[p++]=a[i++];
}
while(j<=r)
{
if(a[j].tp!=)a[j].v+=getsum(a[j].y);
t[p++]=a[j++];
} for(int i=l;i<=mid;i++)
if(a[i].tp==)add(a[i].y,-a[i].v); for(int i=l;i<=r;i++)a[i]=t[i];
} //-------------------cdq------------------------ int ans[],ansl;
int main()
{
int S;
scanf("%d%d",&S,&n); int op,x1,y1,x2,y2,v;len=;
while(scanf("%d",&op)!=EOF)
{
if(op==)break; if(op==)
{
scanf("%d%d%d",&x1,&y1,&v);
ins(,x1,y1,v,);
}
else
{
ansl++;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if(x1->&&y1->)ins(,x1-,y1-,,ansl);
if(x1->)ins(-,x1-,y2,,ansl);
if(y1->)ins(-,x2,y1-,,ansl);
ins(,x2,y2,,ansl);
}
} cdq(,len); memset(ans,,sizeof(ans));
for(int i=;i<=len;i++)
if(a[i].tp!=)ans[a[i].be]+=a[i].v*a[i].tp; for(int i=;i<=ansl;i++)printf("%d\n",ans[i]);
return ;
}

最新文章

  1. 一步步搭建自己的博客 .NET版(2、评论功能)
  2. android XML布局 属性与运用
  3. java发送短信--httpclient方式
  4. 在Oracle中更新数据时,抛出:ORA-01008: not all variables bound
  5. python学习笔记——列表生成式与生成器
  6. YII访问数据库
  7. ie8中parseInt字符型数值转换数值型问题
  8. 在Ubuntu 14.04 64bit上安装StarUML 2.5版本
  9. .gitignore文件的配置和生效
  10. GUI学习之二——PyQt控件初识
  11. G - Balanced Lineup POJ - 3264 线段树最大最小值区间查询模版题
  12. gentoo emacs 中文输入法 呼出
  13. HTML5 文件API
  14. MySQL5.6主从复制最佳实践
  15. systemtap 脚本示例
  16. 复杂密码生成工具apg
  17. CSS2中的伪类与伪元素
  18. unity3d 自带截屏
  19. OpenCV学习笔记十六:opencv_calib3d模块
  20. Mac idea maven 创建web项目

热门文章

  1. 如何根据实体动态生成sql语句
  2. python基础——7(函数)
  3. python基础——3(流程控制)
  4. springmvc ajax传值详解
  5. 运动员最佳匹配问题(km算法)
  6. bzoj4950(二分图最大匹配)
  7. jvm参数设置 -vmargs -Xms128M -Xmx512M -XX:PermSize=64M -XX:MaxPermSize=128M
  8. TYVJ P 1214 硬币问题
  9. Match the string--hdu1797(模拟)
  10. 寒武纪camp Day5