[bzoj2653][middle] (二分 + 主席树)

时间：2021-11-14 19:14:29

Description

　　一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。
　　给你一个长度为n的序列s。
　　回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。
　　其中a<b<c<d。
　　位置也从0开始标号。
　　我会使用一些方式强制你在线。

Input

　　第一行序列长度n。
　　接下来n行按顺序给出a中的数。
　　接下来一行Q。
　　然后Q行每行a,b,c,d，我们令上个询问的答案是x(如果这是第一个询问则x=0)。
　　令数组q={(a+x)%n,(b+x)%n,(c+x)%n,(d+x)%n}。
　　将q从小到大排序之后，令真正的要询问的a=q[0],b=q[1],c=q[2],d=q[3]。
　　输入保证满足条件。

Output

　　Q行依次给出询问的答案。

Sample Input







Sample Output












HINT




　　0:n,Q<=100


　　1,...,5:n<=2000


　　0,...,19:n<=20000,Q<=25000


Solution


一道神奇的题目，在长沙培训时初次见面


和一般主席树的做法不尽相同


为了避免枚举中位数，我们将序列排序，对排序后的点建立一颗以整个序列编号为节点的线段树


此后，对于每个有序点的线段树，我们将其内的所有值小于它的点的贡献标记为-1，记录从左边起最大连续和，还有从右边起最大连续和


显然，这个排序后的主席树是满足二分性质的


那么，我们二分中位数，查询区间[B,C]的贡献、[A,B)的右边最大连续和、(C,D]的左边最大连续和是否大于或等于0，若是，则说明它可以构成一个合法的中位数是当前二分值的序列，也说明中位数大于或等于当前此数


最后输出二分答案即可






#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 20200

#define mid ((s) + (t) >> (1))

#define dmax(a, b) ((a) > (b) ? (a) : (b))

using namespace std;

inline int Rin(){

  int x = , c = getchar(), f = ;

  for(; c <  || c > ; c = getchar())

    if(!(c ^ ))f = -;

  for(; c >  && c < ; c = getchar())

    x = (x << ) + (x << ) + c - ;

  return x * f;

}

int n;

namespace Arcueid{

  struct Area{

    int lq, rq, sum;

    Area(int x = ){

      lq = rq = dmax(x, );

      sum = x;

    }

  };

  Area operator + (Area a, Area b){

    Area c;

    c.sum = a.sum + b.sum;

    c.lq = dmax(a.lq, a.sum + b.lq);

    c.rq = dmax(b.rq, a.rq + b.sum);

    return c;

  }

  struct Node{

    Node *l, *r;

    Area key;

    Node(){}

    Node(Node *_l, Node *_r, Area _key) : l(_l), r(_r), key(_key) {}

  }*_nil = new Node(), *nil = (*_nil = Node(_nil, _nil, ), _nil), pool[N * ], *top = pool, *rt[N];

  Node *newnode(Node *_, Node *__, Area ___){

    *top = Node(_, __, ___);

    return top++;

  }

  Node *born(int s, int t){

    if(!(s ^ t))return newnode(0x0, 0x0, Area());

    Node *_ = born(s, mid); Node *__ = born(mid + , t);

    return newnode(_, __, _->key + __->key);

  }

  Node *real(Node *p, int s, int t, int k){

    if(!(s ^ t))return newnode(0x0, 0x0, Area(-));

    if(k <= mid){

      Node *_ = real(p->l, s, mid, k);

      return newnode(_, p->r, _->key + p->r->key);

    }

    else{

      Node *_ = real(p->r, mid + , t, k);

      return newnode(p->l, _, p->l->key + _->key);

    }

  }

  Area secret(Node *p, int s, int t, int l, int r){

    if(l == s && t == r)return p->key;

    if(r <= mid)return secret(p->l, s, mid, l, r);

    if(l > mid)return secret(p->r, mid + , t, l, r);

    return secret(p->l, s, mid, l, mid) + secret(p->r, mid + , t, mid + , r);

  }

  bool judge(int A, int B, int C, int D, int k){

    int res = ;

    res += secret(rt[k], , n, B, C).sum;

    res += secret(rt[k], , n, A, B - ).rq;

    res += secret(rt[k], , n, C + , D).lq;

    return res >= ;

  }

  int binsearch(int A, int B, int C, int D){

    int s = , t = n;

    while(s +  < t){

      if(judge(A, B, C, D, mid))

        s = mid;

      else

        t = mid;

    }

    if(judge(A, B, C, D, t))

      return t;

    return s;

  }

}

namespace moon{

  struct dat{

    int key, pos;

    void init(int _) {key = Rin(); pos = _;}

    bool operator < (const dat  h)const{

      return key < h.key;

    }

  }b[N];

  void cause(){

    n = Rin();

    for(int i = ; i <= n; i++)

      b[i].init(i);

    sort(b + , b +  + n);

    Arcueid::rt[] = Arcueid::born(, n);

    for(int i = ; i <= n; i++)

      Arcueid::rt[i] = Arcueid::real(Arcueid::rt[i - ], , n, b[i - ].pos);

    int m = Rin(), ans = , q[];

    while(m--){

      for(int j=;j<;j++)

        q[j] = Rin(), q[j] = (q[j] + ans) % n+;

      sort(q,q+);

      printf("%d\n", ans = b[Arcueid::binsearch(q[],q[],q[],q[])].key);

    }

  }

}

int main(){

  moon::cause();

  return ;

}


相关文章