原題鏈接

解析

題意等價于問有多少個位置 \(k\)，使得其對于所有 \(1 \le i \le n\)，右移 \(a_i\) 后不屬于任何一個區(qū)間。

發(fā)現(xiàn)有一個區(qū)間長度互不相等的限制，不知道有什么用。

發(fā)現(xiàn) \(a_i \le 5 \times 10 ^ 5\)，但是區(qū)間和 \(k\) 的值域非常大。

先對 \(a\) 從小到大排序。

若對于一個 \(x\)，有 \(x + a_{n} = l_j\)。那么對于所有 \(y \in [x,x + r_j - l_j]\)，都有 \(y + a_{n} \in [l_j,r_j]\)。由于 \(a\) 的值域很小，感性理解，對于 \(x' + a_{n - 1} = l_j\)，\([x',x' + len_j]\) 很有可能跟 \([x,x + len_j]\) 有交。事實上，若 \(a_n - a_{n - 1} \le len_j\)，則兩區(qū)間有交。

也就是說，對于一個區(qū)間 \([l_i,r_i]\)，可以將 \(a\) 分成 \(\frac{a_{max}}{len_i}\) 份，每段 \(a\) 可以并出一段連續(xù)的值域段。這樣，根據(jù)調(diào)和級數(shù)的結(jié)論，所有 \(m\) 個區(qū)間會產(chǎn)生 \(O(a \log m)\) 個值域段，排序后再進行合并就可以得出非法值域段的并，總時間復(fù)雜度 \(O(a \log m \log m)\)。

代碼

/*
*/
#include<bits/stdc++.h>
#define eps 0.000001
#define mid ((l + r) >> 1)
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1) | 1)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll,ll> pii;
const int N = 5e5 + 5,M = 2e5 + 5,base = 13331,mod = 998244353;
int a[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
//	freopen("in.txt","r",stdin);	
//	freopen("out.txt","w",stdout);
	ll n,m,v;
	cin>>n>>m>>v;
	vector<int> vec;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		vec.push_back(a[i]);
	}
	sort(vec.begin(),vec.end(),greater<int>());
	vector<pii> seg;
	for(int i=1;i<=m;i++){
		ll l,r;
		cin>>l>>r;
		int now = 0,t = 0;
		while(now < vec.size()){
			t = upper_bound(vec.begin() + now,vec.end(),vec[now] - (r - l + 1),greater<ll>()) - vec.begin() - 1;
//			cerr<<now<<" "<<t<<" "<<vec[now]<<" "<<vec[t]<<" "<<l<<" "<<r<<'\n';
			seg.push_back({max(1ll,l - vec[now]),max(0ll,min(v,r - vec[t]))});
			now = t + 1;
		}
	}
	sort(seg.begin(),seg.end());
	seg.push_back({9e18,9e18});
	ll l = 0,r = -1,res = v;
	for(int i=0;i<seg.size();i++){
//		cout<<seg[i].first<<" "<<seg[i].second<<'\n';
		if(seg[i].first > r){
//			cout<<"!!! "<<l<<" "<<r<<'\n';
			res -= r - l + 1;
			if(seg[i].first > v) break;
			l = seg[i].first,r = seg[i].second;
		}else{
			r = max(r,seg[i].second);
		}
	}
	cout<<res;
	return 0;
}
/*
*/