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

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

271451044
271451044
969056313

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 = 0, c = getchar(), f = 1;
  for(; c < 48 || c > 57; c = getchar())
    if(!(c ^ 45))f = -1;
  for(; c > 47 && c < 58; c = getchar())
    x = (x << 1) + (x << 3) + c - 48;
  return x * f;
}

int n;

namespace Arcueid{
  struct Area{
    int lq, rq, sum;

    Area(int x = 0){
      lq = rq = dmax(x, 0);
      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, 0), _nil), pool[N * 32], *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(1));
    Node *_ = born(s, mid); Node *__ = born(mid + 1, t);
    return newnode(_, __, _->key + __->key);
  }

  Node *real(Node *p, int s, int t, int k){
    if(!(s ^ t))return newnode(0x0, 0x0, Area(-1));
    if(k <= mid){
      Node *_ = real(p->l, s, mid, k);
      return newnode(_, p->r, _->key + p->r->key);
    }
    else{
      Node *_ = real(p->r, mid + 1, 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 + 1, t, l, r);
    return secret(p->l, s, mid, l, mid) + secret(p->r, mid + 1, t, mid + 1, r);
  }

  bool judge(int A, int B, int C, int D, int k){
    int res = 0;
    res += secret(rt[k], 1, n, B, C).sum;
    res += secret(rt[k], 1, n, A, B - 1).rq;
    res += secret(rt[k], 1, n, C + 1, D).lq;
    return res >= 0;
  }

  int binsearch(int A, int B, int C, int D){
    int s = 1, t = n;
    while(s + 1 < 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 = 1; i <= n; i++)
      b[i].init(i);
    sort(b + 1, b + 1 + n);
    Arcueid::rt[1] = Arcueid::born(1, n);
    for(int i = 2; i <= n; i++)
      Arcueid::rt[i] = Arcueid::real(Arcueid::rt[i - 1], 1, n, b[i - 1].pos);
    int m = Rin(), ans = 0, q[10];
    while(m--){
      for(int j=0;j<4;j++)
        q[j] = Rin(), q[j] = (q[j] + ans) % n+1;
      sort(q,q+4);
      printf("%d
", ans = b[Arcueid::binsearch(q[0],q[1],q[2],q[3])].key);
    }
  }
}

int main(){
  moon::cause();
  return 0;
}