题目链接
计蒜客传送门
题意
给你一排N个全灭的灯泡，然后进行M次区间翻转，T组测试
- 1≤T≤1000
- 1≤N≤$10^6$
- 1≤M≤1000
- 0≤$L_i$ ≤$R_i$ ≤N−1
题解
- 因为是多次区间修改，然后求区间的特性，我们可以很自然地想到使用差分+前缀和或者线段树
- 不过这里发现8192K，N为$10^6$,$10^6$的int是4*$10^6$Byte=4*$10^3$K.然后线段树要开两倍N(节点2*N),而且一般是一个struct结构(一般几个int)，而非一个int，所以线段树否决
- 然后求前缀和O(T*N)在$10^9$量级，时间限制为1s，所以我们要观察M在1000的量级，所以可以通过离散化来解决
- 注意，这题超级卡时间，所以使用快读(独立缓冲的cin T了)以及各位置用完及时归0而非使用memset
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1e6+10;
int a[M],T,n,m,l,r,ans,sum;
vector<int> b;
inline int read() {
int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);
T = read();
int kase = 1;
while(T--){
n = read(),m = read();
if(!b.empty()) b.clear();
ans = 0,sum = 0;
while(m--){
l = read(),r = read();
l++,r++;
a[l]--;a[r+1]++;
b.push_back(l),b.push_back(r+1);
}
// 先排序，因为unique只从左到右顺序查重，然后unique得到最后一个被删除的位置，用erase搽除尾部
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()),b.end());
int sz = b.size();
sum+=a[b[0]];
a[b[0]] = 0;
for(int i=1;i<sz;i++){
if(sum&1) ans+=b[i]-b[i-1];
sum+=a[b[i]];
a[b[i]] = 0;
}
if(sum&1) ans+=n+1-b[sz-1];
printf("Case #%d: %d\n",kase++,ans);
}
return 0;
}
|
每天一句叨叨
人生总有很多东西无法挽留，比如走远的时光，比如枯萎的情感;总有很多东西难以割舍，比如追逐的梦想，比如心中的深爱。所以你一定要珍惜眼前。