2019年icpc上海网络赛 B Light bulbs （分块、差分）

https://nanti.jisuanke.com/t/41399

题目大意:

有n个灯,m次操作,每次修改[l,r]内的灯,(off - on ,on - off),问最后有几盏灯亮着.

换种说法：n个点m个区间，每次区间内的数+1，最后n个点中计数为奇数的点的个数就是答案。

刚开始没注意，直接用线段树写，超内存了。。。。

这题因为外层有个T,并且n太大,还要卡内存，太过分了。

卡数据卡内存，每组样例一重循环都会超时。所以可以分块和对m处理来做。

对m处理的话，仔细想一想，只有区间次数被操作奇数次的话，这个区间操作才有效，所以我们只要把左右端点从小到大排序然后区间求和就行了。

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <string>

 #include <math.h>

 #include <algorithm>

 #include <vector>

 #include <stack>

 #include <queue>

 #include <set>

 #include <map>

 #include <math.h>

 const int INF=0x3f3f3f3f;

 typedef long long LL;

 const int mod=1e9+;

 const int maxn=1e7+;

 using namespace std;

 int a[];

 int main()

 {

     int T;

     scanf("%d",&T);

     for(int k=;k<=T;k++)

     {

         int n,m;

         int l,r;

         scanf("%d %d",&n,&m);

         for(int i=;i<*m;i++)

         {

             scanf("%d %d",&l,&r);

             a[i++]=l;

             a[i]=++r;

         }

         m*=;

         int ans=;

         sort(a,a+m);

 //        for(int i=0;i<m;i++)

 //        {

 //            printf("%d ",a[i]);

 //        }

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

         {

             ans+=a[i]-a[i-];

         }

         printf("Case #%d: %d\n",k,ans);

     }

     return ;

 }

对m下手,注意到:

把每一个端点存起来之后(并且排序),毎两个点之间的区间的亮与否至于左边有关,不包括右边.

所以利用差分的思想,修改 L,R相当于a(L)+1,a(R+1)-1

我们把端点排好序之后,就直接跑一遍m

如果当前为左端点则覆盖层数++(意思就是之后的每个数都多了一个区间覆盖)

如果当前为右端点则覆盖层数--(意思就是之后每个数都少了一个覆盖区间)

因为区间左闭右开,只要为奇数(灯亮),就加上左边右开区间 R-L的值

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <string>

#include <math.h>

#include <algorithm>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <math.h>

const int INF=0x3f3f3f3f;

typedef long long LL;

const int mod=1e9+;

const int maxn=1e7+;

using namespace std;

struct node

{

    int f;

    int id;

    bool friend operator < (node a,node b)

    {

        if(a.id==b.id)

            return a.f<b.f;

        return a.id<b.id;

    }

}pos[];

int main()

{

    int T;

    scanf("%d",&T);

    for(int k=;k<=T;k++)

    {

        int n,m;

        int l,r;

        int cnt=;

        scanf("%d %d",&n,&m);

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

        {

            scanf("%d %d",&l,&r);

            pos[++cnt].id=l;

            pos[cnt].f=;

            pos[++cnt].id=r+;

            pos[cnt].f=;

        }

        int cot=;

        int ans=;

        sort(pos+,pos++cnt);

        for(int i=;i<=cnt-;i++)

        {

            if(pos[i].f)

                cot--;

            else

                cot++;

            if(cot%)

                ans+=pos[i+].id-pos[i].id;

        }

        printf("Case #%d: %d\n",k,ans);

    }

    return ;

}

巴特西

2019年icpc上海网络赛 B Light bulbs （分块、差分）

最新文章

热门文章