middle-白红宇

middle

阅读量：4326 次

发布时间：2019-06-06

本文共 3709 字，大约阅读时间需要 12 分钟。

主席树大好题……这道题让主席树不仅停留在了区间第k大上，而是让它能执行像线段树一样的操作。

首先我们先说点套路的事。求中位数有一个二分法，就是每次二分答案，把大于等于当前二分的数设为1，小于的设为-1，之后我们只要看和是否大于0就能判断限制二分的值是大是小。然后虽然区间是不确定的，但是我们要求最大的中位数，只要取中间固定的一段+左区间最大后缀+右区间最大前缀判断即可。

不过这样的话每次暴力的时候，查询是\(O(nlogn)\)的，再套上查询次数会超时。如何优化一下呢？如果我们用线段树对于每一个二分的值，都维护一下它当前的值和最大前后缀，这样的话我们就只需要\(O(log^2n)\)的复杂度来完成一次查询。但是这样会\(MLE\)。

然后在每两棵树之间，其实只有\(i-1\)发生了变化，从1变成了-1.这样的话我们就可以把这些线段树建成主席树，用主席树来实现线段树一样的操作就好了。注意这道题是把以当前这个数的值为根，以位置为值域，注意访问区间不要开小（我就因为这个大数据\(MLE\)），最开始建树的地方比较重要，我们需要开一个\(vector\)来把数的值一样，多次出现的数的位置都存起来，然后按照值的大小按顺序修改即可。

看一下代码。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #define rep(i,a,n) for(int i = a;i <= n;i++)#define per(i,n,a) for(int i = n;i >= a;i--)#define enter putchar('\n')#define fr friend inline#define y1 poj#define mp make_pair#define pr pair
             
              #define fi first#define sc second#define pb push_back#define I puts("Oops")using namespace std;typedef long long ll;const int M = 20005;const int N = 1000005;const int INF = 1000000009;const double eps = 1e-7;int read(){ int ans = 0,op = 1;char ch = getchar(); while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();} while(ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar(); return ans * op;}struct node{ int ls,rs,v,lv,rv;}t[N<<2];int n,Q,a[M],b[M],root[M],q[6],x,y,z,e,tot,la,L,R,g,idx;vector 
              
                V[M];void update(int p){ t[p].v = t[t[p].ls].v + t[t[p].rs].v; t[p].lv = max(t[t[p].ls].lv,t[t[p].ls].v + t[t[p].rs].lv); t[p].rv = max(t[t[p].rs].rv,t[t[p].rs].v + t[t[p].ls].rv);}void build(int &p,int l,int r){ if(!p) p = ++idx; if(l == r) {t[p].v = t[p].lv = t[p].rv = 1;return;} int mid = (l+r) >> 1; build(t[p].ls,l,mid),build(t[p].rs,mid+1,r); update(p);}void modify(int old,int &p,int l,int r,int val){ p = ++idx; t[p] = t[old]; if(l == r) {t[p].v = t[p].lv = t[p].rv = -1;return;} int mid = (l+r) >> 1; if(val <= mid) modify(t[old].ls,t[p].ls,l,mid,val); else modify(t[old].rs,t[p].rs,mid+1,r,val); update(p);}int query(int p,int l,int r,int kl,int kr){ //I; if(kr < kl) return 0; if(l == kl && r == kr) return t[p].v; int mid = (l+r) >> 1; if(kr <= mid) return query(t[p].ls,l,mid,kl,kr); else if(kl > mid) return query(t[p].rs,mid+1,r,kl,kr); else return query(t[p].ls,l,mid,kl,mid) + query(t[p].rs,mid+1,r,mid+1,kr);}int ask(int p,int l,int r,int kl,int kr,bool flag)//1 left , 0 right{ //I; //printf("#%d %d %d %d\n",l,r,kl,kr); if(l == kl && r == kr) return flag ? t[p].lv : t[p].rv; int mid = (l+r) >> 1; if(kr <= mid) return ask(t[p].ls,l,mid,kl,kr,flag); else if(kl > mid) return ask(t[p].rs,mid+1,r,kl,kr,flag); else { int cur1 = 0,cur2 = 0; cur1 = flag ? ask(t[p].ls,l,mid,kl,mid,flag) : ask(t[p].rs,mid+1,r,mid+1,kr,flag); if(flag) cur2 = query(t[p].ls,l,mid,kl,mid) + ask(t[p].rs,mid+1,r,mid+1,kr,flag); else cur2 = query(t[p].rs,mid+1,r,mid+1,kr) + ask(t[p].ls,l,mid,kl,mid,flag); return max(cur1,cur2); }}bool judge(int x){ int cur1 = query(root[x],1,n,q[2]+1,q[3]-1); int cur2 = ask(root[x],1,n,q[1],q[2],0); int cur3 = ask(root[x],1,n,q[3],q[4],1); return cur1 + cur2 + cur3 >= 0;}int main(){ n = read(),build(root[0],1,n); rep(i,1,n) a[i] = b[i] = read(); sort(b+1,b+1+n),tot = unique(b+1,b+1+n) - b - 1; rep(i,1,n) a[i] = lower_bound(b+1,b+1+tot,a[i]) - b,V[a[i]].pb(i); rep(i,1,tot) { root[i] = root[i-1]; rep(j,0,(int)V[i-1].size()-1) modify(root[i],root[i],1,n,V[i-1][j]); } Q = read(); rep(i,1,Q) { rep(j,1,4) q[j] = read(),q[j] = (q[j] + la) % n + 1; sort(q+1,q+5),L = 1,R = tot; while(L < R) { int mid = (L+R+1) >> 1; if(judge(mid)) L = mid; else R = mid - 1; } la = b[L]; printf("%d\n",la); } return 0;}

转载于:https://www.cnblogs.com/captain1/p/10102867.html

你可能感兴趣的文章