ZR 集训 Day2 - 线段树进阶 · ooliver

ZR 集训 Day2 - 线段树进阶 CF915E Physical Education Lessons 动态开点板子，代码： C++ #include using namespace std; #define lc(p) tr[p].lson #define rc(p) tr[p].rson int n,q,idx,rt; struct node{ int lson,rson,sum,lazy=-1; }tr[300005*55]; void pushup(int p){ tr[p].sum=tr[lc(p)].sum+tr[rc(p)].sum; } void pushdown(int p,int l,int r){ if(tr[p].lazy!=-1){ int mid=l+r>>1; if(!lc(p)) lc(p)=++idx; if(!rc(p)) rc(p)=++idx; tr[lc(p)].lazy=tr[p].lazy; tr[lc(p)].sum=tr[p].lazy*(mid-l+1); tr[rc(p)].lazy=tr[p].lazy; tr[rc(p)].sum=tr[p].lazy*(r-mid); tr[p].lazy=-1; } } void add(int &p,int l,int r,int L,int R,int tag){ if(!p) p=++idx; if(l>=L&&r>1; pushdown(p,l,r); if(Lmid) add(rc(p),mid+1,r,L,R,tag); pushup(p); } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>q; add(rt,1,n,1,n,1); for(int i=1;i>l>>r>>k; if(k==1){ add(rt,1,n,l,r,0); cout `#include using namespace std; #define lc(p) tr[p].lson #define rc(p) tr[p].rson int n,q,idx,rt; struct node{ int lson,rson,sum,lazy=-1; }tr[300005*55]; void pushup(int p){ tr[p].sum=tr[lc(p)].sum+tr[rc(p)].sum; } void pushdown(int p,int l,int r){ if(tr[p].lazy!=-1){ int mid=l+r>>1; if(!lc(p)) lc(p)=++idx; if(!rc(p)) rc(p)=++idx; tr[lc(p)].lazy=tr[p].lazy; tr[lc(p)].sum=tr[p].lazy*(mid-l+1); tr[rc(p)].lazy=tr[p].lazy; tr[rc(p)].sum=tr[p].lazy*(r-mid); tr[p].lazy=-1; } } void add(int &p,int l,int r,int L,int R,int tag){ if(!p) p=++idx; if(l>=L&&rR){ tr[p].lazy=tag; tr[p].sum=tag*(r-l+1); return; } int mid=l+r>>1; pushdown(p,l,r); if(Lmid) add(lc(p),l,mid,L,R,tag); if(R>mid) add(rc(p),mid+1,r,L,R,tag); pushup(p); } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>q; add(rt,1,n,1,n,1); for(int i=1;iq;i++){ int l,r,k; cin>>l>>r>>k; if(k==1){ add(rt,1,n,l,r,0); couttr[rt].sum"\n"; } else{ add(rt,1,n,l,r,1); couttr[rt].sum"\n"; } } return 0; }` P4097 【模板】李超线段树 / [HEOI2013] Segment 李超线段树模板，处理的是在线加入若干一次函数并在线询问某横坐标上最大的函数值。详情看代码： C++ #include using namespace std; const int N=1e5+5; const double eps=1e-9; #define lc p #define fi first #define sc second int n,ans,idx; struct node{ double k,b; }a[N]; struct tree{ int l,r,ln;//ln记录当前区间较优线段 }tr[Neps) return 1; if(y-x>eps) return -1; return 0; } double f(int x,int id){ return x*a[id].k+a[id].b; } void build(int p,int l,int r){ tr[p].l=l,tr[p].r=r; if(l==r) return; int mid=l+r>>1; build(lc,l,mid); build(rc,mid+1,r); } void upd(int p,int l,int r,int x){ int mid=l+r>>1; int c=pr(f(mid,x),f(mid,tr[p].ln)); if(c==1||(c==0&&x=l&&tr[p].r>1; if(lmid) seg(rc,l,r,id); } void add(int x1,int y1,int x2,int y2){ if(x1==x2){//垂直线段判定 a[++idx]={0,max(y1,y2)}; seg(1,x1,x2,idx); return; } double k=1.0*(y1-y2)/(x1-x2); double b=1.0*y1-k*x1; a[++idx]={k,b}; seg(1,x1,x2,idx); } pdi qry(int p,int x){//查询 if(tr[p].l==x&&tr[p].r==x) return {f(x,tr[p].ln),tr[p].ln}; int mid=tr[p].l+tr[p].r>>1; pdi ans; if(xtr[p].ln)) ans={f(x,tr[p].ln),tr[p].ln}; return ans; } signed main(){ cin>>n; build(1,1,39989); for(int i=1,op,x1,x2,y1,y2,k;i>op; if(op==0){ cin>>k; k=(k+ans-1)%39989+1; ans=qry(1,k).sc; cout>x1>>y1>>x2>>y2; x1=(x1+ans-1)%39989+1; x2=(x2+ans-1)%39989+1; y1=(y1+ans-1)%(int)1e9+1; y2=(y2+ans-1)%(int)1e9+1; if(x2 `#include using namespace std; const int N=1e5+5; const double eps=1e-9; #define lc p #define rc p #define pdi pair #define fi first #define sc second int n,ans,idx; struct node{ double k,b; }a[N]; struct tree{ int l,r,ln;//ln记录当前区间较优线段 }tr[N2]; int pr(double x,double y){//判断大小 if(x-y>eps) return 1; if(y-x>eps) return -1; return 0; } double f(int x,int id){ return x*a[id].k+a[id].b; } void build(int p,int l,int r){ tr[p].l=l,tr[p].r=r; if(l==r) return; int mid=l+r>>1; build(lc,l,mid); build(rc,mid+1,r); } void upd(int p,int l,int r,int x){ int mid=l+r>>1; int c=pr(f(mid,x),f(mid,tr[p].ln)); if(c==1||(c==0&&xtr[p].ln)) swap(tr[p].ln,x);//判断新加入的线段中点函数值是否更优 if(l==r) return; int cl=pr(f(l,x),f(l,tr[p].ln)),cr=pr(f(r,x),f(r,tr[p].ln));//判断剩下的线段左右两边是否更优 if(cl==1||(cl==0&&xtr[p].ln)) upd(lc,l,mid,x); if(cr==1||(cr==0&&xtr[p].ln)) upd(rc,mid+1,r,x); } void seg(int p,int l,int r,int id){//找到线段完全覆盖的区间 if(tr[p].l>=l&&tr[p].rr){ upd(p,tr[p].l,tr[p].r,id); return; } int mid=tr[p].l+tr[p].r>>1; if(lmid) seg(lc,l,r,id); if(r>mid) seg(rc,l,r,id); } void add(int x1,int y1,int x2,int y2){ if(x1==x2){//垂直线段判定 a[++idx]={0,max(y1,y2)}; seg(1,x1,x2,idx); return; } double k=1.0*(y1-y2)/(x1-x2); double b=1.0*y1-k*x1; a[++idx]={k,b}; seg(1,x1,x2,idx); } pdi qry(int p,int x){//查询 if(tr[p].l==x&&tr[p].r==x) return {f(x,tr[p].ln),tr[p].ln}; int mid=tr[p].l+tr[p].r>>1; pdi ans; if(xmid) ans=qry(lc,x); else ans=qry(rc,x); int c=pr(ans.fi,f(x,tr[p].ln)); if(c==-1||(c==0&&ans.sc>tr[p].ln)) ans={f(x,tr[p].ln),tr[p].ln}; return ans; } signed main(){ cin>>n; build(1,1,39989); for(int i=1,op,x1,x2,y1,y2,k;in;i++){ cin>>op; if(op==0){ cin>>k; k=(k+ans-1)%39989+1; ans=qry(1,k).sc; coutans"\n"; } else{ cin>>x1>>y1>>x2>>y2; x1=(x1+ans-1)%39989+1; x2=(x2+ans-1)%39989+1; y1=(y1+ans-1)%(int)1e9+1; y2=(y2+ans-1)%(int)1e9+1; if(x2x1) swap(x1,x2),swap(y1,y2); add(x1,y1,x2,y2); } } return 0; }` P8593 「KDOI-02」一个弹的投根据物理知识，知道不在同一纵坐标的导弹是不会碰撞的。所以根据纵坐标分类，就变成了找逆序对的问题，记得要离散化。代码： C++ #include using namespace std; const int N=5e5+5; #define lowbit(x) x&-x #define int long long int n,m,sum; int a[N],d[N],b[N]; struct node{ int x,id; double y; bool operator0;i-=lowbit(i)) res+=tr[i]; return res; } }bit; map> mp; signed main(){ cin>>n>>m; for(int i=1;i>q[i].x>>q[i].id>>q[i].y,b[i]=q[i].x; sort(b+1,b+1+n); for(int i=1;i=0;k--){ node x=j[k]; a[x.id]+=bit.check(x.x-1); cnt++; bit.add(x.x,1); } for(node x:j) bit.add(x.x,-1); for(node x:j) sum+=a[x.id]; } for(int i=1;i>d[i],d[i]=min(d[i],a[i]); sort(d+1,d+1+n); for(int i=n;i>n-m&&i>0;i--) sum-=d[i]; cout `#include using namespace std; const int N=5e5+5; #define lowbit(x) x&-x #define int long long int n,m,sum; int a[N],d[N],b[N]; struct node{ int x,id; double y; bool operatorconst node b)const{ return yb.y; } }q[N]; struct BIT{ int tr[N]; void add(int x,int k){ for(int i=x;in;i+=lowbit(i)) tr[i]+=k; } int check(int x){ if(!x) return 0; int res=0; for(int i=x;i>0;i-=lowbit(i)) res+=tr[i]; return res; } }bit; mapint,vectornode>> mp; signed main(){ cin>>n>>m; for(int i=1;in;i++) cin>>q[i].x>>q[i].id>>q[i].y,b[i]=q[i].x; sort(b+1,b+1+n); for(int i=1;in;i++){ double y=1.0*q[i].x+1.0*q[i].y*sqrt(2.0*q[i].id/9.8); q[i].x=lower_bound(b+1,b+1+n,q[i].x)-b; mp[(int)q[i].id].push_back({q[i].x,i,y}); } for(auto [i,j]:mp){ sort(j.begin(),j.end()); int cnt=0; for(node x:j){ a[x.id]=cnt-bit.check(x.x-1); cnt++; bit.add(x.x,1); } for(node x:j) bit.add(x.x,-1); cnt=0; for(int k=j.size()-1;k>=0;k--){ node x=j[k]; a[x.id]+=bit.check(x.x-1); cnt++; bit.add(x.x,1); } for(node x:j) bit.add(x.x,-1); for(node x:j) sum+=a[x.id]; } for(int i=1;in;i++) cin>>d[i],d[i]=min(d[i],a[i]); sort(d+1,d+1+n); for(int i=n;i>n-m&&i>0;i--) sum-=d[i]; coutsum; return 0; }` P5554 篮球统计列出篮球高度关于时间的表达式： \begin{aligned} h&=-\frac{1}{2}g(t-l)^2+v(t-l)+a \\ h&=-\frac{1}{2}gt^2+(gl+v)t+(-\frac{1}{2}gl^2-vl+a) \end{aligned} 可以发现，每个篮球在同一时间时，-\frac{1}{2}gt^2 都是一样的，也就是说高度的比较只看后面的一次函数，那就变成了李超线段树。对于小数的处理，我们乘以 1000，就变成整数了，但值域也随之变大，所以要用动态开点线段树。代码： C++ #include using namespace std; #define pdi pair #define fi first #define sc second const int N=1e5+5,MAXN=N*70,L=-1000000005,R=1000000005; const long double eps=1e-9L,g=9.8L,inf=1e30L; int m,root,idx,tot; long double k[N],b[N]; struct tree{ int lc,rc,id; }tr[MAXN]; int pr(long double x,long double y){ if(x-y>eps) return 1; if(y-x>eps) return -1; return 0; } long double f(int x,int id){ if(id==0) return -inf; long double xx=x/1000.0L; return k[id]*xx+b[id]; } void upd(int &p,int l,int r,int id){ if(!p){ p=++tot; tr[p]={0,0,0}; } int &old=tr[p].id; if(!old){ old=id; return; } int mid=(l+r)>>1; int c=pr(f(mid,id),f(mid,old)); if(c==1||(c==0&&id>1; if(Lmid) seg(tr[p].rc,mid+1,r,L,R,id); } pdi qry(int p,int l,int r,int x){ if(!p) return {-inf,0}; long double res=f(x,tr[p].id); int id=tr[p].id; if(l==r) return {res,id}; int mid=(l+r)>>1; pdi son=(xid)) son={res,id}; return son; } signed main(){ scanf("%d"…