P3834 【模板】可持久化线段树 2 模板，直接看代码： C++ #include using namespace std; #define lowbit(x) x&-x const int N=2e5+5; int n,m,cnt; int ans[N],tree[N]; int maxn=INT_MIN,minn=INT_MAX; struct node{ int x,y,k,id,op; }q[N=1;i-=lowbit(i)) res+=p[i]; return res; } }bit; void solve(int l,int r,int vl,int vr){ if(l>r) return; if(vl==vr){ for(int i=l;i>1; int cnt1=0,cnt2=0; for(int i=l;i=q[i].k) q1[++cnt1]=q[i]; else{ q[i].k-=s; q2[++cnt2]=q[i]; } } } for(int i=1;i>n>>m; for(int i=1;i>x; q[++cnt]={x,0,0,i,0}; minn=min(minn,x),maxn=max(maxn,x); } for(int i=1;i>x>>y>>k; q[++cnt]={x,y,k,i,1}; } solve(1,cnt,minn,maxn); for(int i=1;i `#include using namespace std; #define lowbit(x) x&-x const int N=2e5+5; int n,m,cnt; int ans[N],tree[N]; int maxn=INT_MIN,minn=INT_MAX; struct node{ int x,y,k,id,op; }q[N1],q1[N1],q2[N1]; struct BIT{ int p[N]; void add(int x,int k){ for(int i=x;in;i+=lowbit(i)) p[i]+=k; } int sum(int x){ int res=0; for(int i=x;i>=1;i-=lowbit(i)) res+=p[i]; return res; } }bit; void solve(int l,int r,int vl,int vr){ if(l>r) return; if(vl==vr){ for(int i=l;ir;i++) if(q[i].op) ans[q[i].id]=vl; return; } int mid=vl+vr>>1; int cnt1=0,cnt2=0; for(int i=l;ir;i++){ if(!q[i].op){ if(q[i].xmid){ bit.add(q[i].id,1); q1[++cnt1]=q[i]; } else q2[++cnt2]=q[i]; } else{ int s=bit.sum(q[i].y)-bit.sum(q[i].x-1); if(s>=q[i].k) q1[++cnt1]=q[i]; else{ q[i].k-=s; q2[++cnt2]=q[i]; } } } for(int i=1;icnt1;i++) if(!q1[i].op) bit.add(q1[i].id,-1); for(int i=1;icnt1;i++) q[i+l-1]=q1[i]; for(int i=1;icnt2;i++) q[i+l+cnt1-1]=q2[i]; solve(l,l+cnt1-1,vl,mid); solve(l+cnt1,r,mid+1,vr); } int main(){ cin>>n>>m; for(int i=1;in;i++){ int x; cin>>x; q[++cnt]={x,0,0,i,0}; minn=min(minn,x),maxn=max(maxn,x); } for(int i=1;im;i++){ int x,y,k; cin>>x>>y>>k; q[++cnt]={x,y,k,i,1}; } solve(1,cnt,minn,maxn); for(int i=1;im;i++) coutans[i]"\n"; return 0; }` P1527 [国家集训队] 矩阵乘法 上一题的二维版本，把树状数组改成二维的即可，代码： P3527 [POI 2011] MET-Meteors 每次询问的答案具有单调性，考虑整体二分。 相对于模板，把树状数组的操作改为区间修改、单点查询，注意在计算时要把每个国家所占所有轨道都计算上。 代码： P3332 [ZJOI2013] K 大数查询 相较于板子发现需要一个支持区间修改和区间查询的数据结构，考虑线段树，其它都差不多了。 P7424 [THUPC 2017] 天天爱射击 答案明显具有单调性，考虑整体二分。 其余二分答案没啥好说的，一个答案区间，一个处理询问区间，先假设答案区间前一半的子弹都发射，再把询问区间的木板分成两部分，这些都是整体二分的套路。 代码：
整体二分
笔记