题意：给你一个序列，求满足要求的子序列个数，其中要求为：
1、子序列的max-子序列长度len<=k
2、子序列中不出现重复的数字
题解：首先看到子序列max，很容易想到枚举最大值然后分治，这个做法有人通过，但是我并没想到如何做
子序列max还有一个思路是单调队列，这里我们通过单调队列进行解题
首先对于给出的限制条件式子max-(r-l+1)<=k，我们进行移项，可得max+l<=k+r+1，此时我们将l和r分离至不等式两边
容易看出我们可以枚举右端点，然后维护一个权值线段树，每次只需要查询1~k+r+1区间的sum就可以了
以max+l作为权值建线段树
那么容易想到用单调队列进行维护max，每次更新单调队列的时候相当于在权值线段树上的一个区间进行+1/-1操作
单调队列维护：值，位置，这个值的左端点
维护单调队列时为了满足子序列不出现重复数字，于是考虑双向单调队列
新枚举右端点时，单调队列从右往左退栈，直到第一个不小于右端点数字的位置
然后考虑此时的最左边能到哪里
考虑记下每一个位置的前驱位置，即前一个相同数字在哪
容易想到维护一个最大值表示当前的最左端点在哪，每新枚举一个右端点，那么将last[i]+1和当前的左端点取个max，即为新的左端点，显然这样是当前右端点下最大的满足条件的左端点
于是单调队列从左往右退栈，直到第一个下标大于等于左端点的位置，然后再更新单调队列里维护的左端点
至此则可以在nlogn的时间内求出答案
时间复杂度O(nlogn)
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #define ll long long using namespace std; int T; int n,k; int a[300001],last[300001],hd[300001]; int lh[300001],mx[300001],mxi[300001],ln,rn; ll ans; class Segtree { public: ll v[600001*5],flv[600001*5]; bool fl[600001*5]; void init() { memset(v,0,sizeof(v)); memset(fl,0,sizeof(fl)); memset(flv,0,sizeof(flv)); } void pushdown(int l,int r,int pos) { if(fl[pos]) { int mid=l+r>>1; v[pos<<1]+=flv[pos]*(mid-l+1); v[pos<<1|1]+=flv[pos]*(r-mid); flv[pos<<1]+=flv[pos]; flv[pos<<1|1]+=flv[pos]; fl[pos<<1]=fl[pos<<1|1]=1; fl[pos]=0;flv[pos]=0; } } void pushup(int pos) { v[pos]=v[pos<<1]+v[pos<<1|1]; } void change(int l,int r,int al,int ar,ll tv,int pos) { if(l==al && r==ar) { v[pos]+=tv*(ar-al+1); fl[pos]=1; flv[pos]+=tv; return; } pushdown(l,r,pos); int mid=l+r>>1; if(ar<=mid)change(l,mid,al,ar,tv,pos<<1); if(al>mid)change(mid+1,r,al,ar,tv,pos<<1|1); if(al<=mid && ar>mid) { change(l,mid,al,mid,tv,pos<<1); change(mid+1,r,mid+1,ar,tv,pos<<1|1); } pushup(pos); } ll ask(int l,int r,int al,int ar,int pos) { if(l==al && r==ar)return v[pos]; int mid=l+r>>1; pushdown(l,r,pos); if(ar<=mid)return ask(l,mid,al,ar,pos<<1); if(al>mid)return ask(mid+1,r,al,ar,pos<<1|1); if(al<=mid && ar>mid)return ask(l,mid,al,mid,pos<<1)+ask(mid+1,r,mid+1,ar,pos<<1|1); } }segtree; int main() { scanf("%d",&T); while(T--) { segtree.init(); ans=0; memset(hd,0,sizeof(hd)); memset(last,0,sizeof(last)); scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); last[i]=hd[a[i]]; hd[a[i]]=i; } ln=1;rn=0;int tl,tl2=0; for(int i=1;i<=n;i++) { tl=i;tl2=max(tl2,last[i]+1); while(ln<=rn && mx[rn]<a[i]) { tl=min(tl,lh[rn]); segtree.change(1,n*2,mx[rn]+lh[rn],mx[rn]+mxi[rn],-1,1); rn--; } segtree.change(1,n*2,a[i]+tl,a[i]+i,1,1); rn++; lh[rn]=tl;mx[rn]=a[i];mxi[rn]=i; while(ln<=rn && mxi[ln]<tl2) { segtree.change(1,n*2,mx[ln]+lh[ln],mx[ln]+mxi[ln],-1,1); ln++; } if(ln<=rn && lh[ln]<tl2) { segtree.change(1,n*2,mx[ln]+lh[ln],mx[ln]+tl2-1,-1,1); lh[ln]=tl2; } ans+=segtree.ask(1,n*2,1,min(i+k+1,n*2),1); } printf("%lld\n",ans); } return 0; }
心得：区间max的处理方法不仅有枚举max然后分治，还有单调队列，思维不要唯一，要多想一些