双指针法

最长的区间满足要求，求最短满足要求的区间
for (左端点)
{
while (不满足)
{
右端点右移
}
if (满足)
{
更新答案
}
左端点右移
}

或者

for (右端点)
{
while (满足)
{
更新答案
左端点右移
}
左端点右移
}

下面的方法很麻烦
for (右端点)
{
while (如果左端点往右移动后还满足)
{
左端点往右移动
}
if (满足条件)
{
更新答案
}
右端点右移
}
2. 最短的区间满足要求，求最长满足要求的区间

for (右端点)
{
while (不满足)
{
左端点右移
}
更新答案
右端点右移
}

P3029 [USACO11NOV]Cow Lineup S

https://www.luogu.com.cn/problem/P3029

题目背景

【问题描述】

农民约翰雇一个专业摄影师给他的部分牛拍照。由于约翰的牛有好多品种，他喜欢他的照片包含每

个品种的至少一头牛。

约翰的牛都站在一条沿线的不同地方，每一头牛由一个整数位置 X_i以及整数品种编号 ID_i表示。

约翰想拍一张照片，这照片由沿线的奶牛的连续范围组成。照片的成本与规模相当，这就意味着，在一

系列照片中的最大和最小 X 坐标的差距决定了照片的成本。

请帮助约翰计算最小的照片成本，这些照片中有每个不同的品种的至少一头牛，没有两头牛愿意站

在同一个地点的。

【输入格式】

第 1 行：牛的数量 N；

第 2..1+N 行：每行包含 2 个以空格分隔的正整数 X_i 和 ID_i；意义如题目描述；

【输出格式】

输出共一行，包含每个不同品种 ID 的照片的最低成本。

【输入样例】

6 25 7 26 1 15 1 22 3 20 1 30 1 【输出样例】

4 【输入说明】在不同的坐标点 25,26,15,22,20,30 中有六头牛

【输出说明】在约翰的牛中，从 X=22 到 X=26（整个规模为 4）包含了每个的不同品种的 ID 3，7 和 1。

【数据规模】

对于 50%的数据： 1≤N≤300；

对于 100%的数据：1≤N≤50,000；0≤X_i≤1,000,000,000；1≤ID_i≤1,000,000,000；

感谢uid=15936的翻译

题目描述

Farmer John has hired a professional photographer to take a picture of some of his cows. Since FJ's cows represent a variety of different breeds, he would like the photo to contain at least one cow from each distinct breed present in his herd.

FJ's N cows are all standing at various positions along a line, each described by an integer position (i.e., its x coordinate) as well as an integer breed ID. FJ plans to take a photograph of a contiguous range of cows along the line. The cost of this photograph is equal its size -- that is, the difference between the maximum and minimum x coordinates of the cows in the range of the photograph.

Please help FJ by computing the minimum cost of a photograph in which there is at least one cow of each distinct breed appearing in FJ's herd.

依次给出N头牛的位置及种类，要求找出连续一段，使其中包含所有种类的牛，问：这连续的一段最小长度是多少？

输入格式

* Line 1: The number of cows, N (1 <= N <= 50,000).

* Lines 2..1+N: Each line contains two space-separated positive integers specifying the x coordinate and breed ID of a single cow. Both numbers are at most 1 billion.

输出格式

* Line 1: The smallest cost of a photograph containing each distinct breed ID.

样例 #1

样例输入 #1

样例输出 #1

提示

There are 6 cows, at positions 25,26,15,22,20,30, with respective breed IDs 7,1,1,3,1,1.

The range from x=22 up through x=26 (of total size 4) contains each of the distinct breed IDs 1, 3, and 7 represented in FJ's herd.

感谢 wjcwinmt 提供题目简述

参考代码

#include <bits/stdc++.h>
using namespace std;
set<int> s;
map<int, int> c;
int n, cnt, z = 1e9;
pair<int, int> a[50020];
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i].first >> a[i].second;
		s.insert(a[i].second);
	}
	sort(a, a + n);
	for (int i = 0, j = 0; i < n;)
	{
		while (j < n && cnt < s.size())
		{
			cnt += !c[a[j++].second]++;
		}
		if (cnt == s.size())
		{
			z = min(z, a[j-1].first - a[i].first);
		}
		cnt -= !--c[a[i++].second];
	}
	printf("%d\n", z);
	return 0;
}

题解

双指针法尺取法

对于每个起点（左端点）可以求出最优解（右端点）

如果左端点向右移动，右端点要么不动，要么向右移动

满足这个条件就可以用双指针法解决

#include <bits/stdc++.h>
using namespace std;
set<int> s;
map<int, int> c;
int n, cnt, z = 1e9;
pair<int, int> a[50020];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].first >> a[i].second;
        s.insert(a[i].second);
    }
    sort(a, a + n);
    // cnt 当前区间内，牛的种类数
    // c 当前区间内，每种牛的个数
    for (int i = 0, j = 0; i < n;) // 下标范围 [i, j)   区间长度 a[j-1].first - a[i].first
    {
        while (j < n && cnt < s.size())
        {
            cnt += !c[a[j++].second]++;
            // if (!c[a[j].second])
            // {
            //     cnt++;
            // }
            // c[a[j].second]++;
            // j++;
        }
        if (cnt == s.size()) // 如果所有的种类都在
        {
            z = min(z, a[j-1].first - a[i].first);
            // 用当前区间长度更新答案
        }
        // 删去第i个牛
        cnt -= !--c[a[i++].second];
        // --c[a[i].second];
        // if (!c[a[i].second])
        // {
        //     cnt--;
        // }
        // i++;
    }
    printf("%d\n", z);
    return 0;
}

cnt += !c[a[j++].second]++;
if (c[a[j].second] == 0)
{
    cnt += 1;
}
c[a[j].second] += 1
j += 1;


cnt -= !--c[a[i++].second];
--c[a[i].second];
if (c[i].second == 0)
{
    cnt -= 1;
}
i++;

P3069 [USACO13JAN]Cow Lineup G

https://www.luogu.com.cn/problem/P3069

题目描述

Farmer John's N cows (1 <= N <= 100,000) are lined up in a row. Each cow is identified by an integer "breed ID" in the range 0...1,000,000,000; the breed ID of the ith cow in the lineup is B(i). Multiple cows can share the same breed ID.

FJ thinks that his line of cows will look much more impressive if there is a large contiguous block of cows that all have the same breed ID. In order to create such a block, FJ chooses up to K breed IDs and removes from his lineup all the cows having those IDs. Please help FJ figure out the length of the largest consecutive block of cows with the same breed ID that he can create by doing this.

农夫约翰的N(1 <= N <= 100,000)只奶牛排成了一队，每只牛都用编上了一个“血统编号”，该编号为范围0...1,000,000,000的整数。血统相同的奶牛有相同的编号，也就是可能有多头奶牛是相同的"血统编号"。

约翰觉得如果连续排列的一段奶牛有相同的血统编号的话，奶牛们看起来会更具有威猛。为了创造这样的连续段，约翰最多能选出k种血统的奶牛，并把他们全部从队列中赶走。

请帮助约翰计算这样做能得到的由相同血统编号的牛构成的连续段的长度最大是多少？

输入格式

* Line 1: Two space-separated integers: N and K.

* Lines 2..1+N: Line i+1 contains the breed ID B(i).

输出格式

* Line 1: The largest size of a contiguous block of cows with

identical breed IDs that FJ can create.

样例 #1

样例输入 #1

样例输出 #1

提示

There are 9 cows in the lineup, with breed IDs 2, 7, 3, 7, 7, 3, 7, 5, 7. FJ would like to remove up to 1 breed ID from this lineup.

By removing all cows with breed ID 3, the lineup reduces to 2, 7, 7, 7, 7, 5, 7. In this new lineup, there is a contiguous block of 4 cows with the same breed ID (7).

参考代码

#include <bits/stdc++.h>
using namespace std;
map<int, int> c;
int n, m, z, cnt;
int a[100020];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0, j = 0; j < n; j++)
	{
		scanf("%d", &a[j]);
		cnt += !c[a[j]]++;
		while (cnt > m + 1)
		{
			cnt -= !--c[a[i++]];
		}
		z = max(z, c[a[j]]);
	}
	printf("%d\n", z);
	return 0;
}

题解

#include <bits/stdc++.h>
using namespace std;
map<int, int> c;
int n, m, z, cnt;
int a[100020];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0, j = 0; j < n; j++) // j 是右端点
    {
        scanf("%d", &a[j]);
        cnt += !c[a[j]]++;
        // if (!c[a[j]])
        // {
        //     cnt++;
        // }
        // c[a[j]]++；
        while (cnt > m + 1) // while [i, j] 区间内的牛种类数太多了，> m+1
        {
            cnt -= !--c[a[i++]];
            // 删去第i个牛
            // --c[a[i]];
            // if (!c[a[i]])
            // {
            //     cnt--;
            // }
            // i++;
        }
        z = max(z, c[a[j]]);
        // 如果我们选择 [i, j] 区间，我们认为 a[j] 这种牛出现次数最多，用 a[j] 出现的次数更新答案
    }
    printf("%d\n", z);
    return 0;
}

P4085 [USACO17DEC]Haybale Feast G

https://www.luogu.com.cn/problem/P4085

题目描述

Farmer John is preparing a delicious meal for his cows! In his barn, he has $N$ haybales ( $1 \le N \le 100,000$ ). The $i$ th haybale has a certain flavor $F_i$ ( $1 \le F_i \le 10^9$ ) and a certain spiciness $S_i$ ( $1 \le S_i \le 10^9$ ).

The meal will consist of a single course, being a contiguous interval containing one or more consecutive haybales (Farmer John cannot change the order of the haybales). The total flavor of the meal is the sum of the flavors in the interval. The spiciness of the meal is the maximum spiciness of all haybales in the interval.

Farmer John would like to determine the minimum spiciness his single-course meal could achieve, given that it must have a total flavor of at least $M$ ( $1 \le M \le 10^{18}$ ).

输入格式

The first line contains the integers $N$ and $M$ , the number of haybales and the minimum total flavor the meal must have, respectively. The next $N$ lines describe the $N$ haybales with two integers per line, first the flavor $F$ and then the spiciness $S$ .

输出格式

Please output the minimum spiciness in a single course meal that satisfies the minimum flavor requirement. There will always be at least one single-course meal that satisfies the flavor requirement.

样例 #1

样例输入 #1

样例输出 #1

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, z = 1e9;
long long m, s;
int a[100020];
int b[100020];
int q[100020], bb, ff;
int main()
{
	cin >> n >> m;
	for (int i = 0, j = 0; j < n; j++)
	{
		cin >> a[j] >> b[j];
		s += a[j];
		while (bb < ff && b[q[ff - 1]] < b[j])
		{
			ff--;
		}
		q[ff++] = j;
		while (s - a[i] >= m)
		{
			s -= a[i++];
		}
		while (bb < ff && q[bb] < i)
		{
			bb++;
		}
		if (s >= m)
		{
			z = min(z, b[q[bb]]);
		}
	}
	cout << z << endl;
	return 0;
}

题解

双指针法结合单调队列

下面的方法很麻烦
for (右端点)
{
while (如果左端点往右移动后还满足)
{
左端点往右移动
}
if (满足条件)
{
更新答案
}
右端点右移
}

#include <bits/stdc++.h>
using namespace std;
int n, z = 1e9;
long long m, s;
int a[100020];
int b[100020];
int q[100020], bb, ff;
int main()
{
    cin >> n >> m;
    for (int i = 0, j = 0; j < n; j++) // 枚举右端点 j
    {
        cin >> a[j] >> b[j];
        // 加入 j
        s += a[j]; // 维护和
        // 维护单调队列
        while (bb < ff && b[q[ff - 1]] < b[j])
        {
            ff--;
        }
        q[ff++] = j;
        while (s - a[i] >= m) // 如果左端点往右移动后还满足
        {
            s -= a[i++]; // 左端点往右移动
        }
        while (bb < ff && q[bb] < i) // 把单调队列中不在 [i, j] 区间的删掉
        {
            bb++;
        }
        if (s >= m) // 如果和满足条件，更新答案
        {
            z = min(z, b[q[bb]]);
        }
    }
    cout << z << endl;
    return 0;
}

Two-Pointer

If the starting point moves to the right, the end point moves to the right

http://www.usaco.org/index.php?page=viewproblem2&cpid=924

p1 * (1-p2) * (1-p3) + (1-p1) * p2 * (1-p3) + (1-p1) * (1-p2) * p3
(1-p1)*(1-p2)*(1-p3) * (p1/(1-p1) + p2/(1-p2) + p3/(1-p3))

https://abc098.contest.atcoder.jp/tasks/arc098_b

xor is addition without carries.

x + y == (x ^ y). if and only if. (x & y) == 0

For each bit, there is at most 1 one.

[i, j)

i, i+1

i, i+2

i, j

http://codeforces.com/problemset/problem/660/C

for (move the end point right)
{
    add the end point / move the end point right
    while (the interval is invalid (it contains >k 1s))
    {
        move the start point right;
    }
    // the interval is valid
    update the answer.
}




for (move the start point right)
{
    while (the interval is valid after adding the end point)
    {
        move the end point right;
    }
    // the interval is valid
    update the answer.
    delete the start point / move the start point right
}



#include<cstdio>

int a[300001];

int main(){

int ans=0,n,k,pi,pj; scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);

for(int i=1,j=0,cnt=0;i<=n;)
{
    while(cnt<=k&&j<=n)
    {
        cnt+=!a[++j];
    }
    // j > n or a[j] == 0 && cnt > k
    // [i, j-1] is valid
    // [i, j] is invalid
    if(j-i>ans)
    ans=j-i,pi=i,pj=j;
    cnt-=!a[i++]
}

// pi, pj the answer interval

printf("%d\n",ans); // length
for(int i=1;i<=n;++i)
    printf("%d ",a[i]||(i>=pi&&i<pj));
}

P4085 [USACO17DEC]Haybale Feast G

a[1] a[2] .. a[n]

b[1] b[2] .. b[n]

n^2 a[i]+b[j]

What are the smallest n a[i]+b[j]

3 7 7

6 10 10

10 14 14

If we choose a[i]+b[j], then a[i-1]+b[j] and a[i]+b[j-1] must be chosen.

Therefore we only to conside. i*j<=n

(1, 1) (1, 2) ... (1, n)

(2, 1) (2, 2) .. (2, n/2)

(3, 1) (3,2) .. (3, n/3)

...

(n, 1)

O(n log n)

尺取法

名称

Codeforces中对应的名字是two pointers，似乎应该翻译成双指针法。
本质上就是利用单调性扫一遍。

大概就是要找到最短的区间（或者是区间的计数）
当左端点从左向右移动时，区间的右端点也是单调向右移动的。

在许多题中需要先排序，才能使用这个方法。
而这个方法和二分，又有一些联系。

参考题目

poj 3061
求最短的区间，要求和大于等于 $S$ 。

Luogu P1638
poj 3320
求最短的区间，包含所有不同的数字。

poj 2566
求一个区间使得其和的绝对值与输入的 $t$ 差值最小。

Atcoder arc098_b
问有多少个区间，异或等于加法的和；要求所有数字在二进制下加法没有进位

CF 1042D
问有多少个区间，和小于等于 $t$ 。

参考资料

https://www.luogu.org/blog/Nero-Yuzurizaki/chi-qu-fa-xiao-jie