题解 P6829 【[IOI2020]Comparing Plants】

· · 题解

安利：IOI2020题解-洛谷博客 IOI2020题解-cnblogs

题目链接-LOJ 题目链接-洛谷

首先我们考虑构造出一个符合题意的数列。

每次选择一个 前面 k-1 个位置上都是 0 或者已经选过，并且当前位置为 0 的位置，然后把它的值置为这个序列的最大值。不难发现这样做一定能构造出一个符合要求的排列。

这个构造的过程可以用线段树+set优化到 \Theta(n\log n)

不难发现，一个排列符合条件相当于它的每连续 k 位的相对大小关系和我们构造出来的排列相同。

那么，不难证明在 2k>n 的时候只有唯一的一个排列，所以不判 0 直接比较可以获得子任务 2/3/4 的分数。

现在排列不唯一怎么办？

考虑对于每个点，求出它往左/右 k 个位置中，比他小的最大的数字的位置，分别记为 pre_i 和 nxt_i ，然后对 pre/nxt 做一个倍增。

对于每组询问，假定我们构造的排列 A 满足 A_x>A_y 。

我们从 x 开始，通过 nxt 和 pre 往左右跳，保证跳的时候仍然满足当前位置的值 >A_y . 如果跳到的区间包含了 y ，那么就输出 1 ，否则不能确定，输出 0 .

$\Theta((n+q)\log n)

code(LOJ上通过) : 

#include "plants.h"
#define LL long long
#include <bits/stdc++.h>
using namespace std; 
const int N = 200005; 
int n,k,R[N];
struct Tree2{
    #define lc o<<1
    #define rc o<<1|1
    int now[N],node[N],mxi[N<<2];
    inline int Mx(int x,int y){ return now[x] > now[y] ? x : y; }
    inline void up(int o){ mxi[o] = Mx(mxi[lc],mxi[rc]); }
    inline void Build(int o,int l,int r){
        if (l == r){ node[l] = o,mxi[o] = l; return; }
        int mid = l+r>>1; Build(lc,l,mid),Build(rc,mid+1,r),up(o);
    }
    inline void init(){ memset(now,0,n+1<<2),Build(1,1,n); }
    inline void modif(int x,int v){ if (x < 1 || x > n) return; static int o; mxi[node[x]] = x; o = node[x] >> 1,now[x] = v; while (o) up(o),o>>=1; }
    inline int get(){ static int ret; return (now[ret = mxi[1]] >= k) ? (modif(ret,0),ret) : 0; }

    int ll,rr,qans;
    inline void init2(){ memset(now,0,n+1<<2),memset(mxi,0,n*4+1<<2); now[0] = -1; }
    inline void Ask(int o,int l,int r){
        if (ll <= l && rr >= r){ qans = Mx(qans,mxi[o]); return; }
        int mid = l+r>>1; if (ll <= mid) Ask(lc,l,mid); if (rr > mid) Ask(rc,mid+1,r);
    }
    inline int query(int l,int r){ qans = 0,ll = max(1,l),rr = min(n,r); if (ll <= rr) Ask(1,1,n); return qans; }
    #undef lc
    #undef rc
}T2;
set<int>S; bool in[N];
typedef set<int>::iterator IT;
inline void recalc(int x){
    static IT it;
    if (in[x]){
        it = S.find(x);
        if (it == S.begin()){ it = S.end(),--it; if (*it == x) T2.modif(x,n); else T2.modif(x,x+n-*it); }
        else --it,T2.modif(x,x-*it);
    }
    else T2.modif(x,0);
}
inline void Ins(int x){
    static IT it; in[x] = 1;
    it = S.insert(x).first,++it; if (it == S.end()) it = S.begin();
    recalc(x),recalc(*it);
}
inline void Del(int x){
    static IT it; static int v; in[x] = 0;
    it = S.find(x),++it; if (it == S.end()) it = S.begin(); v = *it;
    S.erase(S.find(x)); recalc(v),recalc(x);
}
struct Tree1{
    #define lc o<<1
    #define rc o<<1|1
    int tag[N<<2],mn[N<<2];
    inline void up(int o){ mn[o] = min(mn[lc],mn[rc]); }
    inline void Tag(int o,int v){ mn[o] += v,tag[o] += v; }
    inline void down(int o){ if (tag[o]) Tag(lc,tag[o]),Tag(rc,tag[o]),tag[o] = 0; }
    inline void Build(int o,int l,int r){
        if (l == r){ mn[o] = R[l]; return; }
        int mid = l+r>>1; Build(lc,l,mid),Build(rc,mid+1,r),up(o);
    }
    int ll,rr;
    inline void Add(int o,int l,int r){
        if (ll <= l && rr >= r){ Tag(o,-1); return; }
        down(o); int mid = l+r>>1; if (ll <= mid) Add(lc,l,mid); if (rr > mid) Add(rc,mid+1,r); up(o); 
    }
    inline void Maintain(int o,int l,int r){
        if (mn[o] > 0) return; if (l == r){ mn[o] = 19260817,Ins(l); return; }
        down(o); int mid = l+r>>1; Maintain(lc,l,mid),Maintain(rc,mid+1,r),up(o);
    }
    inline void init(){ Build(1,1,n); }
    inline void maintain(){ Maintain(1,1,n); }
    inline void add(int l,int r){ ll = l,rr = r; if (ll <= rr) Add(1,1,n); }
    #undef lc
    #undef rc
}T1;
int a[N],b[N],La[N][20],Ne[N][20],Ld[N][20],Nd[N][20],L;
inline void MAIN(){
    T2.init(),T1.init(),T1.maintain();
    int i,j,x,p,now = n;
    while (now){
        x = T2.get(); a[x] = now; --now; Del(x);
        if (x >= k) T1.add(x-k+1,x); else T1.add(1,x),T1.add(n-(k-x)+1,n);
        T1.maintain();
    }
    for (i = 1; i <= n; ++i) b[a[i]] = i;
    T2.init2();
    for (i = 1; i <= n; ++i){
        p = b[i];
        La[p][0] = T2.query(p-k+1,p-1); if (La[p][0]) Ld[p][0] = p - La[p][0];
        Ne[p][0] = T2.query(p+1,p+k-1); if (Ne[p][0]) Nd[p][0] = Ne[p][0] - p;
        if (p-k+1 < 1){
            x = T2.query(p-k+1+n,n);
            if (a[x] > a[La[p][0]]) La[p][0] = x,Ld[p][0] = p + n - x;
        }
        if (p+k-1 > n){
            x = T2.query(1,p+k-1-n);
            if (a[x] > a[Ne[p][0]]) Ne[p][0] = x,Nd[p][0] = x + n - p;
        }
        T2.modif(p,i);
    }
    L = 1;
    while ((1<<L) < n) ++L; 
    for (j = 1; j <= L; ++j)
    for (i = 1; i <= n; ++i){
        if (p = La[i][j-1]){
            La[i][j] = La[p][j-1];
            Ld[i][j] = min(n,Ld[i][j-1] + Ld[p][j-1]);
        }
        if (p = Ne[i][j-1]){
            Ne[i][j] = Ne[p][j-1];
            Nd[i][j] = min(n,Nd[i][j-1] + Nd[p][j-1]);
        }
    }
}

void init(int K,vector<int> R){
    k = K,n = R.size();
    for (int i = 1; i <= n; ++i) ::R[i] = R[i-1];
    MAIN();
}
inline bool checkbig(int x,int y){
    int i,xx = x,di = y-x,s;
    for (s = 0,i = L; i >= 0; --i) if (a[Ne[x][i]] >= a[y]) s += Nd[x][i],x = Ne[x][i];
    if (s >= di) return 1;
    for (s = 0,x = xx,i = L; i >= 0; --i) if (a[La[x][i]] >= a[y]) s += Ld[x][i],x = La[x][i];
    if (s >= n-di) return 1;
    return 0;
}
inline bool checksmall(int x,int y){
    int i,yy = y,di = y-x,s;
    for (s = 0,i = L; i >= 0; --i) if (a[La[y][i]] >= a[x]) s += Ld[y][i],y = La[y][i];
    if (s >= di) return 1;
    for (y = yy,s = 0,i = L; i >= 0; --i) if (a[Ne[y][i]] >= a[x]) s += Nd[y][i],y = Ne[y][i];
    if (s >= n-di) return 1;
    return 0;
}
int compare_plants(int x,int y){
    ++x,++y;
    if (a[x] > a[y]) return checkbig(x,y) ? 1 : 0;
    return checksmall(x,y) ? -1 : 0;
}