2019上海ICPC网络赛 B. Light bulbs【差分+思维】

ゞ浴缸里的玫瑰 2024-04-19 09:11 30阅读 0赞

题库链接：[https://nanti.jisuanke.com/t/41399][https_nanti.jisuanke.com_t_41399]

题意：n个灯泡，初始关闭，每次将一个区间翻转，问你最后有多少灯泡是打开的。

思路：题目n范围较大，操作次数较小，所以我们考虑对区间进行操作。利用差分的思想，将区间端点都压入一个队列里，按照x轴排序，然后当sum为奇数时可以确定是打开状态，所以就是当前点减去上次的端点就是符合条件的灯泡数目。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define ls rt << 1
    #define rs rt << 1|1
    #define mid ((l + r) >> 1)
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    const int maxn = 305;
    const int mod = 1e9 + 7;
    vector<pair<int, int> > v;
    
    int main()
    {
        int t, t1 = 1;
        scanf("%d", &t);
        while(t--)
        {
            v.clear();
            int n, m;
            scanf("%d%d", &n, &m);
            for(int i = 1; i <= m; ++i)
            {
                int l, r;
                scanf("%d%d", &l, &r);
                v.push_back({l, 1});
                v.push_back({r + 1, -1});
            }
            sort(v.begin(), v.end());
            int ans = 0, last = 0, sum = 0;
            for(auto x : v)
            {
                if(sum & 1)
                {
                    ans += x.first - last;
                }
                last = x.first;
                sum += x.second;
            }
            if(sum & 1) ans += n - last;
            printf("Case #%d: %d\n", t1++, ans);
        }
        return 0;
    }

[https_nanti.jisuanke.com_t_41399]: https://nanti.jisuanke.com/t/41399