[BZOJ2527]Meteors
2024-10-21 03:13:15
整体二分挺好玩的...学一发
这个询问显然是可以二分的,但每次都二分就会T爆,所以我们有了“整体”二分
每次处理一些询问,要求这些询问的答案一定在$[l,r]$中
先把$l$到$mid$的操作实施,那么当前TAK的询问答案一定在$[l,mid]$中,当前NIE的询问答案一定在$[mid+1,r]$中,对答案为$[mid+1,r]$的那些询问加上$[l,mid]$的修改所产生的影响后分治处理即可
开始时加上一个操作$(1,m,+\infty)$就可以处理NIE的情况了
直接用线段树会被卡常,因为是区间加,单点询问,所以差分后用树状数组做即可
#include<stdio.h> #include<vector> using namespace std; typedef long long ll; const int inf=1000000000; struct rain{ int l,r,d; rain(int a=0,int b=0,int c=0){l=a;r=b;d=c;} }R[300010]; vector<int>s[300010]; vector<int>::iterator it; int p[300010],q[300010],ans[300010],ql[300010],qr[300010],n,m; ll d[300010],las[300010]; int lowbit(int x){return x&-x;} void add(int x,int v){ while(x<=m){ d[x]+=v; x+=lowbit(x); } } void add(int l,int r,int v){ add(l,v); add(r+1,-v); } ll query(int x){ ll s=0; while(x){ s+=d[x]; x-=lowbit(x); } return s; } void solve(int h,int t,int l,int r){ if(h>t)return; int i,mid,cl,cr; ll tmp; if(l==r){ for(i=h;i<=t;i++)ans[q[i]]=l; return; } mid=(l+r)>>1; for(i=l;i<=mid;i++){ if(R[i].l<=R[i].r) add(R[i].l,R[i].r,R[i].d); else{ add(R[i].l,m,R[i].d); add(1,R[i].r,R[i].d); } } cl=cr=0; for(i=h;i<=t;i++){ tmp=0; for(it=s[q[i]].begin();it!=s[q[i]].end();it++){ tmp+=query(*it); if(tmp+las[q[i]]>=p[q[i]])break; } if(tmp+las[q[i]]>=p[q[i]]) ql[++cl]=q[i]; else{ las[q[i]]+=tmp; qr[++cr]=q[i]; } } for(i=1;i<=cl;i++)q[h+i-1]=ql[i]; for(i=1;i<=cr;i++)q[h+cl+i-1]=qr[i]; for(i=l;i<=mid;i++){ if(R[i].l<=R[i].r) add(R[i].l,R[i].r,-R[i].d); else{ add(R[i].l,m,-R[i].d); add(1,R[i].r,-R[i].d); } } solve(h,h+cl-1,l,mid); solve(h+cl,t,mid+1,r); } int main(){ int i,x,k; scanf("%d%d",&n,&m); for(i=1;i<=m;i++){ scanf("%d",&x); s[x].push_back(i); } for(i=1;i<=n;i++)scanf("%d",p+i); scanf("%d",&k); for(i=1;i<=k;i++)scanf("%d%d%d",&R[i].l,&R[i].r,&R[i].d); R[++k]=rain(1,m,inf); for(i=1;i<=n;i++)q[i]=i; solve(1,n,1,k); for(i=1;i<=n;i++){ if(ans[i]==k) puts("NIE"); else printf("%d\n",ans[i]); } }
最新文章
- 本地部署arcgis by eclipse
- [原创]首次制作JQueryUI插件-Timeline时间轴
- MVC 之 WebAPI 系列一
- 做java工作整整1年了,看到了大牛的奋斗历程,我感觉自己又有目标了
- Linux设置IP
- 深入认识JavaScript 中的this指针
- hdu 1800 Flying to the Mars
- 五、Linux/UNIX操作命令积累【cp、mv、cat、grep、ps】
- svn rollback: 恢复到上一版本
- JSON.parse()和JSON.stringify()和eval(&#39;(&#39; + result + &#39;)&#39;)
- react 生命周期函数介绍
- 修改oracle数据库内存报错
- JavaScript JSON对象(一)
- Python-CSS高级 题目
- DRBD数据镜像与搭建
- 因样式冲突引起的div消失问题
- 《高性能SQL调优精要与案例解析》——10.4_SQL语句改写部分文档
- postgre与mysql区别
- Collabtive 系统 SQL 注入实验(补充)
- groovy类、构造函数、方法