Light bulbs

题目链接

毒瘤题
又卡时间又卡空间
思路
显然有一个不考虑时限的做法。对于每次操作 $[l,r]$[l,r]，我们都可以把区间 $[0,n-1]$[0,n−1]中的下标 $l,r+1$l,r+1标记加一，然后扫一般前缀和就可以得到应有的答案。
但是显然这个做***T的，复杂度为 $O(T\ast n)$O(T∗n)
我们观察发现，对于 $0-（n-1）$0−（n−1）的数字我们只需要关注m次操作的端点，所以可以采取离散化。
AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
int tot[2005];
struct node{
    int Case;
    int time;
}flag[maxn];
int main(){
    int t, kase = 0;
    scanf("%d", &t);
    while(t--){
    ++kase;
// map<int, int>flag;
	int n, m, cnt = 0;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++){
		int l, r;
		scanf("%d%d", &l, &r);
		tot[++cnt] = l;
		tot[++cnt] = r + 1;
		if(flag[l].Case != kase){
			flag[l].time = 1;
			flag[l].Case = kase;
		}
		else{
			flag[l].time++;
		}
		if(flag[r + 1].Case != kase){
			flag[r + 1].time = 1;
			flag[r + 1].Case = kase;
		}
		else{
			flag[r + 1].time++;
		}
	}
	sort(tot + 1, tot + cnt + 1);
	int Num = unique(tot + 1, tot + cnt + 1) - (tot + 1);
	//for(int i = 1; i <= m; i++)
	int sum = 0;
	int ans = 0;
	for(int i = 1; i <= Num; i++){
		sum = sum + flag[tot[i]].time;
		if(sum % 2){
			if(i != Num)
				ans += tot[i + 1] - tot[i];
			else
				ans++;
		}
	}
	printf("Case #%d: %d\n", kase, ans);
    }
    return 0;
}