Description&Data Constraint
Bessie 最近收到了一套颜料，她想要给她的牧草地一端的栅栏上色。栅栏由 (N) 个 (1) 米长的小段组成（(1le Nle 2cdot 10^5)）。Bessie 可以使用 (N) 种不同的颜色，她将这些颜色由浅到深用 (1) 到 (N) 标号（(1) 是很浅的颜色，(N) 是很深的颜色）。从而她可以用一个长为 (N) 的整数数组来描述她想要给栅栏的每一小段涂上的颜色。
初始时，所有栅栏小段均未被上色。Bessie 一笔可以给任意连续若干小段涂上同一种颜色，只要她不会在较深的颜色之上涂上较浅的颜色（她只能用较深的颜色覆盖较浅的颜色）。
例如，一段长为 (4) 的未被涂色的栅栏可以按如下方式上色：
0000 -> 1110 -> 1122 -> 1332
不幸的是，Bessie 没有足够的时间等待颜料变干。所以，Bessie 认为她可能需要放弃为栅栏上某些小段上色！现在，她正在考虑 (Q) 个候选的区间（(1le Qle 2cdot 10^5)），每个区间用满足 (1 leq a leq b leq N) 的两个整数 ((a,b)) 表示，为需要上色的小段 (a ldots b) 的两端点位置。
对于每个候选区间，将所有区间内的栅栏小段都涂上所希望的颜色，并且区间外的栅栏小段均不涂色，最少需要涂多少笔？注意在这个过程中 Bessie 并没有真正进行任何的涂色，所以对于每个候选区间的回答是独立的。
Solution
考虑每个右端点对左端点的贡献。
一段区间 ([l,r]) 可以连续被 (i) 上色仅限于 (l) 到 (r) 中没有比 (i) 小的颜色存在。
预处理出每个点上一次出现同色位置 (pre_i)。
对于新加入的点 (i)，查询 (pre_i+1) 到 (i-1) 中的最小值 (mn)。设 (res_l) 表示以 (l) 为左端点的答案。
如果 (mnge a_i)，说明 (a_i) 是可以从 (pre_i) 直接涂过来的，但是 (pre_i+1) 到 (i-1) 这个区间里的答案要加一，因为对于他们 (a_i) 是第一次出现，需要重新涂色。
否则从 (1) 到 (i+1) 都要加一，因为要多操作一次。
对于询问考虑离线，对于每个右端点为 (i) 的询问，查询左端点上的权值，即这个询问的答案。
为此我们需要一个数据结构满足区间最小值查询，区间修改，单点查询。普通的线段树可以轻松解决。
Code
#include<cstdio>
#include<algorithm>
#define N 200005
using namespace std;
struct seg
{
int mn,val,lazy;
}tree[N<<2];
int n,q,l,r,t[N],pre[N],a[N<<1],ans[N],qo[N][3],last[N],ls[N];
void build(int now,int l,int r)
{
if (l==r)
{
tree[now].mn=a[l];
return;
}
int mid=(l+r)>>1;
build(now<<1,l,mid);
build(now<<1|1,mid+1,r);
tree[now].mn=min(tree[now<<1].mn,tree[now<<1|1].mn);
}
int getmin(int now,int l,int r,int p,int q)
{
if (p>q) return 2147483647;
if (l>=p&&r<=q) return tree[now].mn;
int mid=(l+r)>>1,res=2147483647;
if (p<=mid) res=min(res,getmin(now<<1,l,mid,p,q));
if (q>mid) res=min(res,getmin(now<<1|1,mid+1,r,p,q));
return res;
}
void pushup(int now,int len)
{
if (tree[now].lazy)
{
tree[now<<1].lazy+=tree[now].lazy;
tree[now<<1|1].lazy+=tree[now].lazy;
tree[now<<1].val+=tree[now].lazy*(len-(len>>1));
tree[now<<1|1].val+=tree[now].lazy*(len>>1);
tree[now].lazy=0;
}
}
void modify(int now,int l,int r,int p,int q,int v)
{
if (l>=p&&r<=q)
{
tree[now].lazy+=v;
tree[now].val+=v*(r-l+1);
return;
}
pushup(now,r-l+1);
int mid=(l+r)>>1;
if (p<=mid) modify(now<<1,l,mid,p,q,v);
if (q>mid) modify(now<<1|1,mid+1,r,p,q,v);
tree[now].val=tree[now<<1].val+tree[now<<1|1].val;
}
int query(int now,int l,int r,int p)
{
if (l==r) return tree[now].val;
pushup(now,r-l+1);
int mid=(l+r)>>1;
if (p<=mid) return query(now<<1,l,mid,p);
else return query(now<<1|1,mid+1,r,p);
}
int main()
{
scanf("%d%d",&n,&q);
for (int i=1;i<=n;++i)
scanf("%d",&a[i]);
build(1,1,n);
for (int i=1;i<=n;++i)
{
pre[i]=t[a[i]];
t[a[i]]=i;
}
for (int i=1;i<=q;++i)
{
scanf("%d%d",&l,&r);
last[i]=ls[r];
ls[r]=i;
qo[i][1]=i;qo[i][2]=l;
}
for (int i=1;i<=n;++i)
{
if (getmin(1,1,n,pre[i]+1,i-1)<a[i]) modify(1,1,n,1,i,1);
else modify(1,1,n,pre[i]+1,i,1);
for (int j=ls[i];j;j=last[j])
ans[qo[j][1]]=query(1,1,n,qo[j][2]);
}
for (int i=1;i<=q;++i)
printf("%d
",ans[i]);
return 0;
}