病毒扩散题解

题解1：AC
举个例子，比如有4个线段，我们的是。。那么在叠加后如图：

通过例子我们可以知道我们需要看红色线段与多少个线段是“联通”的，这就是我们要找的答案。那么如何找这个联通的个数呢？我们可以贪心的去找。按照左端点从小到大排序，维护右界的最大值，我们就可以知道每一坨连续的区间包含了多少个线段，再看的线段在哪一坨里面就OK。时间复杂度，空间复杂度。

class Solution {
public:
    int CatchVirus(int Personid, vector<Point>& PeoplePosition) {
        // write code here
        int n = PeoplePosition.size();
        Point inf = PeoplePosition[Personid];
        sort(PeoplePosition.begin(), PeoplePosition.end(), [](Point& a, Point& b) {return a.x < b.x; });
        int r = -1, cnt = 0, fg = 0;
        for (int i = 0; i < n; i++) {
            if (PeoplePosition[i].x > r) {
                if (fg == 1) break;
                cnt = 1;
                r = PeoplePosition[i].y;
            }
            else r = max(r, PeoplePosition[i].y), cnt++;
            if (PeoplePosition[i].x == inf.x&& PeoplePosition[i].y == inf.y) fg = 1;
        }
        return cnt;
    }
};

解法2：AC
举个例子，比如有4个线段，我们的Personid是0。[1,2],[2,3],[4,5],[6,6]。那么在叠加后如图：

通过例子我们可以知道我们需要看红色线段与多少个线段是“联通”的，这就是我们要找的答案。那么如何找这个联通的个数呢？还有一种方法我们可以用线段树区间覆盖。但是需要注意的是在线段树中与是相连的，并不满足题目要求，所以我们得以0.5为最小刻度，这样不管是在线段树中还是题目中都是一致单调。所以我们只需要线段树区间覆盖。紧接着看所在的线段向左向右最多能延申到哪里去，把所能到达的部分全部标记为1，然后求一次前缀和。之后我们只需要判断一下每一根线段里面的区间和(用前缀和做差求解)是否＞0来统计答案即可。因为线段的，最多可以到达，（但是真正有用的又只有线段的两个端点）所以这里我们再离散化下即可。时间复杂度，空间复杂度。

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N=3000010;
bool add[N<<2],a[N];
int b[N],l[N/6],r[N/6];
vector<int>v;
void get(int l,int r,int rt) {//获取区间覆盖后的结果
    if (l==r) {a[l]=add[rt];return;}
    if(add[rt]) add[rt<<1|1]=add[rt<<1]=add[rt];
    int m=(l+r)>>1;
    get(lson),get(rson);
}
void edit(int L,int R,int l,int r,int rt) {//线段树区间覆盖
    if (L<=l&&r<=R) {add[rt]=1;return;}
    int m=(l+r)>>1;
    if(L<=m) edit(L,R,lson);
    if(m<R) edit(L,R,rson);
}
class Solution {
public:
    int CatchVirus(int Personid, vector<Point>& PeoplePosition) {
        // write code here
        int n=PeoplePosition.size();
        for(int i=0;i<n;i++) {//以0.5作为最小单位进行离散化，因为double不好处理所以这里我们*2效果一样
            v.push_back(PeoplePosition[i].x*2);
            v.push_back(PeoplePosition[i].x*2+1);
            v.push_back(PeoplePosition[i].x*2-1);
            v.push_back(PeoplePosition[i].y*2);
            v.push_back(PeoplePosition[i].y*2-1);
            v.push_back(PeoplePosition[i].y*2+1);
        }
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());
        int sz=v.size();
        for(int i=0;i<n;i++) {
            l[i]=lower_bound(v.begin(),v.end(),PeoplePosition[i].x*2)-v.begin()+1;//获取离散化后的L
            r[i]=lower_bound(v.begin(),v.end(),PeoplePosition[i].y*2)-v.begin()+1;//获取离散化后的R
            edit(l[i],r[i],1,sz,1);//区间覆盖
        }
        get(1,sz,1);//获取区间覆盖后的答案
        int L=lower_bound(v.begin(),v.end(),PeoplePosition[Personid].x*2)-v.begin()+1;
        int R=lower_bound(v.begin(),v.end(),PeoplePosition[Personid].y*2)-v.begin()+1;
        for(int i=L;i<=R;i++) b[i]=1;
        for(;L&&a[L];L--) b[L]=1;//Personid线段最左能到达哪里
        for(;R<=sz&&a[R];R++) b[R]=1;//Personid线段最右能到达哪里
        for(int i=1;i<=sz;i++) b[i]+=b[i-1];//求前缀和
        int ans=0;
        for(int i=0;i<n;i++) 
            if(b[r[i]]-b[l[i]-1]>0) ans++;//如果Personid能到达所在线段
        return ans;
    }
};