# [题解] CF1864E Exotic Queries [区间问题][二维偏序]

# 题目大意 $\footnotesize^{传送门}$

给一个长度为 $n$ 的数组，有 $q$ 个询问，每次询问对于值域 $[L,R]$ 的所有元素，通过以下操作使得这些元素全部变为 $0$ 的最小操作次数。
指定操作 $(l,r,x)$ ：选取一段区间 $[l,r]$ 和一个正整数 $x$ , 将这段区间上的元素减去 $x$ 。
你可以操作任意多次，但是对于所有操作区间，只存在包含、相离关系，不存在相交关系。

# 题解

比较容易发现，对于一个询问 $[L,R]$ ，取 $x\in [L,R]$ ，我们按照 $x$ 从小到大的顺序把数值为 $x$ 的所有元素变为 $0$ ，每次尽可能地用最少操作次数完成，这样完成区间 $[L,R]$ 的总操作次数就是最小的。
每个需要被变成 $0$ 的元素 $a_i$ 可以直接使用操作 $(i,i,a_i)$ 完成，所以最多操作次数为 $S=\sum\limits_{x=L}^R(count(x))$ 。
考虑什么时候可以一次操作将多个元素变成 $0$ 。
两个相邻的相同元素 $a_i,a_j$ 之间的所有元素 $a_k,i<k<j$ ：

要么满足 $a_k<L$
因为小于 L 的数在这次询问不需要理会
要么满足 $a_k>a_i$
因为这次操作不会将 $a_k$ 变成负值， $a_k$ 仍然可以被之后的操作变成 $0$

那么这两个元素可以被一次操作中全变成 $0$
用 $S$ 减去可以被一次操作全变 $0$ 的相邻元素对数，就是我们要的答案
一次操作让 $a_i,a_j$ 都变成 $0$ 的约束为 $\max\limits_{k=i+1}^{j-1}a_k[a_k<a_i]<L$
我们将一个相邻相同元素对 $(a_i,a_j)$ 记为一个二维点 $(lmax,val)$ ， $lmax=\max\limits_{k=i+1}^{j-1}a_k[a_k<a_i]$ ， $val=a_i$
那么询问就变成了：统计满足 $L<=val<=R且lmax<L$ 的点 $(lmax,val)$ 的个数
很经典的二位偏序了

# 代码

	#include<cstdio>
	#include<vector>
	#include<algorithm>

	int read(){
	int out(0),c(getchar());
	for(;c<'0' \|\| c>'9';c=getchar());
	for(;c<='9' && c>='0';c=getchar())
	out=(out<<3)+(out<<1)+(c^48);
	return out;
	}

	void Max(int &a,const int &b){
	if(b>a) a=b;
	}

	const int MAXN=1e6+10;

	int N,Q;
	int a[MAXN],cnt[MAXN];
	std::vector<int> pos[MAXN];
	int ans[MAXN];

	struct P{
	int lmax,val,i;
	bool operator < (const P &rv)const{
	return lmax<rv.lmax;
	}
	};

	std::vector<P> po,qu;

	struct SegTree{
	int tr[MAXN<<2];
	void mdf(int p,int l,int r,int ll,int val){
	if(l==r)
	return Max(tr[p],val);
	int mid=l+r>>1;
	if(ll<=mid)
	mdf(p<<1,l,mid,ll,val);
	else
	mdf(p<<1\|1,mid+1,r,ll,val);
	Max(tr[p],tr[p<<1]);
	Max(tr[p],tr[p<<1\|1]);
	}

	void que(int p,int l,int r,int ll,int rr,int &res){
	if(ll<=l && r<=rr)
	return Max(res,tr[p]);
	int mid=l+r>>1;
	if(ll<=mid)
	que(p<<1,l,mid,ll,rr,res);
	if(rr>mid)
	que(p<<1\|1,mid+1,r,ll,rr,res);
	}
	}s;



	struct BIT{
	int d[MAXN];
	static inline int lowbit(const int &x){return x&(-x);}
	void add(int x){
	for(;x<=N;x+=lowbit(x))
	d[x]++;
	}
	int que(int x){
	int res=0;
	for(;x;x-=lowbit(x))
	res+=d[x];
	return res;
	}
	int que(int l,int r){
	if(l>r) return 0;
	return que(r)-que(l-1);
	}
	}b;

	int main(){
	// freopen("F.in","r",stdin);
	N=read(),Q=read();
	for(int i=1;i<=N;++i){
	pos[a[i]=read()].push_back(i);
	++cnt[a[i]];
	}
	for(int i=1;i<=N;++i)
	cnt[i]+=cnt[i-1];
	for(int x=1;x<=N;++x){
	for(int i=0;i<(int)pos[x].size()-1;++i){
	int pl=pos[x][i]+1,pr=pos[x][i+1]-1;
	if(pl<=pr){
	int lmax=0;
	s.que(1,1,N,pl,pr,lmax);
	po.push_back({lmax,x});
	}
	else
	po.push_back({0,x});
	}
	for(int c:pos[x])
	s.mdf(1,1,N,c,x);
	}
	std::sort(po.begin(),po.end());
	for(int i=1;i<=Q;++i){
	int l=read(),r=read();
	qu.push_back({l,r,i});
	}
	std::sort(qu.begin(),qu.end());
	int pol=0;
	for(int t=0;t<qu.size();++t){
	int l=qu[t].lmax,r=qu[t].val,i=qu[t].i;
	while(pol<po.size() && po[pol].lmax<l)
	b.add(po[pol++].val);
	ans[i]=cnt[r]-cnt[l-1]-b.que(l,r);
	}
	for(int i=1;i<=Q;++i)
	printf("%d\n",ans[i]);
	return 0;
	}

区间问题偏序