題目鏈接：點擊查看
題目大意：給出一個長度為 n 的數列 a，再給出 m 次詢問，每次詢問假設如果設置?a[ pos ] = val 的話，那么此時序列中的最長上升子序列是多少，此時的上升子序列指的是：若選取 a[ 1 ] 后，找到下一個大于 a[ 1 ] 的位置記為 a[ pos ] ，依次類推
題目分析：考察區間合并的一道題目，因為這個題目對于最長上升子序列多加了一點限制，所以處理起來也并不是很復雜，假如現在有左區間和右區間需要合并，我們可以維護一下每個區間的最大值和貢獻，不難看出，左區間一定是有貢獻的，對于右區間來說還需要進一步討論：
如果右區間的最大值小于左區間的最大值，那么右區間的貢獻為 0如果右區間的左子區間的最大值小于左區間的最大值，那么左子區間的貢獻為 0 ，向右子區間遞歸如果右區間的左子區間的最大值大于左區間的最大值，那么左子區間的貢獻繼續遞歸，此時右子區間的貢獻已經不由左區間控制了，可以直接加上，根據 pushup 函數中的關系，移項可以得出右子區間對于整個區間的貢獻
最后強調一下，上面第三種情況，右子區間對于整個區間的貢獻，并不能單純的以 cnt[ k<<1|1 ] 為答案，因為在 pushup 中的公式為：cnt[ k ] = cnt[ k<<1 ] + cal() ，此處的 cal 函數計算的才是右子區間對于整個區間的貢獻，所以通過移項可以得出，此時右子區間的貢獻為 cnt[ k ] - cnt[ k<<1 ]
時間復雜度是雙 log 級別的，不過 n 只有 1e5 ，雙 log 的復雜度也是頂得住的
代碼：
?
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;int a[N];struct Node
{int l,r,mmax,cnt;
}tree[N<<2];int cal(int k,int h)
{if(tree[k].mmax<=h)return 0;if(tree[k].l==tree[k].r)return tree[k].mmax>h;int mid=tree[k].l+tree[k].r>>1;if(tree[k<<1].mmax<=h)return cal(k<<1|1,h);elsereturn cal(k<<1,h)+tree[k].cnt-tree[k<<1].cnt;
}void pushup(int k)
{tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax);tree[k].cnt=tree[k<<1].cnt+cal(k<<1|1,tree[k<<1].mmax);
}void build(int k,int l,int r)
{tree[k].l=l;tree[k].r=r;if(l==r){tree[k].mmax=a[l];tree[k].cnt=1;return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k);
}void change(int k,int pos,int val)
{if(tree[k].l==tree[k].r){tree[k].mmax=val;return;}int mid=tree[k].l+tree[k].r>>1;if(pos<=mid)change(k<<1,pos,val);elsechange(k<<1|1,pos,val);pushup(k);
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",a+i);build(1,1,n);while(m--){int pos,val;scanf("%d%d",&pos,&val);change(1,pos,val);printf("%d\n",tree[1].cnt);change(1,pos,a[pos]);}}return 0;
}
?
總結
以上是生活随笔為你收集整理的HDU - 6406 Taotao Picks Apples(线段树区间合并)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
