2019上海网络赛B_Light bulbs_算法日常[25/100]

题目链接

计蒜客传送门

题意

给你一排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;
}

每天一句叨叨

人生总有很多东西无法挽留,比如走远的时光,比如枯萎的情感;总有很多东西难以割舍,比如追逐的梦想,比如心中的深爱。所以你一定要珍惜眼前。