前几天想用Github+org-mode替代这个博客，后来想了想，还是算了吧。毕竟博客对大家更方便。

这个题真不愧是陈老师的题啊……exciting！

首先我们看到左端点在[tex][a,b][/tex]，右端点在[tex][c,d][/tex]，一股GSS5的气味扑来？

为了方便，我们先将序列离散化。然后我们将序列中大于等于x的值变为1，小于x的值变为-1，则某段区间的区间和若大于等于0，则该区间的中位数大于等于x，反之则其中位数小于x（注意，此题的中位数定义比较奇怪）。

然后我们可以对每个x建一棵树，然后二分答案，对于每个答案在对应的树上跑一遍GSS5即可（不过这题[tex]a<b<c<d[/tex]，所以不需要复杂的分类讨论）。

但是如果每个x都建一棵树，肯定会MLE吧？这个时候就要用主席树了= =

代码：

/**************************************************************
    Problem: 2653
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2220 ms
    Memory:1956 kb
****************************************************************/
 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=20005;
struct Node{
  Node *lc,*rc;
  int maxPSum,maxSSum,sum;
  Node(int x){
    lc=rc=NULL;
    maxPSum=maxSSum=sum=x;
  }
  Node(Node *l,Node *r){
    lc=l;rc=r;
  }
  void maintain(){
    maxPSum=max(lc->maxPSum,lc->sum+rc->maxPSum);
    maxSSum=max(rc->maxSSum,rc->sum+lc->maxSSum);
    sum=lc->sum+rc->sum;
  }
};
Node* build_tree(int L,int R){
  if(L==R){
    return new Node(1);
  }
  int M=L+(R-L)/2;
  Node *ans=new Node(build_tree(L,M),build_tree(M+1,R));
  ans->maintain();
  return ans;
}
int p,v;
Node* insert(Node *o,int L,int R){
  if(L==R){
    return new Node(v);
  }else{
    Node *ans=new Node(o->lc,o->rc);
    int M=L+(R-L)/2;
    if(p<=M){
      ans->lc=insert(ans->lc,L,M);
    }else{
      ans->rc=insert(ans->rc,M+1,R);
    }
    ans->maintain();
    return ans;
  }
}
int ql,qr;
Node queryPSum(Node *o,int L,int R){
  if(ql<=L && R<=qr){
    return *o;
  }else{
    int M=L+(R-L)/2;
    if(qr<=M){
      return queryPSum(o->lc,L,M);
    }else{
      if(ql<=M){
        Node l=queryPSum(o->lc,L,M);
        Node r=queryPSum(o->rc,M+1,R);
        Node ans(l.sum+r.sum);
        ans.maxPSum=max(l.maxPSum,l.sum+r.maxPSum);
        return ans;
      }else{
        return queryPSum(o->rc,M+1,R);
      }
    }
  }
}
Node querySSum(Node *o,int L,int R){
  if(ql<=L && R<=qr){
    return *o;
  }else{
    int M=L+(R-L)/2;
    if(qr<=M){
      return querySSum(o->lc,L,M);
    }else{
      if(ql<=M){
        Node l=querySSum(o->lc,L,M);
        Node r=querySSum(o->rc,M+1,R);
        Node ans(l.sum+r.sum);
        ans.maxSSum=max(r.maxSSum,r.sum+l.maxSSum);
        return ans;
      }else{
        return querySSum(o->rc,M+1,R);
      }
    }
  }
}
int querySum(Node *o,int L,int R){
  if(ql<=L && R<=qr){
    return o->sum;
  }else{
    int M=L+(R-L)/2;
    int ans=0;
    if(ql<=M){
      ans+=querySum(o->lc,L,M);
    }
    if(qr>M){
      ans+=querySum(o->rc,M+1,R);
    }
    return ans;
  }
}
Node *root[maxn];
 
int n;
int A[maxn],A2[maxn];
vector<int> V[maxn];
int lsh_siz;
inline void lsh(){
  sort(A2+1,A2+1+n);
  lsh_siz=unique(A2+1,A2+1+n)-A2-1;
  for(register int i=1;i<=n;i++){
    A[i]=lower_bound(A2+1,A2+1+lsh_siz,A[i])-A2;
    V[A[i]].push_back(i);
  }
}
int q[4];
inline bool Check(int M){
  register int l,m,r;
  if(q[1]+1<=q[2]-1){
    ql=q[1]+1;
    qr=q[2]-1;
    m=querySum(root[M],1,lsh_siz);
  }else{
    m=0;
  }
  ql=q[0];qr=q[1];
  l=querySSum(root[M],1,lsh_siz).maxSSum;
  ql=q[2];qr=q[3];
  r=queryPSum(root[M],1,lsh_siz).maxPSum;
#ifdef DEBUG
  printf("Case %d: %d %d %d\n",M,l,m,r);
#endif
  return l+m+r>=0;
}
int main(){
  register int i,j,L,M,R,ans=0;
  int t;
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d",&A[i]);
    A2[i]=A[i];
  }
  lsh();
  root[1]=build_tree(1,n);
  for(i=2;i<=lsh_siz;i++){
    root[i]=root[i-1];
    for(j=0;j<V[i-1].size();j++){
      p=V[i-1][j];
      v=-1;
      root[i]=insert(root[i],1,lsh_siz);
    }
  }
  scanf("%d",&t);
  while(t--){
    for(i=0;i<4;i++){
      scanf("%d",&q[i]);
      q[i]=(q[i]+ans)%n;
    }
    sort(q,q+4);
    for(i=0;i<4;i++){
      q[i]++;
      #ifdef DEBUG
      printf("%d ",q[i]);
      if(i==3){
        puts("");
      }
      #endif
    }
    L=1;R=lsh_siz;
    while(true){
      if(R-L<=3){
        for(i=R;i>=L;i--){
          if(Check(i)){
            ans=A2[i];
            break;
          }
        }
        break;
      }
      M=L+(R-L)/2;
      if(Check(M)){
        L=M;
      }else{
        R=M;
      }
    }
    printf("%d\n",ans);
  }
  return 0;
}

• 相关文章
• 全局相关文章