Skip to content

Latest commit

 

History

History
915 lines (864 loc) · 20.9 KB

数据结构.md

File metadata and controls

915 lines (864 loc) · 20.9 KB

数据结构

Hash

矩阵 Hash

原矩阵 $s$ 中查找目标矩阵 $a$ 的出现次数

#define ULL unsigned long long
const ULL Base1=2007;
const ULL Base2=2009;
int test,n,m,x,y;
char s[2005][2005],a[2005][2005];
ULL ans,temp[2005][2005],Temp[2005][2005];

ULL Gethash()
{
    ULL c,sum=0;
    for(int i=0;i<x;i++)
    {
        c=0;
        for(int j=0;j<y;j++)
            c=c*Base1+a[i][j];
        sum=sum*Base2+c;
    }
    return sum;
}

void init()
{
    ULL t=1,c;
    for(int i=0;i<y;i++) t*=Base1;
    for(int i=0;i<n;i++)
    {
        c=0;
        for(int j=0;j<y;j++)
            c=c*Base1+s[i][j];
        temp[i][y-1]=c;
        for(int j=y;j<m;j++)
            temp[i][j]=temp[i][j-1]*Base1-s[i][j-y]*t+s[i][j];
    }
}

int GetAns(ULL Hash)
{
    ULL t=1,c;
    int ans=0;
    for(int i=0;i<x;i++) t*=Base2;
    for(int i=y-1;i<m;i++)
    {
        c=0;
        for(int j=0;j<x;j++) c=c*Base2+temp[j][i];
        Temp[x-1][i]=c;
        if(c==Hash) ans++;
        for(int j=x;j<n;j++)
        {
            Temp[j][i]=Temp[j-1][i]*Base2-temp[j-x][i]*t+temp[j][i];
            if(Temp[j][i]==Hash) ans++;
        }
    }
    return ans;
}

int main()
{
    scanf("%d%d%d%d",&x,&y,&n,&m);
    for(int i=0;i<x;i++)
        scanf("%s",a[i]);
    for(int i=0;i<n;i++)
        scanf("%s",s[i]);
    ULL Hash=Gethash();
    init();
    ans=GetAns(Hash);
    printf("%d\n",ans);
    return 0;
}

线段树

李超树

插入 $O(log^2_2n)$ ，查询 $O(log_2 n)$，注意查询返回的是第几条线段

struct Seg{
    double k,b;
    Seg(){}
    Seg(LL X0,LL Y0,LL X1,LL Y1)
    {
        if(X0==X1) k=0,b=max(Y0,Y1);
        else k=1.0*(Y0-Y1)/(X0-X1),b=-k*X0+Y0;
    }
    double gety(int x){return k*x+b;}
};
const double eps=1e-8;
struct LCST
{
    Seg s[4*N];
    int m,op,cnt,X0,Y0,X1,Y1;
    LL ans,v[4*N];
    inline int sig(double x){return fabs(x)<eps?0:(x>0?1:-1);}
    void ins(int x,int a,int b,int c,int d,int p)
    {
        if(c<=a&&b<=d)
        {
            if(sig(s[p].gety(a)-s[v[x]].gety(a))>0 &&sig(s[p].gety(b)-s[v[x]].gety(b))>0){v[x]=p;return;}
            if(sig(s[p].gety(a)-s[v[x]].gety(a))<=0 &&sig(s[p].gety(b)-s[v[x]].gety(b))<=0)return;
            if(a==b)return;
        }
        int mid=(a+b)>>1;
        if(c<=mid)ins(x<<1,a,mid,c,d,p);
        if(d>mid)ins(x<<1|1,mid+1,b,c,d,p);
    }
    void ask(int x,int a,int b,int c)
    {
        if(sig(s[ans].gety(c)-s[v[x]].gety(c))<0)ans=v[x];
        else if(!sig(s[ans].gety(c)-s[v[x]].gety(c))&&ans>v[x])ans=v[x];
        if(a==b)return;
        int mid=(a+b)>>1;
        c<=mid?ask(x<<1,a,mid,c):ask(x<<1|1,mid+1,b,c);
    }
}tree;
int main()
{
    tree.s[0].b=-1;
    tree.s[++tree.cnt]=Seg(X0,Y0,X1,Y1);//insert
    tree.ins(1,1,N,X0,X1,tree.cnt);
    tree.ans=0;
    tree.ask(1,1,N,i);
}

两延迟标记

change0区间置0，change1区间加1，query询问区间和

struct Data
{
    int tag,tag0,sum;
}tree[40100];

void build(int l,int r,int x)
{
    tree[x].tag=-1;tree[x].sum=0;tree[x].tag0=0;
    if (l==r) return ;
    int mid=l+r>>1;
    build(l,mid,x<<1);build(mid+1,r,x<<1|1);
}

void Pushdown(int x,int l,int r)
{
    if (tree[x].tag==-1) return ;
    int mid=l+r>>1;
    if (tree[x].tag0==1)
    {
        tree[x<<1].tag0=1;
        tree[x<<1|1].tag0=1;
        tree[x<<1].tag=tree[x].tag;
        tree[x<<1|1].tag=tree[x].tag;
        tree[x<<1].sum=tree[x].tag*(mid-l+1);
        tree[x<<1|1].sum=tree[x].tag*(r-mid);
        tree[x].tag=-1;tree[x].tag0=0;
    }
    else
    {
        if (tree[x<<1].tag==-1) tree[x<<1].tag=tree[x].tag;
        else tree[x<<1].tag+=tree[x].tag;
        if (tree[x<<1|1].tag==-1) tree[x<<1|1].tag=tree[x].tag;
        else tree[x<<1|1].tag+=tree[x].tag;
        tree[x<<1].sum+=tree[x].tag*(mid-l+1);
        tree[x<<1|1].sum+=tree[x].tag*(r-mid);
        tree[x].tag=-1;
    }
}

void change0(int lq,int rq,int l,int r,int x)
{
    if (lq<=l&&rq>=r)
    {
        tree[x].tag=0;tree[x].sum=0;tree[x].tag0=1;
        return ;
    }
    Pushdown(x,l,r);
    int mid=l+r>>1;
    if (lq<=mid) change0(lq,rq,l,mid,x<<1);
    if (rq>mid) change0(lq,rq,mid+1,r,x<<1|1);
    tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
}

void change1(int lq,int rq,int l,int r,int x)
{
    if (lq<=l&&rq>=r)
    {
        if (tree[x].tag==-1) tree[x].tag=1;else tree[x].tag++;
        tree[x].sum+=r-l+1;
        return ;
    }
    Pushdown(x,l,r);
    int mid=l+r>>1;
    if (lq<=mid) change1(lq,rq,l,mid,x<<1);
    if (rq>mid) change1(lq,rq,mid+1,r,x<<1|1);
    tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
}

int query(int lq,int rq,int l,int r,int x)
{
    if (lq<=l&&rq>=r) return tree[x].sum;
    Pushdown(x,l,r);
    int mid=l+r>>1,ans=0;
    if (lq<=mid) ans+=query(lq,rq,l,mid,x<<1);
    if (rq>mid) ans+=query(lq,rq,mid+1,r,x<<1|1);
    tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
    return ans;
}

树状数组

区间加区间和

struct bit
{
    int c[maxn],cc[maxn];
    void add(int x,int v)
    {
        for (int i=x;i<=n;i+=i&-i)
            c[i]+=v,cc[i]+=x*v;
    }
    void add(int l,int r,int v){add(l,v);add(r+1,-v);}
    int sum(int x)
    {
        int ret=0;
        for (int i=x;i;i-=i&-i)
            ret+=(x+1)*c[i]-cc[i];
        return ret;
    }
    int sum(int l,int r){return sum(r)-sum(l-1);}
}

三维树状数组

struct bit
{
    int c[100010];
    inline int lowbit(int x){return x&-x;}
    void update(int x,int y,int z,int d){
        for (int i=x;i<=n;i+=lowbit(i))
            for (int j=y;j<=m;j+=lowbit(j))
                for (int k=z;k<=h;k+=lowbit(k))
                    c[id(i,j,k)]=max(c[id(i,j,k)],d);
    }
    int query(int x,int y,int z){
        int res=-inf;
        for (int i=x;i;i-=lowbit(i))
            for (int j=y;j;j-=lowbit(j))
                for (int k=z;k;k-=lowbit(k))
                    res=max(res,c[id(i,j,k)]);
        return res;
    }
}

主席书

区间 K 大数

struct ptree{
    int T,n,m,s,k,h[100010],b[100010],d[100010];
    struct ST
    {
        int lc,rc,sum;
    }a[2000010];
    int Hash(int x)  
    {  
        return lower_bound(b+1,b+1+k,x)-b;
    }  
    void build(int l,int r,int x)
    {
        s++;x=s;
        if (l==r) {a[x].lc=a[x].rc=0;return ;}
        int mid=(l+r)>>1;
        a[x].lc=s+1;build(l,mid,x);
        a[x].rc=s+1;build(mid+1,r,x);
    }
    void change(int x,int y,int z,int xx,int l,int r)     //新结点编号,,,对应结点编号,[l,r]
    {
        if (l==r) {a[x].sum=a[xx].sum+z;return ;}
        int mid=(l+r)>>1;
        if (y<=mid)
        {
            a[x].rc=a[xx].rc;
            s++;a[x].lc=s;
            change(s,y,z,a[xx].lc,l,mid);
        }
        else
        {
            a[x].lc=a[xx].lc;
            s++;a[x].rc=s;
            change(s,y,z,a[xx].rc,mid+1,r);
        }
        a[x].sum=a[a[x].lc].sum+a[a[x].rc].sum;
    }
    int query(int x,int y,int z,int l,int r)
    {
        if (l==r) return b[l];
        if (a[a[y].lc].sum-a[a[x].lc].sum>=z) return query(a[x].lc,a[y].lc,z,l,(l+r)>>1);
        else return query(a[x].rc,a[y].rc,z-(a[a[y].lc].sum-a[a[x].lc].sum),((l+r)>>1)+1,r);
    }
    void init(int _n)
    {
        this->n=_n;
        memset(a,0,sizeof(a));
    }
    void solve()
    {
            for (int i=1;i<=n;i++)
                scanf("%d",&b[i]),d[i]=b[i];
            sort(b+1,b+1+n);
            k=unique(b+1,b+1+n)-b-1;              //离散数据
            s=0;
            build(1,k,1);
            h[0]=1;
            for (int i=1;i<=n;i++)
            {
                s++;h[i]=s;
                change(s,Hash(d[i]),1,h[i-1],1,k); 
            }
    }
    int query(int x,int y,int z)//区间[x,y]中的第z大数
    {
        return query(h[x-1],h[y],z,1,n);        
    }
};

树上 K 大数

const int maxn=100010;
struct ptree{
    int n,m,a[maxn],b[maxn],pos[maxn],cnt;
    struct node{int v,nxt;}E[maxn<<1];
    int head[maxn],tot;
    int fa[maxn],dep[maxn],top[maxn];
    int size[maxn],son[maxn];
    int lft[maxn<<5],rht[maxn<<5];
    int rt[maxn<<5],sum[maxn<<5],sz;
    int ans;
    void add(int u,int v)
    {
        E[++tot].nxt=head[u];
        E[tot].v=v;
        head[u]=tot;
    }
    void dfs1(int u,int pa)
    {
        size[u]=1;
        for(int i=head[u];i;i=E[i].nxt)
        {
            int v=E[i].v;
            if(v==pa) continue;
            dep[v]=dep[u]+1;  fa[v]=u;
            dfs1(v,u);
            size[u]+=size[v];
            if(size[v]>size[son[u]]) son[u]=v;
        }
    }
    void dfs2(int u,int tp)
    {
        top[u]=tp;
        if(son[u]) dfs2(son[u],tp);
        for(int i=head[u];i;i=E[i].nxt)
        {
            int v=E[i].v;
            if(v==fa[u]||v==son[u]) continue;
            dfs2(v,v);
        }
    }
    int update(int pre,int ll,int rr,int x)
    {
        int rt=++sz;
        lft[rt]=lft[pre]; rht[rt]=rht[pre]; sum[rt]=sum[pre]+1;
        if(ll<rr)
        {
            int mid=ll+rr>>1;
            if(x<=mid) lft[rt]=update(lft[pre],ll,mid,x);
            else rht[rt]=update(rht[pre],mid+1,rr,x);
        }
        return rt;
    }
    void dfs(int u)
    {
        int x=lower_bound(pos+1,pos+1+cnt,a[u])-pos;
        rt[u]=update(rt[fa[u]],1,cnt,x);//以fa[u]为上一棵主席树建树
        for(int i=head[u];i;i=E[i].nxt)
        if(E[i].v!=fa[u]) dfs(E[i].v);
    }
    int LCA(int u,int v)
    {
        while(top[u]!=top[v])
        {
            if(dep[top[u]]>dep[top[v]]) u=fa[top[u]];
            else v=fa[top[v]];
        }
        if(dep[u]<dep[v]) return u;
        else return v;
    }
    int query(int u,int v,int lca,int gra,int ll,int rr,int k)
    {
        if(ll==rr) return ll;
        int x=sum[lft[u]]+sum[lft[v]]-sum[lft[lca]]-sum[lft[gra]];//差分得路径
        int mid=ll+rr>>1;
        if(x>=k) return query(lft[u],lft[v],lft[lca],lft[gra],ll,mid,k);
        else return query(rht[u],rht[v],rht[lca],rht[gra],mid+1,rr,k-x);
    }
    void init(int _n)
    {
        this->n=_n;
    }
    int solve()
    {
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]),b[i]=a[i];
        sort(b+1,b+1+n);
        for(int i=1;i<=n;++i)
        if(i==1||b[i]!=b[i-1])
        pos[++cnt]=b[i];
        for(int i=1;i<n;++i)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add(u,v); add(v,u);
        }
        dfs1(1,0);dfs2(1,1);
        dfs(1);
    }
    int query(int u,int v,int k)//询问(u,v,k)，回答u和v这两个节点间第K小的点权
    {
         int lca=LCA(u,v);
         return pos[query(rt[u],rt[v],rt[lca],rt[fa[lca]],1,cnt,k)];
    }
}tree;

树链剖分

struct tree_chain_split{
    int n,root,point[100010],po,T;
    struct data
    {
        int fa,top,c,ne,d,point,l,r;
        LL x;
    }a[100010];
    vector<int> b[100010];
    bool v[100010];
    struct ST
    {
        LL x,tag;
    }tree[400010];
    void dfs1(int x)
    {
        v[x]=true;
        int Max=0,w=0;
        for (int i=0;i<b[x].size();i++)
            if (!v[b[x][i]])
            {
                a[b[x][i]].d=a[x].d+1;
                dfs1(b[x][i]);
                if (a[b[x][i]].c>Max) Max=a[b[x][i]].c,w=b[x][i];
                a[x].c+=a[b[x][i]].c;
                a[b[x][i]].fa=x;
            }
        a[x].ne=w;a[x].c++;
    }
    void dfs2(int x,int y)
    {
        v[x]=true,point[++po]=x,a[x].point=po,a[x].top=y;a[x].l=po;
        if (!v[a[x].ne] && a[x].ne!=0) dfs2(a[x].ne,a[x].top);
        for (int i=0;i<b[x].size();i++)
                if (!v[b[x][i]])
                    dfs2(b[x][i],b[x][i]);
        a[x].r=po;
    }
    void Pushdown(int x,int l,int r)
    {
        if (tree[x].tag!=0)
        {
            tree[x<<1].tag+=tree[x].tag;
            tree[x<<1|1].tag+=tree[x].tag;
            tree[x].x+=tree[x].tag*(LL)(r-l+1);
            tree[x].tag=0;
        }
    }
    void change(int lq,int rq,int x,int l,int r,LL z)
    {
        if (lq<=l && rq>=r) {tree[x].tag+=z;return ;}
        int mid=l+r>>1;
        Pushdown(x,l,r);
        if (lq<=mid) change(lq,rq,x<<1,l,mid,z);
        if (rq>mid) change(lq,rq,x<<1|1,mid+1,r,z);
        tree[x].x=tree[x<<1].x+tree[x<<1|1].x+tree[x<<1].tag*(LL)(mid-l+1)+tree[x<<1|1].tag*(LL)(r-mid);
    }
    LL query(int lq,int rq,int x,int l,int r)
    {
        if (lq<=l && rq>=r) return tree[x].x+tree[x].tag*(LL)(r-l+1);
        int mid=l+r>>1;
        LL res=0;
        Pushdown(x,l,r);
        if (lq<=mid) res+=query(lq,rq,x<<1,l,mid);
        if (rq>mid) res+=query(lq,rq,x<<1|1,mid+1,r);
        tree[x].x=tree[x<<1].x+tree[x<<1|1].x+tree[x<<1].tag*(LL)(mid-l+1)+tree[x<<1|1].tag*(LL)(r-mid);
        return res; 
    }
    void build(int l,int r,int x)
    {
        if (l==r) {tree[x].x=a[point[l]].x;return ;}
        int mid=l+r>>1;
        build(l,mid,x<<1);build(mid+1,r,x<<1|1);
        tree[x].x=tree[x<<1].x+tree[x<<1|1].x;
        tree[x].tag=0;
    }
    void init(int _n,int _r)
    {
        this->n=_n;this->root=_r;
        memset(a,0,sizeof(a));
        int x,y;LL z;
        for (int i=1;i<=n;i++)
            scanf("%lld",&a[i].x);//每一个点的权值
        for (int i=1;i<n;i++)
            scanf("%d%d",&x,&y),b[x].push_back(y),b[y].push_back(x);
    }
    void solve()
    {
        memset(tree,0,sizeof(tree));
        memset(v,false,sizeof(v));
        a[root].d=1;a[root].fa=1;
        dfs1(root);
        memset(v,false,sizeof(v));
        po=0;
        dfs2(root,root);
        build(1,n,1);
    }
    void change_point(int x,LL z){change(a[x].point,a[x].point,1,1,n,z);}
    void change_subtree(int x,LL z){change(a[x].l,a[x].r,1,1,n,z);}
    void change_chain(int x,int y,LL z)
    {
        while (a[x].top!=a[y].top)
        {
            if (a[a[x].top].d<a[a[y].top].d) swap(x,y);
            change(a[a[x].top].point,a[x].point,1,1,n,z);
            x=a[a[x].top].fa;
        }
        if (a[x].d>a[y].d) swap(x,y);
        change(a[x].point,a[y].point,1,1,n,z);
    }
    int Find(int x,int y)    //找x向上y个
    {
        while (a[x].d-a[a[x].top].d<y) y-=a[x].d-a[a[x].top].d+1,x=a[a[x].top].fa;
        return point[a[x].point-y];
    }
    int lca(int x,int y)     //点x、y的lca
    {
        while (a[x].top!=a[y].top)
        {
            if (a[a[x].top].d<a[a[y].top].d) swap(x,y);
            x=a[a[x].top].fa;
        }
        if (a[x].d>a[y].d) swap(x,y);
        return x;
    }
}tree;

树套树

  • 1 x y：把a[x]修改为y。

  • 2 x y k：查询[x,y]内第k小值。

const int N = 200010, M = 524289;
int n, m, cnt, i, a[N], op[N][4], b[N];
int lower(int x)
{
    int l = 1, r = cnt, t, mid;
    while (l <= r)
        if (b[mid = (l + r) >> 1] <= x)
            l = (t = mid) + 1;
        else
            r = mid - 1;
    return t;
}
struct node
{
    int val, cnt, sum, p;
    node *l, *r;
    node()
    {
        val = sum = cnt = p = 0;
        l = r = NULL;
    }
    inline void up() { sum = l->sum + r->sum + cnt; }
} *blank = new (node), *T[M], pool[2000000], *cur;
void Rotatel(node *&x)
{
    node *y = x->r;
    x->r = y->l;
    x->up();
    y->l = x;
    y->up();
    x = y;
}
void Rotater(node *&x)
{
    node *y = x->l;
    x->l = y->r;
    x->up();
    y->r = x;
    y->up();
    x = y;
}
void Ins(node *&x, int y, int p)
{
    if (x == blank)
    {
        x = cur++;
        x-> val = y;
        x-> l = x-> r = blank;
        x-> sum = x-> cnt = 1;
        x-> p = std::rand();
        return;
    }
    x-> sum += p;
    if (y == x-> val)
    {
        x-> cnt += p;
        return;
    }
    if (y<x-> val)
    {
        Ins(x-> l, y, p);
        if (x-> l-> p > x-> p)
            Rotater(x);
    }
    else
    {
        Ins(x-> r, y, p);
        if (x-> r-> p > x-> p)
            Rotatel(x);
    }
}
int Ask(node *x, int y)
{ //ask how many <= y
    int t = 0;
    while (x != blank)
        if (y<x-> val)
            x = x-> l;
        else
            t += x-> l-> sum + x-> cnt, x = x-> r;
    return t;
}
void add(int v, int i, int p)
{
    int a = 1, b = cnt, mid, f = 1, x = 1;
    while (a < b)
    {
        if (f)
            Ins(T[x], i, p);
        mid = (a + b) >> 1;
        x <<= 1;
        if (f = v <= mid)
            b = mid;
        else
            a = mid + 1, x |= 1;
    }
    Ins(T[x], i, p);
}
int kth(int l, int r, int k)
{
    int x = 1, a = 1, b = cnt, mid;
    while (a < b)
    {
        mid = (a + b) >> 1;
        x <<= 1;
        int t = Ask(T[x], r)-Ask(T[x], l-1);
        if (k <= t)
            b = mid;
        else
            k-= t, a = mid + 1, x |= 1;
    }
    return a;
}
void build(int x, int a, int b)
{
    T[x] = blank;
    if (a == b)
        return;
    int mid = (a + b) >> 1;
    build(x << 1, a, mid), build(x << 1 | 1, mid + 1, b);
}
int main()
{
    int T;read(T);
    blank-> l = blank-> r = blank;
    while (T--)
    {
        read(n);read(m);
        cur = pool;
        for (i = 1; i <= n; i++)
            read(a[i]), b[i] = a[i];
        cnt = n;
        for (i = 1; i <= m; i++)
        {
            read(op[i][0]), read(op[i][1]), read(op[i][2]);
            if (op[i][0] == 1)
                b[++cnt] = op[i][2];
            else
                read(op[i][3]);
        }
        sort(b + 1, b + cnt + 1);
        for (i = 1; i <= n; i++)
            a[i] = lower(a[i]);
        for (i = 1; i <= m; i++)
            if (op[i][0] == 1)
                op[i][2] = lower(op[i][2]);
        build(1, 1, cnt);
        for (i = 1; i <= n; i++)
            add(a[i], i, 1);
        for (i = 1; i <= m; i++)
        {
            if (op[i][0] == 1)
                add(a[op[i][1]], op[i][1],-1), add(a[op[i][1]] = op[i][2], op[i][1], 1);
            else
                printf("%d\n", b[kth(op[i][1], op[i][2], op[i][3])]);
        }
    }
}

倍增算法

树上 lca 倍增

#define MAXN 100010
struct LCA
{
    int n,m,S,c[MAXN],h[MAXN],to[MAXN*2],ne[MAXN*2],d[MAXN],p[MAXN*2][20];
    void dfs(int u)
    {
        c[u]=1;
        for (int i=h[u];i!=-1;i=ne[i])
        {
            if (!d[to[i]])
            {
                d[to[i]]=d[u]+1;
                p[to[i]][0]=u;
                dfs(to[i]);
                c[u]+=c[to[i]];
            }
        }
    }
    void solve()
    {
        for (int j=1;(1<<j)<=n;j++)
            for (int i=1;i<=n;i++)
                if (p[i][j-1]!=-1) p[i][j]=p[p[i][j-1]][j-1];
    }
    int lca(int x,int y)
    {
        if (d[x]<d[y]) swap(x,y);
        int i;
        for (i=0;(1<<i)<=d[x];i++);i--;
        for (int j=i;j>=0;j--)
            if (d[x]-(1<<j)>=d[y]) x=p[x][j];
        if (x==y) return x;
        for (int j=i;j>=0;j--)
            if (p[x][j]!=-1 && p[x][j]!=p[y][j])
                x=p[x][j],y=p[y][j];
        return p[x][0];
    }
    void Add(int x,int y)
    {
        S++;to[S]=x;ne[S]=h[y];h[y]=S;
        S++;to[S]=y;ne[S]=h[x];h[x]=S;
    }
    int Find(int x,int y)
    {
        y=d[x]-y;
        int i;
        for (i=0;(1<<i)<=d[x];i++);i--;
        for (int j=i;j>=0;j--)
            if (d[x]-(1<<j)>=y) x=p[x][j];
        return x;
    }
    void pre(int root)
    {
        d[root]=1;dfs(root);solve();
    }
    void init(int _n)
    {
        memset(h,-1,sizeof(h));
        memset(d,0,sizeof(d));
        S=0;this->n=_n;this->m=_n-1;
    }
}lca;

CDQ 分治

三维偏序

第一维排序以后不再考虑，第二维利用归并排序，第三维用数据结构维护

  • 注意数据结构不要 memset ，手动回撤操作

二位数点问题

int n,m,k,K,b[600010],c[600010];
LL ans;
struct data
{
    int x,r,f;
}a[100010];
struct query
{
    int l,r,op,le;
    query(int a=0,int b=0,int c=0,int d=0):l(a),r(b),op(c),le(d){}
}q[600010],temp[600010];

void add(int x,int y)
{
    for (;x<=600000;x+=x&-x) c[x]+=y;
}

int sum(int x)
{
    int ans=0;
    for (;x;x-=x&-x) ans+=c[x];
    return ans;
}

int Hash(int x)
{
    return lower_bound(b+1,b+1+K,x)-b;
}

void move(query &x,query y)
{
    x.l=y.l;x.r=y.r;x.op=y.op;x.le=y.le;
}

void cdq(int l,int r)
{
    if (l==r) return ;
    int mid=l+r>>1;
    cdq(l,mid);cdq(mid+1,r);
    for (int i=l;i<=r;i++)//标记左边的操作
        if (i<=mid) q[i].le=1;else q[i].le=0; 
    int x=l,y=mid+1,s=0;
    while(1)//归并排序
    {
        if (x<=mid&&(y>r||q[x].l<=q[y].l)) move(temp[++s],q[x]),x++;
        else if (y<=r) move(temp[++s],q[y]),y++;
        else break;
    }
    s=0;
    for (int i=l;i<=r;i++)
    {
        move(q[i],temp[++s]);
        if (temp[s].le==1)//处理左边的操作
        {
            if (temp[s].op==2) add(Hash(temp[s].r),1);
            //printf("+ %d(%d)\n",Hash(temp[s].r),temp[s].r);
        }
        else//处理右边的询问
        {
            if (temp[s].op!=2) ans+=(LL)temp[s].op*sum(Hash(temp[s].r));
            //printf("ans+=%d*%d\n",temp[s].op,sum(Hash(temp[s].r)));
        }
    }
    s=1;
    for (int i=l;i<=r;i++,s++)
        if (temp[s].le==1&&temp[s].op==2) add(Hash(temp[s].r),-1);
}

int main()
{
    m=0;K=0;
    for(int i=1;i<=n;i++)
    {
        q[++m]=query(a-1,b-1,1);
        q[++m]=query(x,y,1);
        q[++m]=query(a-1,y,-1);
        q[++m]=query(x,b-1,-1);//查询子矩阵 (a,b)-(x,y)
        q[++m]=query(x,y,2);//修改位置 (x,y)
        b[++K]=x;//离散
    }
    sort(b+1,b+1+K);
    K=unique(b+1,b+1+K)-b-1;
    memset(c,0,sizeof(c));
    cdq(1,m);
    print(ans),puts("");
    return 0;
}