ABC260 E - At Least One (Dual Pointer)

ABC260 E - At Least One(双指针)

一开始想到two pointers 了,But I don't know how to quickly maintain whether the conditions are met.

Originally opened onevector,然后用cntThe variable holds the currently reached number of groups.Then only the pair becomes$0$barrel effectcnt.

因为每个$i$ 对应的vector Iterates at most twice.

因此复杂度是：$O(n+m)$

#include <iostream>
#include <vector>
using namespace std;

int main() {
    
  int N, M;
  cin >> N >> M;
  vector<int> A(N), B(N);
  for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
  vector<vector<int>> inv(M + 1);
  for (int i = 0; i < N; i++) {
    
    inv[A[i]].push_back(i);
    inv[B[i]].push_back(i);
  }
  vector<int> cnt(N), ans(M + 3);
  int cnt_zero = N;
  for (int i = 1, j = 1; i <= M;) {
    
    while (j <= M and cnt_zero != 0) {
    
      for (auto& x : inv[j]) {
    
        if (cnt[x] == 0) cnt_zero--;
        cnt[x]++;
      }
      j++;
    }
    if (cnt_zero != 0) break;
    ans[j - i]++, ans[M + 1 - i + 1]--;
    for (auto& x : inv[i]) {
    
      cnt[x]--;
      if (cnt[x] == 0) cnt_zero++;
    }
    i++;
  }
  for (int i = 1; i <= M; i++) {
    
    ans[i] += ans[i - 1];
    cout << ans[i] << " \n"[i == M];
  }
}

---

According to double pointer,我们可以枚举左端点,The right endpoint actually we just need to update$r=max(r,mx[l++])$

这里$mx[val]$ are all left endpoints of $val$The corresponding maximum right endpoint value.

显然$l++$之后,$r$ 必须大于等于$mx[l]$.

特别地,当$l=1$,$r$ is the maximum value of all left endpoints.这样$r$是最小的$r$.

然后双指针$O(1)$更新即可.

注意$l\le \min \{b[i]\}$ ,不然无解.

时间复杂度：$O(n)$

// Problem: E - At Least One
// Contest: AtCoder - AtCoder Beginner Contest 260
// URL: https://atcoder.jp/contests/abc260/tasks/abc260_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Date: 2022-07-30 23:13:40
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=2e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
const int hashmod[4] = {
    402653189,805306457,1610612741,998244353};
#define mst(a,b) memset(a,b,sizeof a)
#define db double
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define x first
#define y second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr) 
void Print(int *a,int n){
    
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
template <typename T>		//x=max(x,y) x=min(x,y)
void cmx(T &x,T y){
    
	if(x<y) x=y;
}
template <typename T>
void cmn(T &x,T y){
    
	if(x>y) x=y;
}
PII a[N];
int left_mx[N];
int is_right[N];
ll pre[N];
int n,m;
bool ck(int x){
    
	for(int i=1;i<=n;i++){
    
		if(x<a[i].x) return false;
	}
	return true;
}
int main(){
    
	ll mn = 1e18;
	cin>>n>>m;
	rep(i,1,n){
    
		cin>>a[i].x>>a[i].y;
		cmx(left_mx[a[i].x],a[i].y);
		cmn(mn,1LL*a[i].y);
	}
	int l=1,r=m,ans=0;
	while(l<=r){
    
		int mid = l+r>>1;
		if(ck(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	//printf("%d %d\n",1,ans);
	for(int i=1,j=ans;i<=mn;cmx(j,left_mx[i++])){
    
		pre[j-i+1]++,pre[m-i+2]--;
	}
	rep(i,1,m) pre[i]+=pre[i-1];;
	rep(i,1,m){
    
		printf("%lld ",pre[i]);
	}
	return 0;
}