Case 1.
本题其实不难,直接模拟就可以了。时间复杂度: (O(L imes M))
Case 2.
考虑一个简单的增强:把原来的:
改成:
现在我们就不可以直接模拟了,显然考虑一个 (L log L) 级别 的做法。
显然,本题是区间操作,和线段树密不可分。
“砍树”的操作可以视为区间 (-1) . 但困难的地方是,如果一个区间多次减(1),只需要减(1)次。
我们对每个区间记录一个 (tag) ,(tag) 只会是 (-1) 和 (0).
(-1) 则表示该区间整个被 (-1) ;(0) 则表示该区间还有没被减过的。
那么,我们区间修改的时候, 只要当前区间的标记是(-1)就直接停止;如果包含则标上(-1)然后走人;否则一直递归到最底层。
修改的时间复杂度: (O(M log L)).
修改是解决了,那怎么查询结果呢? 我们并没有一个区间和之类的东西啊……
下面我们用一个变量 (s) 表示被 (-1) (也就是被砍的树)的个数。
从根开始走,只要当前区间的标记是(-1),就直接统计掉,停止;否则一直走到最底层。
然后最后答案就是 (L-s+1). (不要忘记 (0) )
那么你会问了,时间复杂度大概是多少呢?
其实这和查询区间和是一样的,都是将一个区间拆成若干个小区间,因此查询的时间复杂度是(O(log L)).
那么,线段是完美地实现了本题,其时间复杂度为:
(O(M log L + log L) = O(M log L)).
注:请不要忘记 (0,L) 才是根维护的区间。而不是 (1,L) .
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+1;
#define L (i<<1)
#define R (i<<1)+1
inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
struct tree{
int l,r,tag;
};
tree t[N<<2];
int n,m;
inline void build_tree(int i,int l,int r) {
t[i].l=l; t[i].r=r; t[i].tag=0;
if(l==r) return;
int mid=(l+r)>>1;
build_tree(L,l,mid);
build_tree(R,mid+1,r);
}
inline void change(int i,int l,int r) {
// printf("%d %d %d %d %d %d
",i,t[i].l,t[i].r,l,r,t[i].tag);
if(t[i].tag==-1) return;
if(l<=t[i].l && t[i].r<=r) {t[i].tag=-1;return;}
if(t[i].l==t[i].r) return;
int mid=(t[i].l+t[i].r)>>1;
if(l<=mid) change(L,l,r);
if(r>mid) change(R,l,r);
}
int s=0;
inline void query(int i,int l,int r) {
// printf("%d %d %d %d
",i,l,r,t[i].tag);
if(t[i].tag==-1) {s+=r-l+1;return;}
if(l==r) return; int mid=(l+r)>>1;
if(l<=mid) query(L,l,mid);
if(r>mid) query(R,mid+1,r);
}
int main(){
n=read(),m=read();
build_tree(1,0,n);
while(m--) {
int x=read(),y=read();
change(1,x,y);
} query(1,0,n);
printf("%d
",n-s+1);
return 0;
}
Case3.
下面再考虑一个显然的优化。
将 (L,M leq 10^6),改为:
(L leq 2 imes 10^9),(M leq 10^6).
这时 线段树、差分、离散化 都无法解决这个难题了。
你会发现:其实最简化的题意是:
求(M)个集合的并集。
那么就很显然了吧!将 (M) 个区间排序(按关键字),然后直接模拟即可。
时间复杂度即为:排序的时间加上线性的递推。 (O(M log M + M) = O(M log M)).
这样,本题的时间复杂度就抛开了 (L).
空间复杂度:(O(M))
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
int n,m,ans=0;
pair<int,int>a[N];
int main(){
n=read(),m=read();
for(int i=1;i<=m;i++) a[i].first=read(),a[i].second=read();
sort(a+1,a+1+m);
int nx=a[1].first,ny=a[1].second;
for(int i=2;i<=m;i++) {
if(ny<=a[i].first) ans+=(ny-nx+1),nx=a[i].first,ny=a[i].second; //两个集合没有交集,直接统计
else if(ny<=a[i].second) ny=a[i].second; //有交集则扩展当前集合
} ans+=(ny-nx)+1;
printf("%d
",n-ans-1); //最后减去被砍的树即可。+1是因为有0这个点。
return 0;
}