题解 P7416 [USACO21FEB] No Time to Dry P

· · 题解

题目传送门

题意简述：给出颜色序列 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;
}