自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:29:40，当前版本为作者最后更新于2021-03-07 16:54:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题意简述：给出颜色序列 $a$，多次询问给出 $l,r$，求涂成 $a_l,a_{l+1},\cdots,a_r$ 的最小操作次数。每次涂色只能用一段数值更大的颜色覆盖原有的颜色。

在我的 cnblogs 中查看

首先考虑 $l=1,r=n$ 的情况：从左到右考虑每个位置上的颜色 $a_i$，记 $pre$ 为 $i$ 左边的颜色为 $a_i$ 的最大位置。若 $a_i\leq \min_{j=pre}^i a_j$ 则表明可以直接将颜色从 $pre$ 直接涂到 $i$，否则要再用一次操作。

从左到右不断加入新的位置 $i$，记 $ans_j$ 为 $[j,i]$ 的答案，考虑维护 $ans$：若 $a_i\leq \min_{j=pre}^i a_j$ 则只需将 $ans_{pre+1},ans_{pre+2},\cdots,ans_i$ 加 $1$；否则这个位置需要再用一次操作，也就是 $ans_1,ans_2,\cdots,ans_i$ 加 $1$。将所有询问按右端点排序，这样就是区间最值和区间加，单点查询，分别用 ST 表和树状数组维护即可。

#include <bits/stdc++.h>
using namespace std;

#define pii pair <int,int>

const int N=2e5+5;
int n,q,d[N],m[N<<1][18],ans[N],pre[N],lst[N];
vector <pii> e[N];
void add(int x,int v){while(x<=n)d[x]+=v,x+=x&-x;}
int query(int x){int ans=0; while(x)ans+=d[x],x-=x&-x; return ans;}

int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>m[i][0],pre[i]=lst[m[i][0]],lst[m[i][0]]=i;
	for(int j=1;j<18;j++)for(int i=1;i<=n;i++)m[i][j]=min(m[i][j-1],m[i+(1<<j-1)][j-1]);
	for(int i=1,l,r;i<=q;i++)cin>>l>>r,e[r].emplace_back((pii){i,l});
	for(int i=1;i<=n;i++){
		int p=pre[i],d=log2(i-p);
		add(min(m[p+1][d],m[i-(1<<d)+1][d])<m[i][0]?1:p+1,1),add(i+1,-1);
		for(pii it:e[i])ans[it.first]=query(it.second);
	} for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
	return 0;
}