洛谷P1496火烧赤壁题解——离散化，差分找规律完成

传送门：烧壁

知识点

离散化或差分找规律
主要是想考察离散化，但隐藏了一些性质

题目大意：

给定n个区间[l_i,r_i]进行涂色，求最后涂色的区间长度（不是点的长度）。
其中 1 ≤ n ≤ 2 × 1 0 4 , − 2 31 ≤ l i , r i ≤ 2 31 1 \leq n\leq 2 \times 10^4,-2^{31}\leq l_i ,r_i \leq 2^{31} 1≤n≤2×104,−231≤li​,ri​≤231

题目解读与分析

之所以给这么大的区间范围说白了就是不打算让你枚举，但是我们又观察到原轴上的节点数其实
至多有$N<<1$个，所以本题符合数量少，数值大且满足单调性的特点，我们考虑离散化进行缩点。
就会将区间范围缩成 [ 1 , 4 × 1 0 4 ] [1,4 \times 10^4] [1,4×104]这下就可以$O(n)$枚举了。
总复杂度 T = O ( n 2 ) T = O(n ^ 2) T=O(n2)
参考代码：

#include
using namespace std;
const int N = 2e4 + 10;
int n,x[N],y[N];
long long c[N << 1];
int bj[N<<1],cnt = 0;
long long ans = 0;
int find(int x)
{int l = 1,r = cnt;int mid; while(l < r){mid = (l + r) >> 1;if(c[mid] < x) l = mid + 1;else           r = mid;}return l;
}
signed main()
{scanf("%d",&n);for(int i = 1;i <= n; i++){scanf("%d %d",&x[i],&y[i]);c[++cnt] = 1ll * x[i],c[++cnt] = 1ll * y[i];}sort(c + 1,c + cnt + 1);cout << cnt;cnt = unique(c + 1,c + cnt + 1) - c;cout << cnt <for(int i = 1;i <= n; i++){int a = find(x[i]),b = find(y[i]);//先将值赋出来避免多次查找！！！！！！for(int j = a;j < b; j++)bj[j] = 1;}for(int i = 1;i < cnt; i++){if(bj[i] == 1) ans += (c[i + 1] - c[i]);}cout << ans << '\n';return 0;
}

这里特殊强调一下：

手写查找函数时，如果枚举时加入会多次调用，复杂度很高！应该先求出来位置之后然后赋值给一个普通变量再做枚举

差分以及特殊做法

也算是很奇妙，O(n^2)都能较快的过掉这些数据，说明数据还是有点水的，但是我们并不能满足这个复杂度，于是打算观察序列的一些性质，我们发现对于任意两个区间，如果我们交换他们的终点，那么所覆盖的区域是不会变的（本来前提是$end1,end2>st1,st2$，不过其实如果$end1<st2$，这个将区间表示的含义可以看为“负的”，意义为“不会覆盖”，所以可以不用管）。

差分

我们用差分的思想就很好懂。首先我们要将区间长度看成点的长度，就可以认为区间开头有贡献，结尾没有贡献。然后因为如果是差分的话就无所谓起点和终点的相对位置，即只是在起点位置上加上1，在终点位置减去1，所以才导致顺序没有变化，所以这里索性先用差分做这道题。另外：鉴于差分做标记仍需要在轴上从左到右走一遍，故我们还是要离散化一下，找到连续区间后再对应为实际长度。
求答案部分也是$O(N)$，但查找部分为$O(NlogN)$，总复杂度$T=O(NlogN)$
eg:
pos:1 2 3 4 5 6 7
val: 0 0 0 0 0 0 0 st1=2,ed1=4,st2=1,ed2=3
del: 0 1 1 -1 -1 0
val: 0 1 2 1 0 0 0 长度为3满足
差分基础：

#include
using namespace std;
const int N = 2e4 +10;
int n,l[N],r[N],b[N<<1],tot = 0,c[N<<1];
int Read()
{int x = 0,k = 1;char ch = getchar();while(!isdigit(ch)) {if(ch =='-') k=  -1;ch = getchar();}while(isdigit(ch)) {x = (x << 3)+(x <<1) + ch - '0';ch = getchar();}return x * k;
}
int find(int x)
{int l = 1,r = tot,mid;while(l < r){mid = (l + r) >> 1;if(b[mid] < x) l = mid + 1;else 	r = mid;}return l;	
}
int main()
{n = Read();for(int i = 1;i <= n; i++)b[++tot] = l[i] = Read(),b[++tot] = r[i] = Read();sort(b + 1,b + 2 * n + 1);tot = unique(b + 1,b + 2 * n + 1) - b - 1;for(int i = 1;i <= n; i++){c[find(l[i])]++,c[find(r[i])]--;}for(int i = 1;i <= tot; i++){c[i] += c[i - 1];}int h = 0,t = 0;//要存连续的起点和终点int ans = 0;for(int i = 1;i <= tot; i++){if(!h and c[i] > 0) h = i;if(h and t and c[i] > 0) ans += b[t] - b[h],h = i,t = 0;if(h and !t and !c[i]) t = i;}ans += b[t] - b[h];cout << ans;return 0;
}

特殊技巧

刚才我们提到了，从差分的角度来分析，我们交换两个区间的终点是没有问题的，既然如此，我们能不能将整个序列看做从头到尾（即按大小排序一下后）依次匹配的n个区间，这样看来是否就要简单许多？
即$sort(st+1,st+n+1);sort(ed+1,ed+n+1）$然后依次对应
那么我们已经排好后，单独考虑一个区间的贡献就是其长度，且对于相邻的两个区间最多只有一部分相交。而所谓相交，其实就是$st[i+1]<ed[i]$，那么只要将重复的长度减去就好了。
所以就能$O(n)$求出答案了，因为排序的复杂度是$O(Nlog2N)$所以总复杂度就为$O(Nlog2N）$
完整代码(短小精悍)：

#include
using namespace std;
const int N=2e4+10;
int n,a[N],b[N];
long long l=0;
int main()
{cin>>n;int st,ed;for(int i=1;i<=n;i++){scanf("%d%d",&st,&ed);a[i]=st;b[i]=ed;}sort(a+1,a+n+1);sort(b+1,b+n+1);for(int i=1;i<=n;i++){l+=b[i]-a[i];//计算单个区间贡献if(i<n)if(a[i+1]<b[i])//两区间有重复片段l -= b[i] - a[i+1];}cout << l << '\n';
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！