傳送門
文章目錄
題意：
思路：
我們考慮將區間內的位置都+1+1+1，之后求區間段數就可以轉換成求，連續不為000的區間段數，由于范圍有[?1e9,1e9][-1e9,1e9][?1e9,1e9]的級別，所以我們考慮將其離散化。
注意離散化之后的時候需要將區間?2?1*2-1?2?1，這樣做是為了防止[1,3][1,3][1,3]和[4,5][4,5][4,5]這段區間之后合并。
讓后我們考慮如何快速的求去掉當前區間之后增加的段數。
我們將連續111的起點和終點都+1+1+1，之后求前綴和，當前區間增加的段數就是pre[r]?pre[l?1]>>1pre[r]-pre[l-1]>>1pre[r]?pre[l?1]>>1，當然這樣還不行，如果區間前后與新增段相連接的話，需要減去。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
;
int a
[N
],pre
[N
];
PII p
[N
];
vector
<int>v
;int find(int x
)
{return lower_bound(v
.begin(),v
.end(),x
)-v
.begin()+1;
}int main()
{
int _
; scanf("%d",&_
);while(_
--){scanf("%d",&n
);for(int i
=1;i
<=n
;i
++)scanf("%d%d",&p
[i
].X
,&p
[i
].Y
),v
.pb(p
[i
].X
),v
.pb(p
[i
].Y
);sort(v
.begin(),v
.end()); v
.erase(unique(v
.begin(),v
.end()),v
.end());int se
=v
.size()*2-1+10;for(int i
=1;i
<=n
;i
++){a
[find(p
[i
].X
)*2-1]++;a
[find(p
[i
].Y
)*2]--;}for(int i
=1;i
<=se
;i
++) a
[i
]+=a
[i
-1];int sum
=0;for(int i
=1;i
<=se
;i
++) if(a
[i
]!=0&&a
[i
-1]==0) sum
++;for(int i
=1;i
<=se
;i
++) pre
[i
]+=(a
[i
-1]!=1&&a
[i
]==1);for(int i
=0;i
<=se
;i
++) pre
[i
]+=(a
[i
+1]!=1&&a
[i
]==1);for(int i
=1;i
<=se
;i
++) pre
[i
]+=pre
[i
-1];int ans
=-INF
;for(int i
=1;i
<=n
;i
++){int l
=find(p
[i
].X
)*2-1,r
=find(p
[i
].Y
)*2-1;int add
=(pre
[r
]-pre
[l
-1])/2;add
-=(a
[l
]==1)+(a
[r
]==1);ans
=max(ans
,sum
+add
);}printf("%d\n",ans
);for(int i
=1;i
<=se
+10;i
++) pre
[i
]=0,a
[i
]=0;v
.clear();}return 0;
}
總結
以上是生活随笔為你收集整理的Codeforces Round #613 (Div. 2) E. Delete a Segment 离散化的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
