P1496 火烧赤壁-离散化

· · 个人记录

校门外的树扩展

离散化学习：oiwiki

方法一：离散化后用校门外的树方法


#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n;
int x[N<<1];
int a[N],b[N],c[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        x[2*i-1]=a[i];
        x[2*i]=b[i];
    }
    sort(x+1,x+1+2*n);
    int m=unique(x+1,x+2*n+1)-x-1;
    for(int i=1;i<=n;i++)
    {
        int L=lower_bound(x+1,x+m+1,a[i])-x;
        int R=lower_bound(x+1,x+m+1,b[i])-x;
        for(int j=L;j<R;j++)c[j]+=1;

    }
    int h=0,t=0,ans=0;
    for(int i=1;i<=m;i++)
    {
        if(!c[i-1]&&c[i])ans+=1;
        if(c[i]&&c[i-1])  ans+=x[i]-x[i-1];
        else if(c[i-1]&&!c[i]) ans+=x[i]-x[i-1]-1;
    }
    cout<<ans;

    return 0;
 }

方法二 ：利用前缀和，区间修改，再求前缀和

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n;
int x[N<<1];
int a[N],b[N],c[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        x[2*i-1]=a[i];
        x[2*i]=b[i];
    }
    sort(x+1,x+1+2*n);
    int m=unique(x+1,x+2*n+1)-x-1;
    for(int i=1;i<=n;i++)
    {
        int L=lower_bound(x+1,x+m+1,a[i])-x;
        int R=lower_bound(x+1,x+m+1,b[i])-x;
    //  for(int j=L;j<R;j++)c[j]+=1;
         c[L]++,c[R]--;

    }

    int h=0,t=0,ans=0;
    for(int i=1;i<=m;i++)
    {   c[i]+=c[i-1];
        if(!c[i-1]&&c[i])ans+=1;
        if(c[i]&&c[i-1])  ans+=x[i]-x[i-1];
        else if(c[i-1]&&!c[i]) ans+=x[i]-x[i-1]-1;
    }

    cout<<ans;

    return 0;
 }

最后的处理还可以只记录起点和终点

int h=0,t=0,ans=0;
    for(int i=1;i<=m;i++)
    {   c[i]+=c[i-1];
        if(!c[i-1]&&c[i])h=x[i];

        else if(c[i-1]&&!c[i]) t=x[i],ans+=t-h;
    }