hiho152周 - 水题区间问题

题目链接

给定两个区间集合 A 和 B，其中集合 A 包含 N 个区间[ A₁, A₂ ], [ A₃, A₄ ], ..., [ A_2N-1, A_2N ]，集合 B 包含 M 个区间[ B₁, B₂ ], [ B₃, B₄ ], ..., [ B_2M-1, B_2M ]。求 A - B 的长度。

例如对于 A = {[2, 5], [4, 10], [14, 18]}, B = {[1, 3], [8, 15]}, A - B = {(3, 8), (15, 18]}，长度为8。

第一行：包含两个整数 N 和 M (1 ≤ N, M ≤ 100000)。

第二行：包含 2N 个整数 A₁, A₂, ..., A_2N (1 ≤ A_i ≤ 100000000)。

第三行：包含 2M 个整数 B₁, B₂, ..., B_2M (1 ≤= B_i ≤ 100000000)。

---------------------------------------------------------------------------------------------------------

一看是区间的问题，就写了个线段树800msAC了，可是看了分析才知道大材小用了，线段树适合多次修改多次询问的，而这个只是一次询问也没动态修改，

所以直接：排序然后用两个计数器记录每个区间起点处A和B的覆盖情况就行了。

线段树版 823ms:

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <cmath>

#include <vector>

#include <string>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define MAX(a,b) ((a)>=(b)?(a):(b))

#define MIN(a,b) ((a)<=(b)?(a):(b))

#define OO 0x0fffffff

using namespace std;

typedef long long LL;

const int N = 100100;

struct Node{

     int l,r;

     int lazy;

     Node(){lazy=0;}

     int mid(){return (l+r)>>1;}

};

Node segtree[N*12];

int uni0[N*4],uni1[N*4],flag[N*4];

int n,m;

void build(int id,int l,int r){

     segtree[id].l = l;

     segtree[id].r = r;

     if(l==r) return ;

     int mid = (l+r)>>1;

     build(id*2+0,l,mid);

     build(id*2+1,mid+1,r);

}

void modify(int id,int spos,int epos,int tag){

     if(segtree[id].l==spos&&segtree[id].r==epos){

        segtree[id].lazy|=tag;

        return ;

     }

     if(segtree[id].lazy&tag) return ;

     if(segtree[id].lazy){

        segtree[id*2+0].lazy|=segtree[id].lazy;

        segtree[id*2+1].lazy|=segtree[id].lazy;

        segtree[id].lazy = 0;

     }

     int mid = segtree[id].mid();

     if(epos<=mid){

        modify(id*2+0,spos,epos,tag);

     }

     else if(spos>mid){

        modify(id*2+1,spos,epos,tag);

     }

     else{

        modify(id*2+0,spos,mid,tag);

        modify(id*2+1,mid+1,epos,tag);

     }

}

void traverse(int id){

     if(segtree[id].l==segtree[id].r) {

        flag[segtree[id].l]=segtree[id].lazy;

        return ;

     }

     segtree[id*2+0].lazy|=segtree[id].lazy;

     segtree[id*2+1].lazy|=segtree[id].lazy;

     traverse(id*2+0);

     traverse(id*2+1);

}

int main(){

    cin>>n>>m;

    int cnt=(m+n)*2;

    for(int i=0;i<cnt;i++) cin>>uni0[i];

    map<int,int> refl;

    memcpy(uni1,uni0,sizeof(int)*cnt);

    sort(uni1,uni1+cnt);

    int maxn = unique(uni1,uni1+cnt)-uni1;

    for(int i=0;i<maxn;i++) { refl[uni1[i]] = i; }

    build(1,0,maxn-2);

    for(int i=0;i<n;i++) {

       if(uni0[i*2+0]==uni0[i*2+1]){continue;}

       int l = refl[uni0[i*2+0]];

       int r = refl[uni0[i*2+1]];

       if(l>r) swap(l,r);

       modify(1,l,r-1,1);

    }

    for(int i=n;i<m+n;i++){

       if(uni0[i*2+0]==uni0[i*2+1]){continue;}

       int l = refl[uni0[i*2+0]];

       int r = refl[uni0[i*2+1]];

       if(l>r) swap(l,r);

       modify(1,l,r-1,2);

    }

    traverse(1);

    long long ans = 0;

    for(int i=0;i<maxn-1;i++){

        if(flag[i]==1){

            ans+=(uni1[i+1]-uni1[i]);

        }

    }

    printf("%lld\n",ans);

    return 0;

}

简单版 104ms

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <cmath>

#include <vector>

#include <string>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define MAX(a,b) ((a)>=(b)?(a):(b))

#define MIN(a,b) ((a)<=(b)?(a):(b))

#define OO 0x0fffffff

using namespace std;

typedef long long LL;

const int N = 100100*4;

struct NODE{

    int value;

    int type;

    friend bool operator<(const NODE &a,const NODE &b){

        return a.value<b.value;

    }

};

NODE ps[N];

int cnta,cntb;

void check(int type){

     switch(type){

         case 0 : cnta++; break;

         case 1 : cnta--; break;

         case 2 : cntb++; break;

         case 3 : cntb--; break;

     }

}

int main(){

    int n,m,cnts;

    cin>>n>>m;

    cnts = m+n;

    for(int i=0;i<n;i++){

        scanf("%d%d",&ps[i*2+0].value,&ps[i*2+1].value);

        ps[i*2+0].type = 0;

        ps[i*2+1].type = 1;

    }

    for(int i=n;i<cnts;i++){

        scanf("%d%d",&ps[i*2+0].value,&ps[i*2+1].value);

        ps[i*2+0].type = 2;

        ps[i*2+1].type = 3;

    }

    cnts<<=1;

    std::sort(ps,ps+cnts);

    int ans = 0;

    cnta = cntb = 0;

    check(ps[0].type);

    int lpos = ps[0].value;

    for(int i=1;i<cnts;i++){

       if(ps[i].value!=lpos){

          if((cnta)&&(!cntb)){

            ans += ps[i].value-lpos;

          }

          lpos = ps[i].value;

       }

       check(ps[i].type);

    }

    printf("%d\n",ans);

    return 0;

}

巴特西

hiho152周 - 水题区间问题

最新文章

热门文章

巴特西

hiho152周 - 水题 区间问题

最新文章

热门文章

hiho152周 - 水题区间问题