傳送門

Description

一個長度為\(n\)的序列\(a\)，設其排過序之后為\(b\)，其中位數定義為\(b[n/2]\)，其中\(a,b\)從\(0\)開始標號,除法取下整。

給你一個長度為n的序列\(s\)。

回答\(Q\)個這樣的詢問：\(s\)的左端點在\([a,b]\)之間,右端點在\([c,d]\)之間的子序列中，最大的中位數。

其中\(a<b<c<d\)。

位置也從\(0\)開始標號,強制在線

Solution

求中位數有一個很常見的做法，二分一個答案，把大于等于它的數設為\(1\),小于它的數設為\(1\)

這樣，如果區間和大于等于\(0\)，中位數顯然會大于等于當前答案

可以對每個權值都建一個線段樹，當然可以用主席樹來實現

check的時候，我們顯然需要得到區間最大值，對\([a,b]\)求后綴最大值，\([b+1,c-1]\)區間求和，\([c,d]\)求前綴最大值即可

調了很久，一直都是\(95\)分，結果是id[i-1].size-1寫成了id[i-1].size，我倒了

Code?

#include<bits/stdc++.h> #define ll long long #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) using namespace std; inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f; } #define MN 20005 int n,N,val[MN],nn[MN],root[MN]; std::vector<int> id[MN]; struct Node{int ls,rs,lm,rm,s;}t[MN*50];int sz; #define mid ((l+r)>>1) #define lson t[x].ls #define rson t[x].rs inline void up(int x) {t[x].s=t[lson].s+t[rson].s;t[x].rm=max(t[rson].rm,t[lson].rm+t[rson].s);t[x].lm=max(t[lson].lm,t[rson].lm+t[lson].s); } inline void Build(int &x,int l,int r) {x=++sz;if(l==r) return (void)(t[x]=(Node){0,0,1,1,1});Build(lson,l,mid);Build(rson,mid+1,r);up(x); } inline void Modify(int &x,int l,int r,int p) {t[++sz]=t[x];x=sz;if(l==r){t[x].s=t[x].lm=t[x].rm=-1;return;}p<=mid?Modify(lson,l,mid,p):Modify(rson,mid+1,r,p);up(x); } #define P std::pair<int,int> inline P QR(int x,int l,int r,int a,int b) {if(a==l&&r==b) return std::make_pair(t[x].rm,t[x].s);if(b<=mid) return QR(lson,l,mid,a,b);if(a>mid) return QR(rson,mid+1,r,a,b);P L=QR(lson,l,mid,a,mid),R=QR(rson,mid+1,r,mid+1,b);return std::make_pair(max(L.first+R.second,R.first),L.second+R.second); } inline P QL(int x,int l,int r,int a,int b) {if(a==l&&r==b) return std::make_pair(t[x].lm,t[x].s);if(b<=mid) return QL(lson,l,mid,a,b);if(a>mid) return QL(rson,mid+1,r,a,b);P L=QL(lson,l,mid,a,mid),R=QL(rson,mid+1,r,mid+1,b);return std::make_pair(max(R.first+L.second,L.first),L.second+R.second); } inline int QS(int x,int l,int r,int a,int b) {if(a>b) return 0;if(a==l&&r==b) return t[x].s;if(b<=mid) return QS(lson,l,mid,a,b);if(a>mid) return QS(rson,mid+1,r,a,b);return QS(lson,l,mid,a,mid)+QS(rson,mid+1,r,mid+1,b); } inline bool check(int a,int b,int c,int d,int v) {int Ans=QR(root[v],1,n,a,b).first+QS(root[v],1,n,b+1,c-1)+QL(root[v],1,n,c,d).first;return Ans>=0; } int main() {n=read();register int i,j;for(i=1;i<=n;++i) nn[i]=val[i]=read();std::sort(nn+1,nn+n+1);N=std::unique(nn+1,nn+n+1)-nn-1;for(i=1;i<=n;++i) val[i]=std::lower_bound(nn+1,nn+N+1,val[i])-nn,id[val[i]].push_back(i);Build(root[1],1,n);for(i=2;i<=N;++i){root[i]=root[i-1];for(j=id[i-1].size()-1;~j;--j) Modify(root[i],1,n,id[i-1][j]);}register int Q=read(),a[6],x=0,l,r;while(Q--){for(i=0;i<4;++i) a[i]=(read()+x)%n+1;std::sort(a,a+4);for(x=l=1,r=N;l<=r;check(a[0],a[1],a[2],a[3],mid)?(x=mid,l=mid+1):r=mid-1);printf("%d\n",x=nn[x]);}return 0; }

---

Blog來自PaperCloud，未經允許，請勿轉載，TKS！

轉載于:https://www.cnblogs.com/PaperCloud/p/10273093.html

總結

以上是生活随笔為你收集整理的[bzoj 2653][国家集训队]middle的全部內容，希望文章能夠幫你解決所遇到的問題。

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