双指针例题

这两天在 cf 做了若干道双指针的题目，不过 cf 对双指针这个标签的题目分类似乎有点迷。。。很多和双指针关系感觉不是很大。

在我看来，双指针的核心在于决策单调，因为单调性的存在，可以减小解空间，从而降低时间复杂度。

这里选了一些思想比较典型的题目记录一下。

例题 1：

传送门：https://codeforces.com/contest/1555/problem/E

让你选择若干条线段使得 ([1, m]) 连通，求合法决策的最小极差。

分析

我们考虑将线段的权值作为关键字排序，那么注意到决策选取相邻的线段一定会得到答案。

因此我们可以考虑使用双指针，从小到大枚举 (l) 指针，然后对于每个 (l) 指针，我们找到最靠左合法的 (r) 指针（所谓合法就是选取 ([l, r]) 的 (r-l+1) 条线段后 ([1,m]) 是连通的）。

判断连通以及维护指针移动原区间对应的变化可以用线段树维护。

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#define endl '
'
#define debug(x) cerr << #x << ": " << x << endl
#define pb push_back
#define eb emplace_back
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b

#define all(x) (x).begin(), (x).end()
#define SUM(a) accumulate(all(a), 0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define lb(a, x) distance(begin(a), lower_bound(all(a), (x)))
#define ub(a, x) distance(begin(a), upper_bound(all(a), (x)))

#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f

using pii = pair<int, int>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vpii = vector<pii>;
using ll = long long;
using ull = unsigned long long;

inline void read(int &x) {
    int s=0;x=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=3e5+5, M=1e6+5;

struct Seg{
	int l, r, w;
	bool operator < (const Seg &o)const{
		return w<o.w;
	}
}a[N];

struct Tree{
	int l, r; 
	int v, add;
	
	#define ls(u) u<<1
	#define rs(u) u<<1|1
}tr[M<<2];

int n, m;

void pushup(int u){
	tr[u].v=min(tr[ls(u)].v, tr[rs(u)].v);
}

void pushdown(int u){
	if(tr[u].add){
		auto &L=tr[ls(u)], &R=tr[rs(u)], &rt=tr[u];
		L.v+=rt.add, L.add+=rt.add;
		R.v+=rt.add, R.add+=rt.add;
		rt.add=0;
	}
}

void build(int u, int l, int r){
	tr[u]={l, r};
	if(l==r) return;
	int mid=l+r>>1;
	build(ls(u), l, mid), build(rs(u), mid+1, r);
}

void modify(int u, int l, int r, int k){
	if(tr[u].l>=l && tr[u].r<=r) return tr[u].v+=k, tr[u].add+=k, void();
	int mid=tr[u].l+tr[u].r>>1;
	pushdown(u);
	if(l<=mid) modify(ls(u), l, r, k);
	if(r>mid) modify(rs(u), l, r, k);
	pushup(u);
}

int main(){
	read(n), read(m);
	rep(i,1,n){
		int l, r, w; read(l), read(r), read(w); r--;
		a[i]={l, r, w};
	}	
	
	sort(a+1, a+1+n);
	build(1, 1, m-1);
	
	int res=INF;
	for(int l=1, r=0; l<=n; l++){
		while(!tr[1].v){
			if(++r>n) break;
			modify(1, a[r].l, a[r].r, 1);
		}	
		if(r>n) break;
		res=min(res, a[r].w-a[l].w);
		modify(1, a[l].l, a[l].r, -1);
	}
	cout<<res<<endl;
	
    return 0;
}

例题 2：

传送门：https://codeforces.com/contest/1539/problem/D

(n) 种价格为 (2) 的商品有属性 (a, b)，(a) 是个数，(b) 是当总共买够 (b) 个商品（不限于本商品）时可以以价格 (1) 购入（打对折）。求最少花多少钱买下所有商品。

分析

模拟 + 双指针

假设没有打折这个操作，那么所有商品价格都是 (2)，怎么决策都一样。

而我们是可以享受打折的，所以目标是最大化打折的商品数。

将所有种类的商品以 (b) 为关键字升序排序。

当 (b) 小的商品现在无法享受折扣时，我们可以去买 (b) 大的商品。
而当现在购买的商品数足够让 (b) 小的商品打折时，我们一定选择购买 (b) 小的商品。

于是我们的决策一定是从两边到中间这样的，符合双指针的特征。

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#define endl '
'
#define debug(x) cerr << #x << ": " << x << endl
#define pb push_back
#define eb emplace_back
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b

#define all(x) (x).begin(), (x).end()
#define SUM(a) accumulate(all(a), 0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define lb(a, x) distance(begin(a), lower_bound(all(a), (x)))
#define ub(a, x) distance(begin(a), upper_bound(all(a), (x)))

#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f

using pii = pair<int, int>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vpii = vector<pii>;
using ll = long long;
using ull = unsigned long long;

#define int ll

inline void read(int &x) {
    int s=0;x=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=1e5+5;

struct Node{
	int a, b; 
	bool operator < (const Node &o)const{
		return b<o.b;
	}
}e[N];
int n;

signed main(){
	read(n);
	rep(i,1,n){
		int a, b; read(a), read(b);
		e[i]={a, b};
	}	
	
	sort(e+1, e+1+n);
	
	ll res=0;
	for(int l=1, r=n, cur=0; l<=r; ){
		while(cur<e[l].b && l<=r){
			while(cur+e[r].a<e[l].b && l<=r) res+=e[r].a*2, cur+=e[r].a, r--;
			if(l>r) break;
			e[r].a-=e[l].b-cur, res+=2*(e[l].b-cur), cur+=e[l].b-cur;
		}
		if(l>r) break;
		while(cur>=e[l].b && l<=r){
			cur+=e[l].a, res+=e[l].a;
			l++;
		}
	}
	cout<<res<<endl;
	
    return 0;
}

例题 3：

传送门：
https://codeforces.com/contest/701/problem/C

给你一个字符串，找到最短的子段，满足字符串出现的所有字符在子段中出现。

分析

这道题很经典。

可以发现如果子段 ([l, r]) 是满足的，那么 ([l, r+d]) 也一定满足，所以这是满足决策单调的。

所以我们可以枚举 (l) 指针，然后从上次决策的 (r) 的位置继续枚举，复杂度为 (O(n))。

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#define endl '
'
#define debug(x) cerr << #x << ": " << x << endl
#define pb push_back
#define eb emplace_back
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b

#define all(x) (x).begin(), (x).end()
#define SUM(a) accumulate(all(a), 0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define lb(a, x) distance(begin(a), lower_bound(all(a), (x)))
#define ub(a, x) distance(begin(a), upper_bound(all(a), (x)))

#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f

using pii = pair<int, int>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vpii = vector<pii>;
using ll = long long;
using ull = unsigned long long;

inline void read(int &x) {
    int s=0;x=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=1e5+5, M=200;
char s[N];
bool vis[M];
int cnt[M];

bool check(){
	rep(i,0,M-1) if(vis[i] && !cnt[i]) return false;
	return true;
}

int main(){
	int n; cin>>n;
	cin>>s+1;
	
	rep(i,1,n) vis[s[i]-'A']=true;
	
	cnt[s[1]-'A']++;
	int j=1, res=INF;
	rep(i,1,n){
		while(!check() && j<n){
			j++;
			cnt[s[j]-'A']++;
		}
		if(!check() && j==n) break;
		res=min(res, j-i+1);
		cnt[s[i]-'A']--;
	}
	cout<<res<<endl;
    return 0;
}

例题 4：

传送门：
https://codeforces.com/contest/1469/problem/C

题意可以看洛谷的：
https://www.luogu.com.cn/problem/CF1469C

分析

注意到当前篱笆的决策范围只和上一个有关，所以我们可以维护一个区间 ([l, r]) 表示可以决策的范围，模拟一下就好了。

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#define endl '
'
#define debug(x) cerr << #x << ": " << x << endl
#define pb push_back
#define eb emplace_back
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
using pii = pair<int, int>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vpii = vector<pii>;
using ll = long long;
using ull = unsigned long long;

inline void read(int &x) {
    int s=0;x=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=2e5+5;

int h[N];

int main(){
	int T; cin>>T;
	while(T--){
		int n, k; read(n), read(k);
		rep(i,1,n) read(h[i]);
		
		int l=h[1], r=h[1];
		bool ok=true;
		rep(i,2,n){
			l=max(h[i], l-k+1), r=min(r+k-1, h[i]+k-1);
			// debug(l), debug(r);
			if(l>r){
				ok=false;
				break;
			}
		}
		if(l!=h[n]) ok=false;
		
		puts(ok? "YES": "NO");
	}	
    return 0;
}