题意概括：给定一个长度为$N$的自然数序列$(N\leqslant500000$,数的范围$0$到$1000000$之间的整数)，有$M$个询问，每个询问两个整数$l,r$表示$l$~$r$区间内有几个不同的数$(M\leqslant500000)$

题意:$Farmer John $的农场缺水了。

他决定将水引入到他的 $n$ 个牧场。他准备通过挖若干井，并在各块田中修筑水道来连通各块田地以供水。在第 $i$ 号田中挖一口井需要花费 $W_i$ 元。连接 $i$ 号田与 $j$ 号田需要 $P_{i,j}$（$P_{j,i}=P_{i,j}$）元。

请求出 FJ 需要为使所有农场都与有水的农场相连或拥有水井所需要的最少钱数。

$1 \leqslant n \leqslant 300$，$1 \leqslant W_i \leqslant 10^5$，$1 \leqslant P_{i,j} \leqslant 10^5$。

题意:从图中第$i$号节点开始遍历,每个节点存有下一步要去的节点,当遍历的路径出现环时结束遍历并输出路径长度(边权默认为$1$)

题意:有一只甲虫处于一根水平的树枝。因为他沉迷数学无法自拔，所以他觉得很像是在 $x$ 轴上。

在同一根树枝上，还有 $n$ 滴露水。每滴露水占用 $m$ 个单位的水分。相对于甲虫的位置，他们的坐标分别是 $x_1,x_2,\dots,x_n$。

显然，这一天将会骄阳似火。每过一个时间单位，就会有一个单位的水分从每一滴露水流失。这只甲虫受尽了烈阳的折磨，以至于每当它碰到一滴露水都能瞬间喝完。在每个时间单位中它能移动一个单位的距离。

所以你要写一个程序，根据露水的坐标，计算出甲虫最多能喝到的水。

$0 \le n \le 300,1 \le m \le 1,000,000,-10,000 \le x_1,x_2,\dots,x_n \le 10,000,$ 对于所有 $i \ne j,x_i \ne x_j$。

线段树、树状数组、ST表、分块、堆……等数据结构，但是复杂度都至少是$nlogn$的，于是我写了个尺取法+单调队列的方法，时间复杂度$O(n)$

单调队列维护区间中$si$~$sj$的最大值,这里运用到了一点贪心策略，如果两个区间有包含关系，那么大的区间最大值一定$\geqslant$小的区间最大值，所以对于每一个$i$，我们去前面找第一个$head$，使$sum_{i,j}\geqslant m$

如图所示，我们选择$5$作为$head$而不是前面的$11$、$2$、$3$、$4$，是因为区间更长，就像在一个数列中加入了另一些数，另一些数中可能有大于原数列的最大值，因为要求最大值的最小值，故不是最优。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}//快读
int a[300000],b[300000],p[300000],head=1,head1=1,tail1=0,ans=2100000000;
ll sum,m;
inline ll Min(int a,int b){
    if (a>b)return b;
    else return a;
}
int main(){
    int n=read();
    scanf("%lld",&m);
    for (int i=1;i<=n;i++) a[i]=read(),b[i]=read();
    for (int i=1;i<=n;i++){
        sum+=a[i];
        while (head<=i&&sum-a[head]>=m){
            sum-=a[head];head++;//这里注意要先减再head++，尺取法与单调队列在这里都容易出错
        }
        while (head1<=tail1&&p[head1]<head) head1++;//若队首位置小于区间左端，则出队
        while (head1<=tail1&&b[i]>=b[p[tail1]]) tail1--;//若新加入的数大于队尾，则队尾出队
        p[++tail1]=i;//放入队列
        if (sum>=m)ans=Min(ans,b[p[head1]]);
        }
    printf("%lld",ans);
}