P8264 [Ynoi Easy Round 2020] TEST_100 题解

zhy12138 · 2022-07-22 09:10:24 · 题解

怎么题解没一个正解啊（全恼）

首先我们不难发现我们实际要维护的是一个绝对值的复合函数

直接维护的话段数是 2^n 级别的，所以考虑用一些特殊的数据结构维护

考虑从后往前依次加入函数，假设目前已经维护了后 n 个的复合函数，现在正在加入倒数第 n+1 个函数 f(x)=|x-v|

那么不难发现当 x 在 0\sim v 中，f(x) 是 v\sim 0

当 x 在 v+1 \sim 10^7 中，f(x) 是 1 \sim 10^7-v

因为我们已经维护好了后 n 个的复合函数，那么我们只需要拿出这个复合函数的 0 \sim v,1 \sim 10^7-v 两段，然后将前一段反转再拼接即可

不难发现这个操作可以用可持久化平衡树维护

然后因为需要支持区间查询，所以我们需要实现的是线段树套平衡树

这样查询时只需要在 O(\log n) 个节点中花费 O(\log V) 的复杂度找到对应的段，然后求值即可，复杂度 O(m\log n\log V)

而初始化时一共会进行 O(n\log n) 次在前面加函数的操作，每次操作的复杂度是 O(\log V)

因此总复杂度为 O((n+m)\log n\log V)

但是我的实现空间常数很大（也可能是我写的可持久化 fhq_treap 复杂度有问题）

因此还要加两个小优化

第一个是线段树顶层不要二分，而是分为 O(\log n) 个块

这样这一层最多在单次查询中多贡献 O(\log n) 次节点查询，不改变复杂度

但是这一部分加入函数的次数就由 O(n\log \log n) 变为 O(n) 了

第二个是线段树底层不要到区间长度为 1 再停，而是到 O(\log n\log V) 就停，查询的时候就暴力扫过去

因为底层只会有 O(1) 个节点被查询，因此复杂度不变，且显然少加了很多次函数

代码实现比较傻，仅供参考

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<vector>
#include<random>
#define ll long long
using namespace std;
const int MAXN=1e5+10;
const int inf=1e5;
int read()
{
    int kkk=0,x=1;
    char c=getchar();
    while((c<'0' || c>'9') && c!='-') c=getchar();
    if(c=='-') c=getchar(),x=-1;
    while(c>='0' && c<='9') kkk=kkk*10+(c-'0'),c=getchar();
    return kkk*x;
}
int n,m,a[MAXN],ans;
mt19937 gen(time(NULL));
int root[MAXN*2],rcnt,pcnt;
vector<int> son[MAXN*2];
struct fhq_treap
{
    int ly,ry;
    int size;
    int slen;
    int l,r;
    bool tag;
}tree[MAXN*600];
#define ls(x) (tree[x].l)
#define rs(x) (tree[x].r)
void up(int x)
{
    tree[x].size=tree[ls(x)].size+tree[rs(x)].size+1;
    tree[x].slen=tree[ls(x)].slen+tree[rs(x)].slen+abs(tree[x].ly-tree[x].ry)+1;
}
int copy(int x)
{
    int bck=++pcnt;
    tree[bck]=tree[x];
    return bck;
}
int check(int x,int y)
{
    uniform_int_distribution<int> dcd(1,tree[x].size+tree[y].size);
    return dcd(gen)<=tree[x].size;
}
int calc(int o,int len)
{
    if(len==1) return tree[o].ly;
    else return tree[o].ly+(len-1)*(tree[o].ly>tree[o].ry?-1:1);
}
int NEW(int ly,int ry)
{
    int bck=++pcnt;
    tree[bck].ly=ly;
    tree[bck].ry=ry;
    tree[bck].slen=abs(ly-ry)+1;
    tree[bck].size=1;
    return bck;
}
void turn(int x)
{
    tree[x].tag^=1;
    swap(ls(x),rs(x));
    swap(tree[x].ly,tree[x].ry);
}
void down(int x)
{
    if(!tree[x].tag) return;
    if(ls(x)) tree[x].l=copy(ls(x)),turn(ls(x));
    if(rs(x)) tree[x].r=copy(rs(x)),turn(rs(x));
    tree[x].tag=0;
}
int merge(int x,int y)
{
    if(!x || !y) return x+y;
    int bck;
    if(check(x,y))
    {
        bck=copy(x); down(bck);
        tree[bck].r=merge(rs(bck),y);
    }
    else
    {
        bck=copy(y); down(bck);
        tree[bck].l=merge(x,ls(bck));
    }
    up(bck);
    return bck;
}
void split_len(int x,int len,int &lx,int &rx)
{
    if(!x) {lx=rx=0;return;}
    if(tree[ls(x)].slen+abs(tree[x].ly-tree[x].ry)+1<=len)
    {
        lx=copy(x); down(lx);
        split_len(rs(lx),len-tree[ls(x)].slen-(abs(tree[x].ly-tree[x].ry)+1),rs(lx),rx);
        up(lx);
    }
    else
    {
        rx=copy(x); down(rx);
        split_len(ls(rx),len,lx,ls(rx));
        up(rx);
    }
}
void split_size(int x,int size,int &lx,int &rx)
{
    if(!x) {lx=rx=0;return;}
    if(tree[ls(x)].size+1<=size)
    {
        lx=copy(x); down(lx);
        split_size(rs(lx),size-tree[ls(x)].size-1,rs(lx),rx);
        up(lx);
    }
    else
    {
        rx=copy(x); down(rx);
        split_size(ls(rx),size,lx,ls(rx));
        up(rx);
    }
}
int find(int &x,int &len,int &S)
{
    if(tree[x].tag) x=copy(x),down(x);
    if(tree[ls(x)].slen>=len) return find(ls(x),len,S);
    else
    {
        S+=tree[ls(x)].size;
        len-=tree[ls(x)].slen;
        if(abs(tree[x].ly-tree[x].ry)+1>=len) return x;
        else
        {
            ++S;
            len-=abs(tree[x].ly-tree[x].ry)+1;
            return find(rs(x),len,S);
        }
    }
}
void get_split_len(int &x,int len,int &lx,int &rx)
{
    int tmp=len,S=1;
    int o=find(x,tmp,S);
    if(abs(tree[o].ly-tree[o].ry)+1!=tmp)
    {
        int A,B,C,F;
        split_size(x,S,F,C);
        split_size(F,S-1,A,B);
        int D=NEW(tree[o].ly,calc(o,tmp));
        int E=NEW(calc(o,tmp+1),tree[o].ry);
        lx=merge(A,D);
        rx=merge(E,C);
    }
    else split_len(x,len,lx,rx);
}
void init(int l,int r,int x)
{
    for(int i=r;i>=l;--i)
    {
        int A,B,C,D;
        get_split_len(root[x],a[i]+1,A,B);
        get_split_len(root[x],inf-a[i]+1,C,B);
        get_split_len(C,1,B,D);
        turn(A);
        root[x]=merge(A,D);
    }
}
const int base=2000;
void build(int l,int r,int &x)
{
    x=++rcnt;
    if(r-l<=1000) return;
    if(x==1)
    {
        int N=(n-1)/base+1;
        son[x].resize(N);
        for(int i=1;i<=N;++i)
        {
            build((i-1)*base+1,min(n,i*base),son[x][i-1]);
        }
        root[x]=NEW(0,inf);
        init(l,r,x);
        return;
    }
    int mid=(l+r)>>1;
    son[x].resize(2);
    build(l,mid,son[x][0]);
    build(mid+1,r,son[x][1]);
    if(root[son[x][1]])
    {
        root[x]=copy(root[son[x][1]]);
        init(l,mid,x);
    }
    else
    {
        root[x]=NEW(0,inf);
        init(l,r,x);
    }
}
int cx(int l,int r,int L,int R,int v,int x)
{
    if(r-l<=1000)
    {
        for(int i=max(L,l);i<=min(R,r);++i) v=abs(v-a[i]);
        return v;
    }
    if(L<=l && r<=R)
    {
        ++v;
        int S=0;
        int o=find(root[x],v,S);
        return calc(o,v);
    }
    if(x==1)
    {
        int N=(n-1)/base+1;
        int bck=v;
        for(int i=1;i<=N;++i)
        {
            if(max((i-1)*base+1,L)<=min(min(n,i*base),R)) bck=cx((i-1)*base+1,min(n,i*base),L,R,bck,son[x][i-1]);
        }
        return bck;
    }
    int mid=(l+r)>>1;
    if(R<=mid) return cx(l,mid,L,R,v,son[x][0]);
    if(mid<L) return cx(mid+1,r,L,R,v,son[x][1]);
    return cx(mid+1,r,L,R,cx(l,mid,L,R,v,son[x][0]),son[x][1]);
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;++i) a[i]=read();
    int R;
    build(1,n,R);
    while(m--)
    {
        int l=read()^ans,r=read()^ans,v=read()^ans;
        printf("%d\n",ans=cx(1,n,l,r,v,R));
    }
    return 0;
}
//tetu no isi to hagane no tuyosa