ZR 集训 Day2 – 线段树进阶

ooliver 发布于 2026-07-18 300 次阅读 OI

AI 摘要

线段树还能这样玩？动态开点暴力过题，李超树在线硬刚函数最值，更有两道物理题的神奇转化——导弹碰撞变身逆序对，篮球轨迹算起一次函数，集训第二天直接打开新世界。

ZR 集训 Day2 - 线段树进阶

CF915E Physical Education Lessons

动态开点板子，代码：

C++
#include<bits/stdc++.h>
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<=R){
        tr[p].lazy=tag;
        tr[p].sum=tag*(r-l+1);
        return;
    }
    int mid=l+r>>1;
    pushdown(p,l,r);
    if(L<=mid) 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;i<=q;i++){
        int l,r,k;
        cin>>l>>r>>k;
        if(k==1){
            add(rt,1,n,l,r,0);
            cout<<tr[rt].sum<<"\n";
        }
        else{
            add(rt,1,n,l,r,1);
            cout<<tr[rt].sum<<"\n";
        }
    }
    return 0;
}

P4097 【模板】李超线段树 / [HEOI2013] Segment

李超线段树模板，处理的是在线加入若干一次函数并在线询问某横坐标上最大的函数值。

详情看代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
const double eps=1e-9;
#define lc p<<1
#define rc p<<1|1
#define pdi pair<double,int>
#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[N<<2];

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&&x<tr[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&&x<tr[p].ln)) upd(lc,l,mid,x);
    if(cr==1||(cr==0&&x<tr[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].r<=r){
        upd(p,tr[p].l,tr[p].r,id);
        return;
    }
    int mid=tr[p].l+tr[p].r>>1;
    if(l<=mid) 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(x<=mid) 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;i<=n;i++){
        cin>>op;
        if(op==0){
            cin>>k;
            k=(k+ans-1)%39989+1;
            ans=qry(1,k).sc;
            cout<<ans<<"\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(x2<x1) swap(x1,x2),swap(y1,y2);
            add(x1,y1,x2,y2);
        }
    }
    return 0;
}

P8593 「KDOI-02」一个弹的投

根据物理知识，知道不在同一纵坐标的导弹是不会碰撞的。

所以根据纵坐标分类，就变成了找逆序对的问题，记得要离散化。

代码：

C++
#include<bits/stdc++.h>
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 operator<(const node b)const{
        return y<b.y;
    }
}q[N];
struct BIT{
    int tr[N];
    void add(int x,int k){
        for(int i=x;i<=n;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;

map<int,vector<node>> mp;

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;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;i<=n;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;i<=n;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];
    cout<<sum;
    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<bits/stdc++.h>
using namespace std;

#define pdi pair<long double,int>
#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<old)) swap(old,id);
    if(l==r) return;
    int cl=pr(f(l,id),f(l,old));
    if(cl==1||(cl==0&&id<old)) upd(tr[p].lc,l,mid,id);
    int cr=pr(f(r,id),f(r,old));
    if(cr==1||(cr==0&&id<old)) upd(tr[p].rc,mid+1,r,id);
}

void seg(int &p,int l,int r,int L,int R,int id){
    if(!p){ p=++tot; tr[p]={0,0,0}; }
    if(L<=l&&r<=R){ upd(p,l,r,id); return; }
    int mid=(l+r)>>1;
    if(L<=mid) seg(tr[p].lc,l,mid,L,R,id);
    if(R>mid) 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=(x<=mid)?qry(tr[p].lc,l,mid,x):qry(tr[p].rc,mid+1,r,x);
    if(pr(son.fi,res)==-1||(pr(son.fi,res)==0&&son.sc>id)) son={res,id};
    return son;
}

signed main(){
    scanf("%d",&m);
    char op[10];
    while(m--){
        scanf("%s",op);
        if(op[0]=='a'){
            double a,v,l,r;
            scanf("%lf%lf%lf%lf",&a,&v,&l,&r);
            int A=round(a*1000.0),V=round(v*1000.0),tl=round(l*1000.0),trr=round(r*1000.0);
            ++idx;
            long double L_val=tl/1000.0L,V_val=V/1000.0L,A_val=A/1000.0L;
            k[idx]=g*L_val+V_val;
            b[idx]=-0.5L*g*L_val*L_val-V_val*L_val+A_val;
            seg(root,L,R,tl,trr,idx);
        }
        else{
            double x;
            scanf("%lf",&x);
            int X=round(x*1000.0);
            pdi res=qry(root,L,R,X);
            if(res.fi<-1e28L) printf("Undefined\n");
            else printf("%.6Lf\n",res.fi-0.5L*g*(X/1000.0L)*(X/1000.0L));
        }
    }
    return 0;
}