线段树解题报告

Alicia ·

更新时间:2024-11-10

· 624 次阅读

H Moving Points
题目链接：https://vjudge.net/contest/358745#problem/H
思路：树状数组维护，类似于树状数组求逆序对+思维（思维量很小）

#include
using namespace std;
const int N = 2e5+9;
typedef long long ll;
struct node{
    ll a,b;
    friend bool operator <(node a,node b){
        return a.a<b.a;
    }
}a[N];
ll b[N];
ll h[N];
ll c1[N],c2[N];
int m,n;
void des(){
    sort(h+1,h+n+1);m=0;
    for(int i=1;i<=n;i++){
        if(i==1||h[i]!=h[i-1]){
            b[++m]=h[i];
        }
    }
}
int query(ll x){
    return lower_bound(b+1,b+m+1,x)-b;
}
int lowbit(int x){
    return x&(-x);
}
void update1(int x,ll v){
    for(int i=x;i<=m;i+=lowbit(i)){
        c1[i]+=v;
    }
//    for(int i=1;i<=m;i++)cout<<c1[i]<<" ";puts("");
}
void update2(int x,ll v){
    for(int i=x;i<=m;i+=lowbit(i)){
        c2[i]+=v;
    }
}
ll query1(ll x){
    ll ans=0;
    for(ll i=x;i;i-=lowbit(i)){
        ans+=c1[i];
    }
    return ans;
}
ll query2(ll x){
    ll ans=0;
    for(int i=x;i;i-=lowbit(i)){
        ans+=c2[i];
    }
    return ans;
}
int main(){
//    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    while(~scanf("%d",&n)){
        m=0;
        memset(c1,0,sizeof c1);
        memset(c2,0,sizeof c2);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i].a);
        }
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i].b);
            h[i]=a[i].b;
        }
        des();
        sort(a+1,a+n+1);
        ll ans=0;
//        for(int i=1;i<=m;i++){
//            cout<<b[i]<<" ";
//        }puts("");
        for(int i=1;i<=n;i++){
            int x=query(a[i].b);
            ll y=query1(x),z=query2(x);
//            cout<<x<<endl;
            ans+=(y*a[i].a-z);
            update1(x,1ll);
            update2(x,a[i].a);
//            cout<<y<<" "<<z<<endl;
        }
        printf("%lld\n",ans);
    }
}

I - Mayor’s posters
题目链接：https://vjudge.net/contest/358745#problem/I
思路：插点离散化+懒惰标记的应用

#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+9;
typedef long long ll;
struct node{
    int l,r;
    int lazy;
}tree[N<>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
}
int L[N],R[N],ans[N];
vectorpoint;
void pushdown(int rt){
    if(tree[rt].lazy!=0){
        tree[rt<<1|1].lazy=tree[rt<=l&&tree[rt].r>1;
    if(l<=mid)change(rt<mid)change(rt<>1;
    query(rt<<1,l,r);
    query(rt<<1|1,l,r);
}
int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        scanf("%d",&n);point.clear();
        for(int i=1;i<=n;i++){
            scanf("%d%d",&L[i],&R[i]);
            point.push_back(L[i]);
            point.push_back(R[i]);
        }
        sort(point.begin(),point.end());
        point.erase(unique(point.begin(),point.end()),point.end());
        int m=point.size();
        for(int i=0;i1){
                point.push_back(point[i+1]-1);
            }
        }
        sort(point.begin(),point.end());
        m=point.size();
        build(1,0,m-1);memset(ans,0,sizeof ans);
        for(int i=1;i<=n;i++){
            int x=lower_bound(point.begin(),point.end(),L[i])-point.begin();
            int y=lower_bound(point.begin(),point.end(),R[i])-point.begin();
            change(1,x,y,i);
        }
        int res=0;query(1,0,m-1);
        for(int i=1;i<=n;i++){
            if(ans[i])res++;
        }
        printf("%d\n",res);
    }
}

J - Atlantis
题目链接：https://vjudge.net/contest/358745#problem/J
思路：课上讲过这里不在赘述，不过要注意c++11要用.f

#include
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define debug puts("*");
const int N=220;
int n,cnt,t=1;
struct node{
    int l,r,cnt;
    double len;
}tree[N<<2];
struct knode{
    double x1,y1,y2;
    int k;
    friend bool operator <(knode a,knode b){
        return a.x1<b.x1;
    }
}line[N];
double raw[N],b[N],val[N];
void discrete(){
    sort(raw+1,raw+2*n+1);
//    rep(i,1,2*n)cout<<raw[i]<<" ";puts("");
    rep(i,1,2*n)
        if(i==1||raw[i]!=raw[i-1])
            b[++cnt]=raw[i];
//    rep(i,1,cnt)cout<<b[i]<<" ";
}
int findx(double x){
    return lower_bound(b+1,b+cnt+1,x)-b;
}
void pushup(int rt,int l,int r){
    if(tree[rt].cnt){
        tree[rt].len=b[r+1]-b[l];
    }
    else if(l!=r){
        tree[rt].len=tree[rt<<1].len+tree[rt<<1|1].len;
    }else tree[rt].len=0;
    return ;
}
void build(int rt,int l,int r){
    tree[rt].l=l,tree[rt].r=r;
    tree[rt].len=0.0;tree[rt].cnt=0;
//    cout<<l<<" "<<r<>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
}
void update(int rt,int l,int r,int x){
    if(l<=tree[rt].l&&tree[rt].r>1;   ///2
    if(l<=mid)update(rt<mid)update(rt<<1|1,l,r,x);
    pushup(rt,tree[rt].l,tree[rt].r);
}
int main(){
    while(~scanf("%d",&n)){
        if(!n)break;
        cnt = 0;     /// 1
        rep(i,1,n){
            double x1,y1,x2,y2;
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            raw[i*2-1]=y1,raw[i*2]=y2;
            line[i*2-1].x1=x1,line[i*2-1].y1=y1,line[i*2-1].y2=y2;
            line[i*2-1].k=1;
            line[i*2].x1=x2,line[i*2].y1=y1,line[i*2].y2=y2;
            line[i*2].k=-1;
        }
        discrete();
        sort(line+1,line+2*n+1);
        double ans=0;
        build(1,1,cnt);
        rep(i,1,2*n){
            ans+=tree[1].len*(line[i].x1-line[i-1].x1);
            update(1,findx(line[i].y1),findx(line[i].y2)-1,line[i].k);
        }
        printf("Test case #%d\nTotal explored area: %.2lf\n\n", t++, ans);
    }
}

K - A Simple Problem with Integers
思路：课上例题，lazy标记应用

#include
#include
#include
using namespace std;
typedef long long ll;
const int N=1e5+9;
struct node{
    ll l,r;
    ll data,add;
}m[N<<2];
ll a[N];
void pushdown(ll rt,ll len){
    if(m[rt].add){
        m[rt<<1].add+=m[rt].add;
        m[rt<<1|1].add+=m[rt].add;
        m[rt<>1)));
        m[rt<>1));
        m[rt].add=0;
    }
}
void build(ll rt,ll l,ll r){
    m[rt].l=l;
    m[rt].r=r;
    m[rt].add=0;
    if(l==r){
        m[rt].data=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    m[rt].data=m[rt<<1].data+m[rt<<1|1].data;
}
void update(ll l,ll r,ll v,ll rt){
    if(l=m[rt].r){
        m[rt].add+=v;
        m[rt].data+=(v*(m[rt].r-m[rt].l+1ll));
        return;
    }
    pushdown(rt,m[rt].r-m[rt].l+1);
    int mid=(m[rt].r+m[rt].l)>>1;
    if(mid>=l)update(l,r,v,rt<<1);
    if(mid<r)update(l,r,v,rt<<1|1);
    m[rt].data=m[rt<<1|1].data+m[rt<=l&&m[p].r>1;
    pushdown(p,m[p].r-m[p].l+1);
    ll ans=0;
    if(mid>=l)ans+=query(l,r,p<<1);
    if(mid<r)ans+=query(l,r,p<<1|1);
    return ans;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    while(m--){
        char c[4];
        scanf("%s",c);
        ll x,y;ll z;
        if(c[0]=='Q'){
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",query(x,y,1));
        }
        else{
            scanf("%lld%lld%lld",&x,&y,&z);
            update(x,y,z,1);
        }
    }
}

L - Black And White
思路：区间合并的典型例题，最好自己写一遍，我写的时候出了太多bug，这个代码还是借用的。。。

#include 
#define LS(a) (a << 1)
#define RS(a) (a << 1 | 1)
#define NS (100005)
using namespace std;
struct N {int l1, r1, m1, l0, r0, m0, tag;} e[NS <> 1;
    Build(L, Mid, LS(a)), Build(Mid + 1, R, RS(a)), pup(a);
}
void Rev(int l, int r, int L = 1, int R = n, int a = 1)
{
    if (l <= L && R > 1;
    if (l  Mid) Rev(l, r, Mid + 1, R, RS(a));
    pup(a);
}
int Query(int l, int r, int L = 1, int R = n, int a = 1)
{
    if (l <= L && R > 1, res = 0;
    if (l  Mid) res = max(res, Query(l, r, Mid + 1, R, RS(a)));
    res = max(res, min(Mid - l + 1, e[LS(a)].r1) + min(r - Mid, e[RS(a)].l1));
    return res;
}
int main(int argc, char const* argv[])
{
    while (~scanf("%d", &n))
    {
        for (int i = 1; i <= n; i += 1) scanf("%d",&arr[i]);
        Build();scanf("%d",&m);
        for (int c = 1, o, l, r; c <= m; c += 1)
        {
            scanf("%d%d%d",&o,&l,&r);
            if (o) Rev(l, r);
            else printf("%d\n", Query(l, r));
        }
    }
    return 0;
}

2019ICPC上海网络赛 - A. Lightning Routing I
网络赛的题，知识点略深可不看，下面有篇博客
https://blog.csdn.net/weixin_44059127/article/details/100941413
思路：动态维护直径+LCA

作者：hrbust_yr

线段树

1024 个赞