bzoj3489:A simple rmq problem(KDT/可持久化树套树)

题解

  mdzz这个破题写KDT无修我还打了半天插入+替罪羊树重构结果T成苟调了一万年才发现可以直接建树。

做法1

  这题显然先一眼套路,如果某个位置ii的数字在区间[l,r][l,r]只出现一次,那么满足lir, prei<l, r<nxtil\leq i\leq r,\ pre_i<l,\ r<nxt_ipreprenxtnxt为上一个这种数字出现的位置。
  因为最值是不满足可减性的信息,所以如果询问的某种限制为区间那么处理这种限制必定要上一层数据结构,但是对于某种限制若是前缀或者后缀询问,我们可以按这个限制排个序,按顺序处理来少掉一层数据结构。
  那么这题可以按prepre或者nxtnxt排一个序,然后两层可持久化线段树套上去,一层nxtnxt一层ii,其实这两层顺序无所谓,维护一下最值即可。
  注意线段树深度是log2n+1\left \lceil log_2n\right \rceil+1,内层线段树空间要开n×n\times深度2^2

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
#define lt1 tr1[x].ls
#define rt1 tr1[x].rs
#define lt2 tr2[x].ls
#define rt2 tr2[x].rs
using namespace std;
const int maxn=100010, inf=1e9;
struct sgt{int ls, rs, w;}tr1[maxn*18], tr2[maxn*324];
struct poi{int w, pos, pre, nxt;}q[maxn];
int n, m, L, R, tott1, tott2, ans, x, y;
int last[maxn], root[maxn*18];
  
template<typename T>
inline void read(T &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;   
}
  
bool operator < (poi a, poi b){return a.pre<b.pre;}
  
int query2(int x, int l, int r)
{
    if(L<=l && r<=R) return tr2[x].w;
    int mid=(l+r)>>1, ans=0;
    if(L<=mid) ans=query2(lt2, l, mid);
    if(R>mid) ans=max(ans, query2(rt2, mid+1, r));
    return ans;
}
  
int query1(int x, int l, int r)
{
    if(R+1<=l) return query2(tr1[x].w, 1, n);
    int mid=(l+r)>>1, ans=0;
    if(R+1<=mid) return max(query1(lt1, l, mid), query2(tr1[rt1].w, 1, n));
    else return ans=query1(rt1, mid+1, r);
}
  
void update2(int &x, int l, int r, int cx)
{
    tr2[++tott2]=tr2[x]; x=tott2;
    tr2[x].w=max(tr2[x].w, q[cx].w);
    if(l==r) return;
    int mid=(l+r)>>1;
    if(q[cx].pos<=mid) update2(lt2, l, mid, cx);
    else update2(rt2, mid+1, r, cx);
}
  
void update1(int &x, int l, int r, int cx)
{
    tr1[++tott1]=tr1[x]; x=tott1;
    update2(tr1[x].w, 1, n, cx);
    if(l==r) return;
    int mid=(l+r)>>1;
    if(q[cx].nxt<=mid) update1(lt1, l, mid, cx);
    else update1(rt1, mid+1, r, cx);
}
   
int main()
{
    read(n); read(m);
    for(int i=1;i<=n;i++) read(q[i].w), q[i].pos=i;
    for(int i=1;i<=n;i++) q[i].pre=last[q[i].w], last[q[i].w]=i;
    for(int i=1;i<=n;i++) last[i]=n+1;
    for(int i=n;i;i--) q[i].nxt=last[q[i].w], last[q[i].w]=i;
    sort(q+1, q+1+n);
    for(int i=1;i<=n;i++)
    {
        root[i]=root[i-1];
        update1(root[i], 1, n+1, i);
    }
    for(int i=1;i<=m;i++)
    {
        read(x); read(y);
        L=min((x+ans)%n+1, (y+ans)%n+1);
        R=max((x+ans)%n+1, (y+ans)%n+1);
        int l=1, r=n;
        while(l<r)
        {
            int mid=(l+r+1)>>1;
            if(q[mid].pre<L) l=mid;
            else r=mid-1;
        }
        printf("%d\n", ans=query1(root[l], 1, n+1));
    }
}

做法2

  还是用套路,可以把i,pre,nxti,pre,nxt看成三维坐标,KDT就完事了。
  因为是求最值,所以可以估一下价,一个是最大值比当前答案都小就不跑,第二个是先跑最大值大的子树。

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
#define lt tr[x].ls
#define rt tr[x].rs
#define maxs(a, b) a=(a>b?a:b)
#define mins(a, b) a=(a<b?a:b)
using namespace std;
const int maxn=500010, inf=1e9;
const double A=0.8;
struct kdt{int d[3], l[3], r[3], w, mx, size, ls, rs;}tr[maxn];
struct poi{int d[3], w;}P, np[maxn];
struct que{int l, r;}q;
int n, m, tott, now, dep, cmpd, cnt, root, x, y, ans;
int a[maxn], last[maxn], pre[maxn], nxt[maxn];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
}

inline void newnode(int x)
{
	tr[x].w=tr[x].mx=P.w; tr[x].size=1;
	for(int i=0;i<3;i++)
	tr[x].d[i]=tr[x].l[i]=tr[x].r[i]=P.d[i];
}

inline void up(int x)
{
	tr[x].mx=max(tr[x].w, max(tr[lt].mx, tr[rt].mx));
	tr[x].size=tr[lt].size+tr[rt].size+1;
	for(int i=0;i<3;i++)
	{
		if(lt) mins(tr[x].l[i], tr[lt].l[i]), maxs(tr[x].r[i], tr[lt].r[i]);
		if(rt) mins(tr[x].l[i], tr[rt].l[i]), maxs(tr[x].r[i], tr[rt].r[i]);
	}
}

bool operator < (poi a, poi b){return a.d[cmpd]<b.d[cmpd];}

void build(int &x, int l, int r, int ty)
{
	x=++tott; int mid=(l+r)>>1; cmpd=ty;
	nth_element(np+l, np+mid, np+r+1);
	P=np[mid]; newnode(x);
	if(l<mid) build(lt, l, mid-1, (ty==2)?0:(ty+1));
	if(r>mid) build(rt, mid+1, r, (ty==2)?0:(ty+1));
	up(x);
}

inline bool cross(int x)
{
	if(!x) return 0;
	if(q.l>tr[x].r[0]) return 0;
	if(q.r<tr[x].l[0]) return 0;
	if(q.l<=tr[x].l[1]) return 0;
	if(q.r>=tr[x].r[2]) return 0;
	return 1;
}

void query(int x)
{
	if(q.l<=tr[x].l[0] && tr[x].r[0]<=q.r && tr[x].r[1]<q.l && tr[x].l[2]>q.r) ans=max(ans, tr[x].mx);
	if(q.l<=tr[x].d[0] && tr[x].d[0]<=q.r && tr[x].d[1]<q.l && tr[x].d[2]>q.r) ans=max(ans, tr[x].w);
	if(tr[lt].mx>tr[rt].mx)
	{
		if(tr[lt].mx>ans && cross(lt)) query(lt);
		if(tr[rt].mx>ans && cross(rt)) query(rt);	
	}
	else
	{
		if(tr[rt].mx>ans && cross(rt)) query(rt);
		if(tr[lt].mx>ans && cross(lt)) query(lt);
	}
}

int main()
{
	read(n); read(m);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i++) pre[i]=last[a[i]], last[a[i]]=i;
	for(int i=1;i<=n;i++) last[i]=n+1;
	for(int i=n;i;i--) nxt[i]=last[a[i]], last[a[i]]=i;
	for(int i=1;i<=n;i++) np[i].w=a[i], np[i].d[0]=i, np[i].d[1]=pre[i], np[i].d[2]=nxt[i];
	build(root, 1, n, 0);
	for(int i=1;i<=m;i++)
	{
		read(x); read(y);
		q.l=min((x+ans)%n+1, (y+ans)%n+1);
		q.r=max((x+ans)%n+1, (y+ans)%n+1);
		ans=0; query(root); printf("%d\n", ans);
	}
}