題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)長(zhǎng)度為 $n$ 的數(shù)列，需要回答 $m$ 次詢問(wèn)，每次詢問(wèn)的格式如下： $lrk$，需要回答區(qū)間 $[l,r]$ 內(nèi)，所有長(zhǎng)度為 $k$ 的子區(qū)間中，最小值的最大值是多少，即在 $[l,r]$ 中選擇一段長(zhǎng)度為 $k$ 的子區(qū)間，使得其最小值最大

題目分析：求最小值的最大值不難想到二分，所以現(xiàn)在問(wèn)題轉(zhuǎn)換為了對(duì)于詢問(wèn)$lrk$，以及已經(jīng)知道了最大值為 $mmax$ 后，如何進(jìn)行 $check$

應(yīng)該算是一個(gè)比較經(jīng)典的模型吧，就是令 $[l,r]$ 內(nèi)所有大于等于 $mmax$ 的數(shù)置為 $1$，其余的數(shù)置為 $0$，然后問(wèn)題就轉(zhuǎn)換為了：區(qū)間 $[l,r]$ 內(nèi)最長(zhǎng)的連續(xù)的 $1$ 的子段長(zhǎng)度是否大于等于 $k$

維護(hù)大于等于某個(gè)閾值時(shí)的所有位置可以用主席樹(shù)實(shí)現(xiàn)，而查找區(qū)間內(nèi)最長(zhǎng)的連續(xù)的 $1$ 的子段長(zhǎng)度可以用區(qū)間合并實(shí)現(xiàn)，組合起來(lái)就是這個(gè)題目的解法了，主席樹(shù)的區(qū)間合并

實(shí)現(xiàn)的話可以直接重載一下加法運(yùn)算符，寫起來(lái)比直接合并要簡(jiǎn)單不少

代碼：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #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> #include<bitset> #include<unordered_map> using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9) write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e5+100; int a[N],root[N],cnt; vector<int>node,id[N]; struct Node {int ls,rs,l,r,id;int ll,rr,all;Node ZERO(){return {ls,rs,l,r,id,0,0,0};}friend Node operator+(Node a,Node b){Node c={a.id,b.id};c.ll=a.ll,c.rr=b.rr;if(a.ll==a.r-a.l+1) c.ll+=b.ll;if(b.rr==b.r-b.l+1) c.rr+=a.rr;c.all=max({a.all,b.all,a.rr+b.ll});return c;} }tree[N*20]; void update(int &k,int l,int r,int pos) {tree[++cnt]=tree[k],k=cnt;tree[k].l=l,tree[k].r=r,tree[k].id=k;if(l==r){tree[k].ll=tree[k].rr=tree[k].all=1;return;}int mid=(l+r)>>1;if(pos<=mid) update(tree[k].ls,l,mid,pos);else update(tree[k].rs,mid+1,r,pos);tree[k]=tree[tree[k].ls]+tree[tree[k].rs],tree[k].l=l,tree[k].r=r,tree[k].id=k; } Node query(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l) return tree[k].ZERO();if(tree[k].l>=l&&tree[k].r<=r) return tree[k];return query(tree[k].ls,l,r)+query(tree[k].rs,l,r); } void discreate(int n) {sort(node.begin(),node.end());node.erase(unique(node.begin(),node.end()),node.end());for(int i=1;i<=n;i++)//桶排id[lower_bound(node.begin(),node.end(),a[i])-node.begin()].push_back(i); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;read(n);for(int i=1;i<=n;i++) read(a[i]),node.push_back(a[i]);discreate(n);int sz=node.size();for(int i=sz-1;i>=0;i--){root[i]=root[i+1];for(auto it:id[i]) update(root[i],1,n,it);}int m;read(m);while(m--){int x,y,k;read(x),read(y),read(k);int l=0,r=sz-1,ans=-1;while(l<=r){int mid=(l+r)>>1;if(query(root[mid],x,y).all>=k) ans=mid,l=mid+1;else r=mid-1;}write(node[ans]),putchar('\n');}return 0; }

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 484E Sign on Fence(主席树区间合并+二分)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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