日子沒法過了呀！QAQ，啥玩意啊！以前寫過線段樹尋找區間最長連續子序列，這個不連續，覺得可以搞搞，然后思想誤區了，直接拿線段樹維護的區間，然后，，，，維護了整場比賽200多行的線段樹最后都沒搞出來，自閉了呀！比賽后想了想覺得為什么要用線段樹，維護一下更改數的前半段和后半段不就完了嗎。。。。。然后更自閉了，于是搞了一上午。

#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <cmath> #include <stack> using namespace std; const int maxn=1e5+100; struct note {int v;int id; }aa[maxn];//下面的注釋里用a[i]代替的aa[i].v做的解釋 int t,m,n; int tap[maxn];//以a[i]為起點到結尾組成的上升序列的元素個數 int tbp[maxn];//在i前面第一個”在上升序列中的數“的位置 int sum[maxn];//在i以前的”上升序列“的元素個數 int maxi[maxn<<2],mini[maxn<<2]; void build(int l,int r,int rt) {if(l==r){maxi[rt]=mini[rt]=aa[l].v;return;}int mid=(l+r)>>1;build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);maxi[rt]=max(maxi[rt<<1],maxi[rt<<1|1]);mini[rt]=min(mini[rt<<1],mini[rt<<1|1]); } int found(int x,int l,int r,int rt) {if(l==r){if(aa[l].v>=x) return l;else return -1;}int mid=(l+r)>>1;int zz=-1;if(maxi[rt<<1]>=x) zz=found(x,l,mid,rt<<1);else if(maxi[rt<<1|1]>=x){zz=found(x,mid+1,r,rt<<1|1);}return zz; } int query(int x,int L,int R,int l,int r,int rt)//必須先找到L-R的區間再查找，否則rt不對 {if(L<=l&&r<=R){return found(x,l,r,rt);}int mid=(l+r)>>1;int zz=-1;if(L<=mid) zz=query(x,L,R,l,mid,rt<<1);if(R>mid&&zz==-1) zz=query(x,L,R,mid+1,r,rt<<1|1);return zz; } int main() {scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);int cnt=0;for(int i=1;i<=n;i++){scanf("%d",&aa[i].v);aa[i].id=i;sum[i]=tap[i]=tbp[i]=0;}build(1,n,1);stack<note> st;st.push(aa[n]);tap[n]=1;for(int i=n-1;i>=1;i--)//單調棧維護從每一個a[i]到結尾形成的單調上升序列 {while(st.size()&&st.top().v<=aa[i].v){st.pop();}st.push(aa[i]);tap[aa[i].id]=st.size();//從每一個a[i]到結尾形成的單調上升序列的元素個數 }while(st.size()) st.pop();st.push(aa[1]);tbp[1]=-1;for(int i=2;i<=n;i++){tbp[i]=st.top().id;//前一個在”上升序列“中的元素的位置sum[i]=st.size();//在i以前的元素組成的”上升序列“的元素個數if(aa[i].v>st.top().v) st.push(aa[i]);//篩出一個原數組的”上升序列“ }int p,v;for(int i=1;i<=m;i++){scanf("%d%d",&p,&v);int ans=0,hh;if(p!=1)//更改的不是第一個數 {ans+=sum[p];if(aa[tbp[p]].v<v) ans++;//v比在p前一個在”上升序列“中的那個元素大，那么要算上這個元素，故ans++hh=max(aa[tbp[p]].v,v);}else//更改的是第一個數 {hh=v;ans++;//自己就是第一個元素，當然要加上 }int ff=query(hh+1,p+1,n,1,n,1);//尋找在p之后第一個比hh大的位置if(ff!=-1) ans+=tap[ff];printf("%d\n",ans);}}return 0; }

?

轉載于:https://www.cnblogs.com/Wangwanxiang/p/9486455.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的hdu 6406（思路+数据结构）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。