ZR 集训 Day2 – 线段树进阶

ooliver 发布于 14 小时前 76 次阅读 OI

AI 摘要

从体育课上的区间翻转，到动态插入直线的最值查询，再到把导弹碰撞问题变成逆序对……这些看似毫不相干的难题，背后的本质竟都是线段树的精巧进阶。

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;
}