傳送門

文章目錄

• 題意：
• 思路：

題意：

思路：

我們先解決怎么判斷中位數的問題，我們可以二分一個$mid$，將$<mid$的值都變成$?1$，其他的數都變成$1$，那么當全部的和$>=0$的時候，就說明當前數可以為中位數，且可能會變得更大，讓后繼續二分判斷就好。
以上過程的復雜度是$O(qnlogn)$的，顯然不能接受，但是可以發現我們的預處理之后的數組是可以遞推出來的，不需要每次都算一遍，比如當前$mid$為$1$，那么就全都是$1$，$mid$為$2$的時候，只需要將$1$改成$?1$即可，這個過程我們可以用主席樹可持久化一下，$root$的下標為中位數的值的位置。
讓后我們考慮怎么判斷區間選擇哪個，首先我們可以發現$[b+1,c?1]$這個區間內的數是必選的，所以直接將$[b+1,c?1]$區間和加上即可。讓后再就是$[a,b]$和$[c,d]$，對于$[a,b]$我們只需要取一個最長后綴，$[c,d]$我們只需要取一個最長前綴，讓后判斷$sum+ls+rs>=0$即可。
以下有兩種寫法。

//#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=100010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n,m; int x[N]; int root[N],tot; vector<int>v,pos[N]; struct Query {int val,id;bool operator < (const Query &W) const{return val<W.val;} }a[N]; struct Node {int l,r;int ls,rs,sum; }tr[N*40];int find(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1; }void pushup(int u) {tr[u].sum=tr[tr[u].l].sum+tr[tr[u].r].sum;tr[u].ls=max(tr[tr[u].l].ls,tr[tr[u].l].sum+tr[tr[u].r].ls);tr[u].rs=max(tr[tr[u].r].rs,tr[tr[u].r].sum+tr[tr[u].l].rs); }int build(int l,int r) {int p=++tot;if(l==r){tr[p].ls=tr[p].rs=tr[p].sum=1;return p;}int mid=l+r>>1;tr[p].l=build(l,mid);tr[p].r=build(mid+1,r);pushup(p);return p; }void insert(int p,int &q,int l,int r,int pos) {q=++tot; tr[q]=tr[p];if(l==r){tr[q].ls=tr[q].rs=tr[q].sum=-1;return;}int mid=l+r>>1;if(pos<=mid) insert(tr[p].l,tr[q].l,l,mid,pos);else insert(tr[p].r,tr[q].r,mid+1,r,pos);pushup(q); }int query_sum(int u,int l,int r,int ql,int qr) {if(!u) return 0;if(l>=ql&&r<=qr) return tr[u].sum;int ans=0,mid=l+r>>1;if(ql<=mid) ans+=query_sum(tr[u].l,l,mid,ql,qr);if(qr>mid) ans+=query_sum(tr[u].r,mid+1,r,ql,qr);return ans; }Node query_ls(int u,int l,int r,int ql,int qr) {if(!u) return {0,0,0,0,0};if(l>=ql&&r<=qr) return tr[u];Node ans;int mid=l+r>>1;if(qr<=mid) ans=query_ls(tr[u].l,l,mid,ql,qr);else if(ql>mid) ans=query_ls(tr[u].r,mid+1,r,ql,qr);else{Node a,b;a=query_ls(tr[u].l,l,mid,ql,qr);b=query_ls(tr[u].r,mid+1,r,ql,qr);ans.sum=a.sum+b.sum;ans.ls=max(a.ls,a.sum+b.ls);}return ans; }Node query_rs(int u,int l,int r,int ql,int qr) {if(!u) return {0,0,0,0,0};if(l>=ql&&r<=qr) return tr[u];Node ans;int mid=l+r>>1;if(qr<=mid) ans=query_rs(tr[u].l,l,mid,ql,qr);else if(ql>mid) ans=query_rs(tr[u].r,mid+1,r,ql,qr);else{Node a,b;a=query_rs(tr[u].l,l,mid,ql,qr);b=query_rs(tr[u].r,mid+1,r,ql,qr);ans.sum=a.sum+b.sum;ans.rs=max(b.rs,b.sum+a.rs);}return ans; }int check(int mid) {int add=0,ls,rs;if(x[2]+1<=x[3]-1) add=query_sum(root[mid],1,n,x[2]+1,x[3]-1);ls=query_rs(root[mid],1,n,x[1],x[2]).rs;rs=query_ls(root[mid],1,n,x[3],x[4]).ls;return (ls+rs+add)>=0; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i].val),a[i].id=i;sort(a+1,a+1+n);root[1]=build(1,n);for(int i=2;i<=n;i++) insert(root[i-1],root[i],1,n,a[i-1].id);scanf("%d",&m);int ans=0;while(m--){int aa,b,c,d; scanf("%d%d%d%d",&aa,&b,&c,&d);x[1]=(aa+ans)%n; x[2]=(b+ans)%n;x[3]=(c+ans)%n; x[4]=(d+ans)%n;x[1]++; x[2]++; x[3]++; x[4]++;sort(x+1,x+1+4);int ll=1,rr=n,anss=0;while(ll<=rr){int mid=ll+rr>>1;if(check(mid)) anss=mid,ll=mid+1;else rr=mid-1;}printf("%d\n",ans=a[anss].val);}return 0; } /* 5 1 1 1 1 1 1 0 1 2 3 */ //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=100010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n,m; int a[N],x[N]; int root[N],tot; vector<int>v,pos[N]; struct Node {int l,r;int ls,rs,sum; }tr[N*40];int find(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1; }void pushup(int u) {tr[u].sum=tr[tr[u].l].sum+tr[tr[u].r].sum;tr[u].ls=max(tr[tr[u].l].ls,tr[tr[u].l].sum+tr[tr[u].r].ls);tr[u].rs=max(tr[tr[u].r].rs,tr[tr[u].r].sum+tr[tr[u].l].rs); }int build(int l,int r) {int p=++tot;if(l==r){tr[p].ls=tr[p].rs=tr[p].sum=1;return p;}int mid=l+r>>1;tr[p].l=build(l,mid);tr[p].r=build(mid+1,r);pushup(p);return p; }void insert(int p,int &q,int l,int r,int pos,int x) {q=++tot; tr[q]=tr[p];if(l==r){tr[q].ls=tr[q].rs=tr[q].sum=-1;return;}int mid=l+r>>1;if(pos<=mid) insert(tr[p].l,tr[q].l,l,mid,pos,x);else insert(tr[p].r,tr[q].r,mid+1,r,pos,x);pushup(q); }int query_sum(int u,int l,int r,int ql,int qr) {if(!u) return 0;if(l>=ql&&r<=qr) return tr[u].sum;int ans=0,mid=l+r>>1;if(ql<=mid) ans+=query_sum(tr[u].l,l,mid,ql,qr);if(qr>mid) ans+=query_sum(tr[u].r,mid+1,r,ql,qr);return ans; }Node query_ls(int u,int l,int r,int ql,int qr) {if(!u) return {0,0,0,0,0};if(l>=ql&&r<=qr) return tr[u];Node ans;int mid=l+r>>1;if(qr<=mid) ans=query_ls(tr[u].l,l,mid,ql,qr);else if(ql>mid) ans=query_ls(tr[u].r,mid+1,r,ql,qr);else{Node a,b;a=query_ls(tr[u].l,l,mid,ql,qr);b=query_ls(tr[u].r,mid+1,r,ql,qr);ans.sum=a.sum+b.sum;ans.ls=max(a.ls,a.sum+b.ls);}return ans; }Node query_rs(int u,int l,int r,int ql,int qr) {if(!u) return {0,0,0,0,0};if(l>=ql&&r<=qr) return tr[u];Node ans;int mid=l+r>>1;if(qr<=mid) ans=query_rs(tr[u].l,l,mid,ql,qr);else if(ql>mid) ans=query_rs(tr[u].r,mid+1,r,ql,qr);else{Node a,b;a=query_rs(tr[u].l,l,mid,ql,qr);b=query_rs(tr[u].r,mid+1,r,ql,qr);ans.sum=a.sum+b.sum;ans.rs=max(b.rs,b.sum+a.rs);}return ans; }int check(int mid) {int add=0,ls,rs;if(x[2]+1<=x[3]-1) add=query_sum(root[mid],1,n,x[2]+1,x[3]-1);ls=query_rs(root[mid],1,n,x[1],x[2]).rs;rs=query_ls(root[mid],1,n,x[3],x[4]).ls;return (ls+rs+add)>=0; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]),v.pb(a[i]);sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());for(int i=1;i<=n;i++) pos[find(a[i])].pb(i);root[1]=build(1,n);for(int i=2;i<=(int)v.size();i++){root[i]=root[i-1];for(auto x:pos[i-1])insert(root[i],root[i],1,n,x,-1);}scanf("%d",&m);int ans=0;while(m--){int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d);x[1]=(a+ans)%n; x[2]=(b+ans)%n;x[3]=(c+ans)%n; x[4]=(d+ans)%n;x[1]++; x[2]++; x[3]++; x[4]++;sort(x+1,x+1+4);int ll=1,rr=(int)v.size(),anss=0;while(ll<=rr){int mid=ll+rr>>1;if(check(mid)) anss=mid,ll=mid+1;else rr=mid-1;}printf("%d\n",ans=v[anss-1]);}return 0; } /* 5 1 1 1 1 1 1 0 1 2 3 */

總結

以上是生活随笔為你收集整理的P2839 [国家集训队]middle 二分 + 主席树 在值域上建区间的全部內容，希望文章能夠幫你解決所遇到的問題。

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