題意：給你一個序列，求滿足要求的子序列個數(shù)，其中要求為：

1、子序列的max-子序列長度len<=k

2、子序列中不出現(xiàn)重復的數(shù)字

題解：首先看到子序列max，很容易想到枚舉最大值然后分治，這個做法有人通過，但是我并沒想到如何做

子序列max還有一個思路是單調(diào)隊列，這里我們通過單調(diào)隊列進行解題

首先對于給出的限制條件式子max-(r-l+1)<=k，我們進行移項，可得max+l<=k+r+1，此時我們將l和r分離至不等式兩邊

容易看出我們可以枚舉右端點，然后維護一個權(quán)值線段樹，每次只需要查詢1~k+r+1區(qū)間的sum就可以了

以max+l作為權(quán)值建線段樹

那么容易想到用單調(diào)隊列進行維護max，每次更新單調(diào)隊列的時候相當于在權(quán)值線段樹上的一個區(qū)間進行+1/-1操作

單調(diào)隊列維護：值，位置，這個值的左端點

維護單調(diào)隊列時為了滿足子序列不出現(xiàn)重復數(shù)字，于是考慮雙向單調(diào)隊列

新枚舉右端點時，單調(diào)隊列從右往左退棧，直到第一個不小于右端點數(shù)字的位置

然后考慮此時的最左邊能到哪里

考慮記下每一個位置的前驅(qū)位置，即前一個相同數(shù)字在哪

容易想到維護一個最大值表示當前的最左端點在哪，每新枚舉一個右端點，那么將last[i]+1和當前的左端點取個max，即為新的左端點，顯然這樣是當前右端點下最大的滿足條件的左端點

于是單調(diào)隊列從左往右退棧，直到第一個下標大于等于左端點的位置，然后再更新單調(diào)隊列里維護的左端點

至此則可以在nlogn的時間內(nèi)求出答案

時間復雜度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; }

心得：區(qū)間max的處理方法不僅有枚舉max然后分治，還有單調(diào)隊列，思維不要唯一，要多想一些

轉(zhuǎn)載于:https://www.cnblogs.com/worcher/p/11391728.html

總結(jié)

以上是生活随笔為你收集整理的【HDU6701】Make Rounddog Happy【权值线段树+双向单调队列】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。