CodeForces - 484E Sign on Fence(主席树区间合并+二分)

题目链接：点击查看

题目大意：给出一个长度为 $n$ 的数列，需要回答 $m$ 次询问，每次询问的格式如下： $lrk$，需要回答区间 $[l,r]$ 内，所有长度为 $k$ 的子区间中，最小值的最大值是多少，即在 $[l,r]$ 中选择一段长度为 $k$ 的子区间，使得其最小值最大

题目分析：求最小值的最大值不难想到二分，所以现在问题转换为了对于询问$lrk$，以及已经知道了最大值为 $mmax$ 后，如何进行 $check$

应该算是一个比较经典的模型吧，就是令 $[l,r]$ 内所有大于等于 $mmax$ 的数置为 $1$，其余的数置为 $0$，然后问题就转换为了：区间 $[l,r]$ 内最长的连续的 $1$ 的子段长度是否大于等于 $k$

维护大于等于某个阈值时的所有位置可以用主席树实现，而查找区间内最长的连续的 $1$ 的子段长度可以用区间合并实现，组合起来就是这个题目的解法了，主席树的区间合并

实现的话可以直接重载一下加法运算符，写起来比直接合并要简单不少

代码：

// #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; }

总结

以上是生活随笔为你收集整理的CodeForces - 484E Sign on Fence(主席树区间合并+二分)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。