牛客练习赛34 C little w and Segment Coverage(差分或者线段树)

题意：

思路：

首先，我们可以简单的得到，那些重复覆盖的点我们肯定是不能选的，我们要选的肯定是那些只被覆盖过一次的点，那么现在的问题就到了我们如何快速的找到那些只被覆盖过一次的点？

思路1：我们根据区间信息建一棵线段树，之后查询他的叶子节点的权值是不是1，复杂度是o(logn)。

思路2：根据差分数组，利用差分数组我们可以直接O(n)的知道叶子节点的权值。

之后我们要开始枚举这些只被覆盖过一次节点的那些边，之后找到一个最小值就好了，那么怎么找呢？

思路1：线段树，我们查询节点权值为1的那些点，看他在那一条边上，之后找到删除最多点的那条边是多少。

思路2：还是差分得到第i条边的可以删除的权值是多少就好了

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
pair<int,int>P[maxn];
struct seg
{
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    int sum[maxn<<2];
    int lazy[maxn<<2];
    void pushup(int rt)
    {
        sum[rt] = sum[rt<<1] + sum[rt<<1|1];
    }
    void pushdown(int l,int r,int rt)
    {
        if(lazy[rt])
        {
            int m = (l+r)>>1;
            lazy[rt<<1] += lazy[rt];
            lazy[rt<<1|1] += lazy[rt];
            sum[rt<<1] += lazy[rt] * (m-l+1);
            sum[rt<<1|1] += lazy[rt] *(r-m);
            lazy[rt] = 0;
        }
    }
    void build(int l , int r,int rt)
    {
        lazy[rt] = 0;
        sum[rt] = 0;
        if(l == r) return ;
        int m = (l+r)>>1;
        build(lson);
        build(rson);
        pushup(rt);
    }
    void update(int L,int R,int val,int l,int r,int rt)
    {
        if(L <= l && R >= r)
        {
            sum[rt] += (r-l+1)*val;
            lazy[rt] += val;
            return ;
        }
        pushdown(l,r,rt);
        int m = (l+r)>>1;
        if(L <= m) update(L,R,val,lson);
        if(R > m) update(L,R,val,rson);
        pushup(rt);
    }
    void print(int l,int r,int rt)
    {
        if(l == r) {printf("%d %d %d\n",l,r,sum[rt]);return;}
        int m = (l+r)>>1;
        pushdown(l,r,rt);
        print(lson);
        print(rson);
    }
    int query(int pos,int l,int r,int rt)
    {
        if(l == r) return sum[rt];
        pushdown(l,r,rt);
        int m = (l+r)>>1;
        int ret = 0;
        if(pos <= m) return query(pos,lson);
        else return query(pos,rson);
    }
}tree,tree1;
int ans[maxn];
int main()
{
    int n , m , L,R;
    scanf("%d%d",&n,&m);
    tree.build(1,n,1);
    tree1.build(1,n,1);
    for(int i = 1 ; i <= m ; i++)
    {
        scanf("%d%d",&L,&R);
        tree.update(L,R,1,1,n,1);
        tree1.update(L,R,i,1,n,1); // 建两颗线段树，第一颗的意思是L,R这个区间被覆盖了一遍，第二颗线段树的意思是由第i条边覆盖了L,R区间
    }
    int res = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        int x = tree.query(i,1,n,1);
        if(x == 0) res++; // 如果是0，我们要记录下来哪些从来没有被覆盖过的点
        else if(x == 1) ans[tree1.query(i,1,n,1)] ++; // 如果这个点只被覆盖过一次，那么找到他是被哪条边覆盖的
    }
    int pos = 1;
    for(int i = 1 ; i <= m ; i++)
    {
        if(ans[i] <=  ans[pos]) pos = i;
    }
    cout<<pos<<" "<<ans[pos]+res<<endl;
}

差分：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int D[maxn];
int l[maxn] , r[maxn];
int main()
{
    int n ,m;
    scanf("%d%d",&n,&m);
    for(int i = 0 ; i < m ; i++)
    {
        int L,R;scanf("%d%d",&l[i],&r[i]);
        D[l[i]]++;D[r[i]+1]--;
    }
    for(int i = 1 ; i <= n ; i++) D[i] += D[i-1];
    int res = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        if(D[i] == 0 ) res++; // 查看哪些边从来都没有被覆盖过
        else if(D[i] != 1) D[i] = 0; // 那些被覆盖过不止一次的边我们可以忽略掉
        D[i] += D[i-1];
    }
    int ans = 0 , pos = 0;
    for(int i = 0 ; i < m ; i++)
    {
        if(D[r[i]] - D[l[i]-1]  <= D[r[pos]] - D[l[pos] - 1]) pos = i; // 得到删除第i条可以获得的权值
    }
    cout<< (pos+1) << " " << (D[r[pos]] - D[l[pos] -1]) + res <<endl;
}

牛客练习赛34 C little w and Segment Coverage(差分或者线段树)

相关推荐