C
题意：
就是给你一个数组。接下来他会进行 qqq 次询问，每次询问将 给出两个数字 lll 与 rrr ，要你把 [l,r][l, r][l,r] 区间划分为若干个片段[l1,r1],[l2,r2],…,[lk,rk]\left[l_{1}, r_{1}\right],\left[l_{2}, r_{2}\right], \ldots,\left[l_{k}, r_{k}\right][l1,r1],[l2,r2],…,[lk,rk] 。要求对于任意一个片 段 [li,ri]，a[li]\left[l_{i}, r_{i}\right] ， a\left[l_{i}\right][li,ri]，a[li] 为这个片段中的最大值。牛拉底鲁想要最小化片段的数量，因此对于每次询 问，请你回答出 kkk 的最小值。
思考：
很明显，想要分最少就是贪心往后走，再转化一下就是以a[l]为起点最长的上升序列就是k。但是每次都求一遍这个k肯定超时。然后我发现，可以用维护前缀和呀，就是从后往前走，这个点的sum就是右边第一个比他大的sum+1。然后每次查询的答案就是sum[l]-sum[r]+1。但是提交WA了，然后写了几个样例发现，对于数据1 2 10 1 2查询[1,4]，如果这样做答案是3-2+1 = 2，实际上答案是3。也就是对于sum[l]不是减去sum[r]，而是减去这段区间最大的第一个出现的数的位置idx。为什么呢，因为最大的数后面都可以被这个数给包起来，这样答案就不会出错了。所以线段树维护区间最值，然后set存每个值的下标。idx就是set[maxn]中第一个>=l的位置。
代码：
#include<bits/stdc++.h>#define fi first#define se second#define pb push_back#define db double#define int long long#define PII pair<int,int >#define mem(a,b) memset(a,b,sizeof(a))#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);#define node_l node<<1#define node_r node<<1|1using namespace std;const int mod = 1e9+7,inf = 1e18;const int N = 1e5+10,M = ;struct Node{int L,R;int maxn;}t[4*N];int T,n,m,k;int va[N];int sum[N];int tr[N],R = 1e5+5;vector<int > v;set<int > s[N];void build(int node,int l,int r){t[node].L = l,t[node].R = r;if(l==r){t[node].maxn = va[l];return ;}int mid = (l+r)>>1;build(node_l,l,mid);build(node_r,mid+1,r);t[node].maxn = max(t[node_l].maxn,t[node_r].maxn);}int query(int node,int l,int r){if(t[node].L>=l&&t[node].R<=r) return t[node].maxn;int mid = (t[node].L+t[node].R)>>1;if(r<=mid) return query(node_l,l,r);else if(l>mid) return query(node_r,l,r);else return max(query(node_l,l,mid),query(node_r,mid+1,r));}int get(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}int bit(int x){return x&(-x);}void update(int x,int value){while(x){tr[x] = min(tr[x],value);x -= bit(x);}}int query(int x){int minn = inf;while(x<=R){minn = min(minn,tr[x]);x += bit(x);}return minn;}signed main(){IOS;cin>>n>>m;for(int i=0;i<=R;i++) tr[i] = inf;for(int i=1;i<=n;i++){cin>>va[i];v.pb(va[i]);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());for(int i=1;i<=n;i++){va[i] = get(va[i]);s[va[i]].insert(i);}build(1,1,n);for(int i=n;i>=1;i--){int idx = query(va[i]+1);if(idx==inf) sum[i] = 1;else sum[i] = sum[idx]+1;update(va[i],i);}while(m--){int a,b;cin>>a>>b;int maxn = query(1,a,b);auto idx = s[maxn].lower_bound(a);cout<<sum[a]-sum[*idx]+1<<"\n";}return 0;}
总结：
多多思考呀，注意细节和思路的正确性。
如果觉得《牛客练习赛85-哲学家的沉思-(上升子序列变形+树状数组+线段树+离散化+set)》对你有帮助，请点赞、收藏，并留下你的观点哦！
