题目链接
题目大意
n个电灯泡 一开始都是关着的 给你m个区间 每个区间有l，r
代表着l，r的灯泡全部开关一次 原来的开变成关 原来的关变成开
问你最后有多少个灯泡
题目思路
1题目到手一看 线段树裸题 光速三发MLE 才发现
ML=8000K
也就是说最多开俩1e6数组
2然后想到 差分 然后最后扫一遍数组
但是数组长度n为1e6 而且t为1e3
但是m是1e3 所以从m入手
3考虑离散化
把m出现过的点计算进去
但是还有一个问题
比如说只出现过 2 4 6 8 这种情况
两次覆盖分别为2-4 和 6-8 你不知道4-6之间有没有覆盖
4所以我们选择将区间化点
即每个点之间再插一个点 最后计算答案时 若该点是插的点 则答案++左右俩点的区间
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4e3+10;
int a[maxn];
int sum[maxn];
int c[maxn];
int n,m,T;
struct xy{int l,r;
}e[maxn];
void init()
{for(int i=1;i<=m*2;i++){a[i]=0;sum[i]=0;c[i]=0;}
}
int main()
{cin>>T;int ti=0;while(T--){cin>>n>>m;init();int t,x,y,k;int cnt=0;for(int i=1;i<=m;i++){cin>>x>>y;a[++cnt]=x;a[++cnt]=y;e[i].l=x;e[i].r=y;}cnt=unique(a+1,a+cnt+1)-a;sort(a+1,a+cnt+1);int num=0;for(int i=1;i<=cnt;i++){c[++num]=a[i];c[++num]=a[i];}for(int i=1;i<=m;i++){int l=lower_bound(c+1,c+num+1,e[i].l)-c;int r=lower_bound(c+1,c+num+1,e[i].r)-c;sum[l]++;sum[r+1]--;}int tmp=0;int ans=0;for(int i=1;i<=num;i++){tmp+=sum[i];if(i%2==0){if(tmp%2==1){ans+=c[i+1]-c[i]-1;}continue;}if(tmp%2==1){ans+=1;continue;}}printf("Case #%d: ",++ti);cout<<ans<<endl;}return 0;
}