【luoguP3792】由乃与大母神原型和偶像崇拜

这个题目……佛了。
有一个一定不会被hack但是我写不出来的做法,考虑离散化+插入中间空位里面不存在的数,这个时候查询区间max,min和后继的min就可以做到一定正确,但是这样会被卡空间……cnbb
然后我们考虑随机化贪心,考虑给每个权值随机一个数,然后查询区间的异或和是否和我们预处理的一样即可。

#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned long long ulo;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = gch()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = gch();
    if(b == 1)
        x = - x;
}

const int ms = 5e5 + 10;

int n, m, lx, ly, lz, a[ms], tmpa[ms << 2], ta;

ulo p[ms << 2], su1[ms << 2], su2[ms << 2], P[ms << 2];

mt19937 rnd(time(0));

struct node
{
    int opt, x, y;
}poi[ms];

inline int lowbit(int x)
{
    return x & (-x);
}

inline void change1(int x, ulo v)
{
    while(x <= n)
        su1[x] += v, x += lowbit(x);
}

inline void change2(int x, ulo v)
{
    while(x <= n)
        su2[x] ^= v, x += lowbit(x);
}

inline ulo ask1(int x)
{
    ulo rt = 0;
    while(x)
        rt += su1[x], x -= lowbit(x);
    return rt;
}

inline ulo ask2(int x)
{
    ulo rt = 0;
    while(x)
        rt ^= su2[x], x -= lowbit(x);
    return rt;
}

int main()
{
    re(n), re(m);
    for(ri i = 1; i <= n; i ++)
        re(a[i]), tmpa[++ ta] = a[i], tmpa[++ ta] = a[i] + 1;
    for(ri i = 1; i <= m; i ++)
    {
        re(lx), re(ly), re(lz), poi[i] = (node){lx, ly, lz};
        if(lx == 1)
            tmpa[++ ta] = lz, tmpa[++ ta] = lz + 1;
    }
    sort(tmpa + 1, tmpa + 1 + ta);
    ta = unique(tmpa + 1, tmpa + 1 + ta) - tmpa - 1;
    p[0] = time(0);
    for(ri i = 1; i <= ta; i ++)
        p[i] = rnd(), P[i] = p[i] ^ P[i - 1];
    for(ri i = 1; i <= n; i ++)
        a[i] = lower_bound(tmpa + 1, tmpa + 1 + ta, a[i]) - tmpa, change1(i, a[i]), change2(i, p[a[i]]);
    for(ri i = 1; i <= m; i ++)
        if(poi[i].opt == 1)
            poi[i].y = lower_bound(tmpa + 1, tmpa + 1 + ta, poi[i].y) - tmpa;
    for(ri i = 1; i <= m; i ++)
    {
        if(poi[i].opt == 1)
            change1(poi[i].x, poi[i].y - a[poi[i].x]), change2(poi[i].x, p[poi[i].y] ^ p[a[poi[i].x]]), a[poi[i].x] = poi[i].y;
        else
        {
            ulo mid; 
            int l, r;
            mid = (ask1(poi[i].y) - ask1(poi[i].x - 1)) / (poi[i].y - poi[i].x + 1);
            l = mid - (poi[i].y - poi[i].x) / 2;
            if ((poi[i].y - poi[i].x) & 1)
                r = mid + (poi[i].y - poi[i].x) / 2 + 1;
            else
                r = mid + (poi[i].y - poi[i].x) / 2;
            if(l <= 0 || r > ta)
                puts("yuanxing");
            else if((ask2(poi[i].y) ^ ask2(poi[i].x - 1)) == (P[r] ^ P[l - 1]))
                puts("damushen");
            else
                puts("yuanxing");
        }
    }
    system("pause");
}

【luoguP3920】[WC2014]紫荆花之恋

n m d, w s m,劳资就是头铁,过了233333333333333333333
这个破题简直司马。
首先这个式子很好变化
Dis_{i}表示目前i这个点到根的距离。
Dis_{i}+Dis_{j}-2Dis_{lca(i,j)} \leq r_{i} + r_{j}
那么
Dis_{i} – r_{i}-Dis_{lca(i,j)} \leq r_{j} – Dis_{j} + Dis_{lca(i,j)}
然后你就直接把每个点都当lca来看的话,把左右两边的值插进u这个点的平衡树就好了,注意因为你要查询它的父亲,所以要把子树的信息传上来,建两个平衡树,这是因为假如你到达了lca的父亲,思考下,如果直接查询子树信息,这里会计算deep[lca]次。再外面套个点分树,复杂度O(nlog^2n)
说着挺简单的,维护贼·t·m·恶·心。
首先你的平衡树就不能写splay/fhq,因为这俩哥们太慢。
treap不会,那么剩下最好写的就是替罪羊了。
替罪羊之前扯过。
那么就算你第一层替罪羊写完了,接下来的点分树还是动态的。
那么第二个好像也需要平衡,所以再套一层替罪羊树。可是问题是,如果我们只对点分树的一部分进行重构了,怎么办?
记录每个点在自己父亲儿子中的顺序,每次修改的时候找出Root,然后直接按照它在父亲的顺序进行O(1)的修改。
剩下的细节代码里有,不再详细叙述,大概破了学oi以来写的最长的正解(数据分治暴力不算)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = gch()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = gch();
    if(b == 1)
        x = - x;
}

const int ms = 1e5 + 10, Ms = 1e7 + 10;

const double Alpha = 0.8;

int n, lx, ly, lz;

lo lastans;

struct Dt
{
    struct Tree//树本身
    {
        int de[ms], fa[ms], dis[ms][105], sz[ms];

        unsigned h[ms];

        vector <int> a[ms];
    }tre;

    struct edge
    {
        int to, co;
    };

    vector <edge> a[ms];

    int n, cnt, Root, r[ms], w[ms], sz[ms];

    bool flag[ms];

    struct Sgt
    {
        int val[Ms], ch[Ms][2], sz[Ms], sonroot[ms], faroot[ms], Top, mem[Ms], tot, tmp[ms];

        void init(int tot)
        {
            Top = 0;
            for(ri i = tot; i; i --)
                mem[++ Top] = i;
        }

        int newnode(int v)
        {
            int t = mem[Top --]; val[t] = v, sz[t] = 1, ch[t][0] = 0, ch[t][1] = 0;
            return t;
        }

        void dfs(int pos)//准备拍扁重建
        {
            mem[++ Top] = pos;
            if(ch[pos][0])
                dfs(ch[pos][0]);
            tmp[++ tot] = val[pos];//这里是为了严格按照中序遍历
            if(ch[pos][1])
                dfs(ch[pos][1]);
        }

        int rebuild(int l, int r)
        {
            if(l == r)
                return newnode(tmp[l]);
            int mid = (l + r) >> 1, rt = newnode(tmp[mid]);
            sz[rt] = r - l + 1;
            if(mid > l)
                ch[rt][0] = rebuild(l, mid - 1);
            if(mid < r)
                ch[rt][1] = rebuild(mid + 1, r);
            return rt;
        }

        inline int Rebuild(int Rt, int v)//拍扁重建
        {
            tot = 0, dfs(Rt); bool fl = 1;
            for(ri i = 1; i <= tot; i ++)
                if(tmp[i] >= v)
                {
                    tot ++;
                    for(ri j = tot; j > i; j --)
                        tmp[j] = tmp[j - 1];
                    tmp[i] = v, fl = 0; break;
                }
            if(fl)
                tmp[++ tot] = v;
            return rebuild(1, tot);
        }

        void insert(int &x, int v)//替罪羊的重建过程
        {
            if(!x)
            {
                x = newnode(v); return;
            }
            sz[x] ++;
            if(v < val[x])
            {
                if(sz[ch[x][0]] > sz[x] * Alpha)
                    x = Rebuild(x, v);
                else
                    insert(ch[x][0], v);
            }
            else
            {
                if(sz[ch[x][1]] > sz[x] * Alpha)
                    x = Rebuild(x, v);
                else
                    insert(ch[x][1], v);
            }
        }

        void restore(int x)
        {
            mem[++ Top] = x;
            if(ch[x][0])
                restore(ch[x][0]);
            if(ch[x][1])
                restore(ch[x][1]);
        }

        int ask(int x, int v)
        {
            if(x == 0)
                return 0;
            if(v < val[x])
                return ask(ch[x][0], v);
            return ask(ch[x][1], v) + sz[ch[x][0]] + 1;
        }

        void faclear(int x)
        {
            if(faroot[x])
                restore(faroot[x]);
            faroot[x] = 0;
        }

        void sonclear(int x)
        {
            if(sonroot[x])
                restore(sonroot[x]);
            sonroot[x] = 0;
        }

        void fainsert(int x, int v)
        {
            insert(faroot[x], v);
        }

        void soninsert(int x, int v)
        {
            insert(sonroot[x], v);
        }

        int faask(int x, int v)
        {
            return ask(faroot[x], v);
        }

        int sonask(int x, int v)
        {
            return ask(sonroot[x], v);
        }

        void Give(int f, int t)
        {
            sonroot[t] = sonroot[f], sonroot[f] = 0;
        }
    }sgt;

    void init(int x, int y)
    {
        tre.a[0].push_back(0), tre.de[1] = 1, n = x, r[1] = y; 
        w[0] = n + 1, sgt.init(Ms - 1), sgt.fainsert(1, -y);
    }

    void dfs(int x)
    {
        cnt ++; flag[x] = 1; int Si = tre.a[x].size();
        for(ri i = 0; i < Si; i ++)
            dfs(tre.a[x][i]);
    }

    void askroot(int no, int f, int S)
    {
        sz[no] = 1, w[no] = 0; int to, Si = a[no].size();
        for(ri i = 0; i < Si; i ++)
            if((to = a[no][i].to) != f && flag[to])
                askroot(to, no, S), sz[no] += sz[to], w[no] = max(w[no], sz[to]);
        w[no] = max(w[no], S - sz[no]);
        if(w[no] < w[Root])
            Root = no;
    }

    void reasksz(int no, int f)//重新计算size
    {
        sz[no] = 1; int to, Si = a[no].size();
        for(ri i = 0; i < Si; i ++)
            if((to = a[no][i].to) != f && flag[to])
                reasksz(to, no), sz[no] += sz[to];
    }

    void reask(int no, int f, int fr, int d, int c)
    {
        int to;
        tre.sz[fr] ++, tre.dis[no][d] = c;
        sgt.fainsert(fr, c - r[no]), sgt.soninsert(Root, c - r[no]);
        for(ri i = 0; i < a[no].size(); i ++)
            if((to = a[no][i].to) != f && flag[to])
                reask(to, no, fr, d, c + a[no][i].co);
    }

    void Work(int no, int d, int tot)//具体的重构过程
    {
        tre.a[no].clear(), flag[no] = 0, tre.de[no] = d, sgt.faclear(no);
        sgt.fainsert(no, -r[no]), reasksz(no, 0), tre.sz[no] = 1, tre.dis[no][d] = 0;
        int Si = a[no].size(), to, ci = 0;
        for(ri i = 0; i < Si; i ++)
            if(flag[to = a[no][i].to])
                Root = 0, askroot(to, 0, sz[to]), sgt.sonclear(Root), reask(to, no, no, d, a[no][i].co);
        for(ri i = 0; i < Si; i ++)
            if(flag[to = a[no][i].to])//记录所有点在自己点分树上父亲,儿子的顺序
                Root = 0, askroot(to, 0, sz[to]), tre.fa[Root] = no, tre.a[no].push_back(Root), tre.h[Root] = ci, ci ++, Work(Root, d + 1, sz[to]);
    }

    void rebuild(int no)//对最大的不合法的点分树进行重构
    {
        cnt = 0, dfs(no), Root = 0, askroot(no, 0, cnt);
        tre.a[tre.fa[no]][tre.h[no]] = Root, tre.fa[Root] = tre.fa[no];//通过记录原来这个点儿子所在位置,对于没修改的点分树进行快速的对儿子的维护
        sgt.Give(no, Root), Work(Root, tre.de[no], cnt);
    }

    int insert(int no, int x, int y, int z)//插入到真实的树上
    {
        a[no].push_back((edge){x, y}), a[x].push_back((edge){no, y}); 
        r[no] = z, tre.sz[no] = 1, tre.fa[no] = x, tre.de[no] = tre.de[x] + 1;
        tre.a[x].push_back(no), tre.h[no] = tre.a[x].size() - 1;//h记录在父亲的位置?
        tre.dis[no][tre.de[no]] = 0, sgt.fainsert(no, -z);//这个dis应该是利用的随机树高不会超过logn……看脸看脸
        int No = no, las = no, rt = 0;
        for(ri i = tre.de[no] - 1; i; i --)
        {
            las = No, No = tre.fa[No], tre.sz[No] ++;
            tre.dis[no][i] = tre.dis[x][i] + y;//就直接复制点分树的距离
            sgt.fainsert(No, tre.dis[no][i] - z), sgt.soninsert(las, tre.dis[no][i] - z);
            if(tre.sz[las] > tre.sz[No] * Alpha + 1)
                rt = No;
        }
        if(rt)
            rebuild(rt);
        int ans = sgt.faask(no, z) - 1;
        No = no, las = no;
        for(ri i = tre.de[no] - 1; i; i --)
            las = No, No = tre.fa[No], ans += sgt.faask(No, z - tre.dis[no][i]), ans -= sgt.sonask(las, z - tre.dis[no][i]);
        return ans;
    }
}dt;

int main()
{
    re(n), re(n), re(lx), re(ly), re(lz), dt.init(n, lz);
    puts("0");
    for(ri i = 2; i <= n; i ++)
        re(lx), re(ly), re(lz), lx ^= (lastans % 1000000000), lastans += dt.insert(i, lx, ly, lz), printf("%lld\n", lastans);
}

【luoguP4211】[LNOI2014]LCA

这个题想法好神仙啊qwq。
考虑问题转化,我们现在很难对一堆点的lca进行快速查询——事实上最多可以有n^2种可能性,所以这是不现实的。
那么我们就考虑把dep[lca(i,z)]转化成其他东西。
考虑对每个i到根的路径打一个区间+1的标记,然后统计从z到根的路径上的权值和。为了防止询问间的影响,我们离线进行差分,将询问变成1到r减去1到l-1,那么现在就可以线段树+树剖了,O(nlog^2n)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 5e4 + 10;

const lo mo = 201314;

int n, q, tot = -1, cnt, ta, head[ms], de[ms], fa[ms], pos[ms], pre[ms], tp[ms], son[ms], sz[ms];

lo ans[ms];

struct node
{
    int num, pos, z, v;
}poi[ms << 1];

struct in
{
    int to, ne;
}ter[ms << 1];

inline void build(int f, int l)
{
    ter[++ tot] = (in){l, head[f]}, head[f] = tot;
    ter[++ tot] = (in){f, head[l]}, head[l] = tot;
}

void dfs1(int no)
{
    sz[no] = 1, de[no] = de[fa[no]] + 1;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(to == fa[no])
            continue;
        fa[to] = no, dfs1(to), sz[no] += sz[to];
        if((!son[no]) || sz[son[no]] < sz[to])
            son[no] = to;
    }
}

void dfs2(int no, int t)
{
    tp[no] = t, pos[no] = ++ cnt, pre[cnt] = no;
    if(son[no])
        dfs2(son[no], t);
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(to == fa[no] || to == son[no])
            continue;
        dfs2(to, to);
    }
}

inline bool cmp(node a, node b)
{
    return a.pos < b.pos;
}

struct Seg
{
    lo su[ms << 2], add[ms << 2], ds[ms << 2];

    inline void down(int w, int l, int r)
    {
        if(!add[w])
            return;
        int mid = (l + r) >> 1;
        add[w << 1] += add[w], su[w << 1] += add[w] * (mid - l + 1), su[w << 1] %= mo;
        add[w << 1 | 1] += add[w], su[w << 1 | 1] += add[w] * (r - mid), su[w << 1 | 1] %= mo;
        add[w] = 0;
    }

    lo ask(int w, int l, int r, int ll, int rr)
    {
        if(l == ll && r == rr)
            return su[w];
        down(w, l, r); int mid = (l + r) >> 1;
        if(rr <= mid)
            return ask(w << 1, l, mid, ll, rr);
        else if(ll > mid)
            return ask(w << 1 | 1, mid + 1, r, ll, rr);
        else
            return (ask(w << 1, l, mid, ll, mid) + ask(w << 1 | 1, mid + 1, r, mid + 1, rr)) % mo;
    }

    void change(int w, int l, int r, int ll, int rr, lo v)
    {
        if(l == ll && r == rr)
        {
            add[w] += v, su[w] += v * (r - l + 1), su[w] %= mo; return;
        }
        down(w, l, r); int mid = (l + r) >> 1;
        if(rr <= mid)
            change(w << 1, l, mid, ll, rr, v);
        else if(ll > mid)
            change(w << 1 | 1, mid + 1, r, ll, rr, v);
        else
            change(w << 1, l, mid, ll, mid, v), change(w << 1 | 1, mid + 1, r, mid + 1, rr, v);
        su[w] = (su[w << 1] + su[w << 1 | 1]) % mo;
    }
}seg;

inline void change(int x)
{
    while(tp[x] ^ tp[1])
        seg.change(1, 1, cnt, pos[tp[x]], pos[x], 1), x = fa[tp[x]];
    seg.change(1, 1, cnt, pos[1], pos[x], 1);
}

inline lo ask(int x)
{
    lo rt = 0;
    while(tp[x] ^ tp[1])
        rt += seg.ask(1, 1, cnt, pos[tp[x]], pos[x]), x = fa[tp[x]], rt %= mo;
    rt += seg.ask(1, 1, cnt, pos[1], pos[x]); rt %= mo;
    return rt;
}

int main()
{
    re(n), re(q), memset(head, -1, sizeof(head));
    for(ri i = 2; i <= n; i ++)
        re(fa[i]), fa[i] ++, build(fa[i], i);
    dfs1(1), dfs2(1, 1);
    int l, r, z;
    for(ri i = 1; i <= q; i ++)
    {
        re(l), re(r), re(z), r ++, z ++;
        poi[++ ta] = (node){i, l, z, -1};
        poi[++ ta] = (node){i, r, z, 1};
    }
    sort(poi + 1, poi + 1 + ta, cmp);
    int no = 0; //seg.build(1, 1, cnt);
    for(ri i = 1; i <= ta; i ++)
    {
        while(no < poi[i].pos)
            no ++, change(no);
        ans[poi[i].num] += ask(poi[i].z) * poi[i].v;
        ans[poi[i].num] %= mo;
    }
    for(ri i = 1; i <= q; i ++)
        ans[i] = (ans[i] + mo) % mo, cout << ans[i] << '\n';
}

【luoguP3703】[SDOI2017]树点涂色

这破题该死的难写。
首先考虑,他一口气从x到根,也就说在树上是连续的一段,那么可以考虑用树剖/LCT维护,这里用LCT。考虑每次跨越一条轻链答案+1,那么就用lct维护轻重链切换,每次lct断开的子树答案+1,接上去的答案-1
但是这个地方答案怎么维护?树转dfs序,上个线段树

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h++;
}

typedef long long lo;

typedef long double ld;

template <typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a;
    bool b = 0;
    while (!isdigit(a = getchar()))
        b = a == '-';
    while (isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if (b == 1)
        x = -x;
}

const int ms = 1e5 + 10;

int n, m, opt, lx, ly, fa[ms], head[ms], de[ms], pos[ms], pre[ms], rpos[ms], sz[ms], tp[ms], son[ms], cnt, tot = -1;

struct in
{
    int to, ne;
}ter[ms << 1];

inline void build(int f, int l)
{
    ter[++ tot] = (in){l, head[f]}, head[f] = tot;
    ter[++ tot] = (in){f, head[l]}, head[l] = tot;
}

struct Seg
{
    int mx[ms << 2], add[ms << 2];

    inline void build(int w, int l, int r)
    {
        if(l == r)
        {
            mx[w] = de[pre[l]]; return;
        }
        int mid = (l + r) >> 1;
        build(w << 1, l, mid), build(w << 1 | 1, mid + 1, r);
        mx[w] = max(mx[w << 1], mx[w << 1 | 1]);
    }

    inline void down(int w)
    {
        if(!add[w])
            return;
        mx[w << 1] += add[w], add[w << 1] += add[w];
        mx[w << 1 | 1] += add[w], add[w << 1 | 1] += add[w];
        add[w] = 0;
    }

    int ask(int w, int l, int r, int ll, int rr)
    {
        if(l == ll && r == rr)
            return mx[w];
        down(w); int mid = (l + r) >> 1, rt = 0;
        if(rr <= mid)
            rt = ask(w << 1, l, mid, ll, rr);
        else if(ll > mid)
            rt = ask(w << 1 | 1, mid + 1, r, ll, rr);
        else
            rt = max(ask(w << 1, l, mid, ll, mid), ask(w << 1 | 1, mid + 1, r, mid + 1, rr));
        mx[w] = max(mx[w << 1], mx[w << 1 | 1]); return rt;
    }

    inline int Ask(int x)
    {
        int w = 1, l = 1, r = cnt;
        while(l != r)
        {
            down(w);
            int mid = (l + r) >> 1;
            if(x <= mid)
                w <<= 1, r = mid;
            else
                w = w << 1 | 1, l = mid + 1;
        }
        return mx[w];
    }

    void change(int w, int l, int r, int ll, int rr, int v)
    {
        if(l == ll && r == rr)
        {
            mx[w] += v, add[w] += v; return;
        }
        down(w); int mid = (l + r) >> 1;
        if(rr <= mid)
            change(w << 1, l, mid, ll, rr, v);
        else if(ll > mid)
            change(w << 1 | 1, mid + 1, r, ll, rr, v);
        else
            change(w << 1, l, mid, ll, mid, v), change(w << 1 | 1, mid + 1, r, mid + 1, rr, v);
        mx[w] = max(mx[w << 1], mx[w << 1 | 1]);
    }
}seg;

struct Lct
{
    int ch[ms][2], Fa[ms], lpos[ms]; 

    inline bool dir(int x)
    {
        return ch[Fa[x]][1] == x;
    }

    inline bool isroot(int x)
    {
        return ch[Fa[x]][0] != x && ch[Fa[x]][1] != x;
    }

    inline void rotate(int x)
    {
        int d = dir(x), f = Fa[x], g = Fa[f];
        Fa[x] = g;
        if(!isroot(f))
            ch[g][dir(f)] = x;
        ch[f][d] = ch[x][d ^ 1], Fa[f] = x, ch[x][d ^ 1] = f;
        if(ch[f][d])
            Fa[ch[f][d]] = f;
        lpos[f] = ch[f][0] ? lpos[ch[f][0]] : f;
        lpos[x] = ch[x][0] ? lpos[ch[x][0]] : x;
    }

    inline void splay(int x)
    {
        for(ri i; (i = Fa[x]) && (!isroot(x)); rotate(x))
            if(!isroot(i))
                rotate(dir(x) == dir(i) ? i : x);
    }

    inline int find(ri x)
    {
        while(ch[x][0])
            x = ch[x][0];
        return x;
    }

    inline void access(int x)
    {
        int las = 0, y;
        while(x)
        {
            splay(x);
            if(ch[x][1])
                y = lpos[ch[x][1]], seg.change(1, 1, cnt, pos[y], rpos[y], 1);
            if((ch[x][1] = las))
                y = lpos[las], seg.change(1, 1, cnt, pos[y], rpos[y], - 1);
            las = x, x = Fa[x];
        }
    }
}lct;

void dfs1(int no)
{
    de[no] = de[fa[no]] + 1, sz[no] = 1, lct.Fa[no] = fa[no], lct.lpos[no] = no;
    pos[no] = ++ cnt, pre[cnt] = no;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(to == fa[no])
            continue;
        fa[to] = no, dfs1(to), sz[no] += sz[to];
        if((!son[no]) || sz[son[no]] < sz[to])
            son[no] = to;
    }
    rpos[no] = cnt;
}

void dfs2(int no, int t)
{
    tp[no] = t;
    if(son[no])
        dfs2(son[no], t);
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(to == fa[no] || to == son[no])
            continue;
        dfs2(to, to);
    }
}

inline int lca(int x, int y)
{
     while(tp[x] ^ tp[y])
        (de[tp[x]] >= de[tp[y]]) ? x = fa[tp[x]] : y = fa[tp[y]];
    return de[x] <= de[y] ? x : y;
}

int main()
{
    re(n), re(m); memset(head, -1, sizeof(head));
    for(ri i = 1; i < n; i ++)
        re(lx), re(ly), build(lx, ly);
    dfs1(1), dfs2(1, 1), seg.build(1, 1, cnt);
    while(m --)
    {
        re(opt), re(lx);
        if(opt == 1)
            lct.access(lx);
        else if(opt == 2)
            re(ly), printf("%d\n", seg.Ask(pos[lx]) + seg.Ask(pos[ly]) - (seg.Ask(pos[lca(lx, ly)]) << 1) + 1);
        else
            printf("%d\n", seg.ask(1, 1, cnt, pos[lx], rpos[lx]));
    }
}

【算法】cdq分治&整体二分

这两天学了学cdq分治和整体二分,感觉世界真奇妙
这两个东西用处就是在离线的时候代替恶心的树套树(然而有的时候还不如树套树好调emmmm),通过分治将询问修改按照一定顺序进行并且求出答案
cdq分治是一种用来解决偏序问题的好办法,归并排序就是一个cdq分治的个例,所以学过归并排序理解这里就会强很多。所谓偏序就是形如a.x < b.x a.y < b.y这种关系。当然小于号可以换成大于号,也可以不止两个不等式,有多个维度多个不等式。最多的一般是三维偏序。对于三维偏序,我们一般先会按照关键字顺序排个序(首先保证第一关键字有序),之后剩下两个维度,我们再像归并排序进行,不过一般不能直接归并,需要其他的数据结构来去维护。但是这样我们就将一些本来只有二维数据结构才能解决的问题通过cdq分治强行压掉一维,代码上要好写很多,而且常数也小了
放例题
luogu P3157[CQOI2011]动态逆序对
这个题就是一个典型的cdq分治,我们现在考虑原来的逆序对,实际上就是一个a.x < b.x a.y > b.y的二维偏序,支持删除操作后,我们又多了个新的关键字——被修改时间。然后删除挺烦人的,我们将删除变为插入,将操作倒过来,这样我们每次新插入一个值,三个关键字(被修改时间t,原序列位置pos,数字大小num)他们的关系就是a.t < b.t a.pos < b.pos a.num > b.num
那么这就是一个典型的三维偏序,预处理t,排序,然后按照归并做后面两个维度,用线段树/树状数组维护

// luogu-judger-enable-o2
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

const int ms = 100010;

int n, m, lx, ta, tail, sta[ms], a[ms], pos[ms];

lo ans[ms];

bool flag[ms];

struct in
{
    int t, pos, num; bool fl;//那么对于这个题目,我们设加入序列时间为t,位置为pos,数字大小为num,现在求a.t < b.t a.pos < b.pos a.num > b.num的个数 
}ter[ms], lin[ms];

struct es
{
    int l, r, v;
}ing[ms << 2];

inline bool cmpt(in a, in b)
{
    return a.t < b.t;//首先按照t排序,保证cdq分治中这一维度不会产生影响 
}

inline void up(int w)
{
    ing[w].v = ing[w << 1].v + ing[w << 1 | 1].v;
}

inline void insert(int w, int l, int v)//值域线段树,维护某段值域上的数的个数 
{
    if(ing[w].l == l && ing[w].r == l)
    {
        ing[w].v = (v == 0) ? 0 : (ing[w].v + v); return;
    }
    int mid = (ing[w].l + ing[w].r) >> 1;
    if(l <= mid)
        insert(w << 1, l, v);
    else
        insert(w << 1 | 1, l, v);
    up(w);
}

int ask(int w, int l, int r)//值域线段树查询 
{
    if(l > r)
        return 0;
    if(ing[w].l == l && ing[w].r == r)
        return ing[w].v;
    int mid = (ing[w].l + ing[w].r) >> 1;
    if(r <= mid)
        return ask(w << 1, l, r);
    else if(l > mid)
        return ask(w << 1 | 1, l, r);
    else
        return ask(w << 1, l, mid) + ask(w << 1 | 1, mid + 1, r);
}

void merge(int l, int r)//cdq分治具体过程 
{
    if(l == r)
        return;
    int mid = (l + r) >> 1, ll = l, rr = mid + 1, ta = l; lo d;
    merge(l, mid), merge(mid + 1, r);//先处理好两侧 
    while(ll <= mid && rr <= r)//对于t我们事先排序了,并不影响答案 
    {
        if(ter[ll].pos < ter[rr].pos)//然后我们就把它转化成一个二维的偏序问题了,这个时候和归并差不多,只是需要线段树维护 
            lin[ta ++] = ter[ll ++], insert(1, ter[ll - 1].num, 1);//每次先去pos小的,这是第二维 
        else//否则把答案处理下 
            ans[ter[rr].t] += (d = ask(1, ter[rr].num + 1, n)), lin[ta ++] = ter[rr ++];//要记住按哪维度记录答案!! 
    }
    while(ll <= mid)//把没进行完的操作进行完 
        lin[ta ++] = ter[ll ++], insert(1, ter[ll - 1].num, 1);
    while(rr <= r)
        ans[ter[rr].t] += (d = ask(1, ter[rr].num + 1, n)), lin[ta ++] = ter[rr ++];
    for(ri i = l; i <= mid; i ++)//删除每个点对线段树的影响 
        insert(1, ter[i].num, 0);
    for(ri i = l; i <= r; i ++)//把改好的序列放回去 
        ter[i] = lin[i];
    for(ri i = r; i >= l; i --)//我们不仅要正向考虑,还要反向考虑,即a.t > b.t a.pos > b.pos a.num < b.num 
    {
        if(ter[i].t <= mid)
            insert(1, ter[i].num, 1);
        else
            ans[ter[i].t] += (d = ask(1, 1, ter[i].num));
    }
    for(ri i = l; i <= r; i ++)//依然记得清空 
        insert(1, ter[i].num, 0);
}

inline void build(int w, int l, int r)//线段树建树 
{
    ing[w] = (es){l, r, 0};
    if(l == r)
        return;
    int mid = (l + r) >> 1;
    build(w << 1, l, mid), build(w << 1 | 1, mid + 1, r);
}

int main()
{
    re(n), re(m); int ci = n; ta = m;
    for(ri i = 1; i <= n; i ++)
        re(a[i]), pos[a[i]] = i;
    for(ri i = 1; i <= m; i ++)//首先我们逆向考虑,倒序看删除,即为插入 
        re(lx), flag[lx] = 1, ter[i] = (in){ci --, pos[lx], lx}, sta[++ tail] = lx;
    for(ri i = 1; i <= n; i ++)
        if(flag[a[i]] == 0)//这些一开始就插入的肯定时间要早 
            ter[++ ta] = (in){ci -- , i, a[i]};//对于答案,现在有3个因素影响,加入序列的时间,在序列中的位置,数字大小 
    sort(ter + 1, ter + 1 + n, cmpt), build(1, 1, n);
    merge(1, n);
    lo pri = 0;
    for(ri i = 1; i <= n; i ++)
        pri += ans[i];
    for(ri i = n; i >= n - m + 1; i --)
        printf("%lld\n", pri), pri -= ans[i];
}

luogu P3810【模板】三维偏序(陌上花开)
这个题和刚才那个题目基本一样,就是需要去个重这样的,但是我的代码只能在luogu拿到90分,因为剩下一个点mle,但是我在本机测那个点,只用了17m空间,bzoj上也通过了……所以我就精神ac了233333333333

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register long long

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

const int ms = 200010;

lo n, k, tre[ms], a[ms], lx, ly, lz, tot;

lo f[ms];

struct in
{
    lo a, b, c, cnt, ans;
}ter[ms], lin[ms];

inline bool cmpa(in a, in b)//这个题和刚才那个一样,只不过求的是顺序对 
{
    if(a.a != b.a)//依然要分关键字 
        return a.a < b.a;
    if(a.b != b.b)
        return a.b < b.b;
    if(a.c != b.c)
        return a.c < b.c;
}

inline lo lowbit(lo x)
{
    return x & (-x);
}

inline void add(lo x, lo v)
{
    while(x <= k)
        tre[x] += v, x += lowbit(x);
}

inline lo ask(lo x)
{
    lo rt = 0;
    while(x > 0)
        rt += tre[x], x -= lowbit(x);
    return rt;
}

inline void merge(lo l, lo r)
{
    if(l == r)//这个地方因为对于相同的操作来说,答案增加了cnt-1,一共会有cnt个cnt-1的答案 
    {
        ter[l].ans += ter[l].cnt - 1; return;
    }
    lo mid = (l + r) >> 1, ta = l;
    merge(l, mid), merge(mid + 1, r);
    for(ri i = l, j = mid + 1; i <= mid ||j <= r;)//压缩了下合并方式 
    {
        if(j > r || (i <= mid && ter[i].b <= ter[j].b))
            add(ter[i].c, ter[i].cnt), lin[ta ++] = ter[i ++];
        else
            ter[j].ans += ask(ter[j].c), lin[ta ++] = ter[j ++];
    }
    for(ri i = l; i <= mid; i ++)//删除…… 
        add(ter[i].c, -ter[i].cnt);
    for(ri i = l; i <= r; i ++)
        ter[i] = lin[i];
}

int main()
{
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    re(n), re(k);
    for(ri i = 1; i <= n; i ++)
        re(lx), re(ly), re(lz), ter[i] = (in){lx, ly, lz, 1, 0};
    sort(ter + 1, ter + 1 + n, cmpa); 
    for(ri i = 1; i <= n; i ++)//因为存在重复的情况,所以要去重 
    {
        if(ter[i].a != ter[i - 1].a || ter[i].b != ter[i - 1].b || ter[i].c != ter[i - 1].c)
            lin[++ tot] = ter[i], lin[tot].cnt = 1;
        else
            lin[tot].cnt ++;
    }
    for(ri i = 1; i <= tot; i ++)
        ter[i] = lin[i];
    merge(1, tot);
    for(ri i = 1; i <= tot; i +P3332 [ZJOI2013]K大数查询+)
        f[ter[i].ans] += ter[i].cnt;
    for(ri i = 0; i < n; i ++)
        printf("%lld\n", f[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

cdq分治就是这两道题了,有空再做……
整体二分,这个东西和cdq分治的思想也是类似的,我每次对询问二分答案,对于大于这个答案的我就丢到右区间,反之左区间,直到最后答案边界相同为止
至于中间怎么维护……还是要用线段树之类的数据结构了23333333
luogu P3332[ZJOI2013]K大数查询

// luogu-judger-enable-o2
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#define ri register int
#define debug(x) cout<<#x<<":"<<x<<endl
using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = gch()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = gch();
    if(b == 1)
        x = -x;
}

const lo ms = 100010;

lo la, lb, lc, ld, n, m, pri[ms];

struct in
{
    lo type, a, b, c, ans, pos;
}ter[ms], lx[ms << 1], ly[ms << 1];

struct es
{
    lo l, r, add, s;
}ing[400040];

inline void down(lo w)//下放标记 
{
    lo f = ing[w].add; ing[w].add = 0;
    ing[w << 1].add += f, ing[w << 1 | 1].add += f;
    ing[w << 1].s += (ing[w << 1].r - ing[w << 1].l + 1) * f;
    ing[w << 1 | 1].s += (ing[w << 1 | 1].r - ing[w << 1 | 1].l + 1) * f;
}

inline void up(lo w)//更新 
{
    ing[w].s = ing[w << 1].s + ing[w << 1 | 1].s;
}

void change(lo w, lo l, lo r, lo v)//维护一个区间线段树,记录区间内出现多少数 
{
    if(ing[w].l == l && ing[w].r == r)
    {
        ing[w].s += (ing[w].r - ing[w].l + 1) * v, ing[w].add += v; return;
    }
    lo mid = (ing[w].l + ing[w].r) >> 1; down(w);
    if(r <= mid)
        change(w << 1, l, r, v);
    else if(l > mid)
        change(w << 1 | 1, l, r, v);
    else
        change(w << 1, l, mid, v), change(w << 1 | 1, mid + 1, r, v);
    up(w);
}

inline void build(lo w, lo l, lo r)//建树 
{
    ing[w] = (es){l, r, 0, 0};
    if(l == r)
        return;
    lo mid = (l + r) >> 1;
    build(w << 1, l, mid), build(w << 1 | 1, mid + 1, r);
}

lo ask(lo w, lo l, lo r)//线段树查询 
{
    if(ing[w].l == l && ing[w].r == r)
        return ing[w].s;
    lo mid = (ing[w].l + ing[w].r) >> 1, rt = 0;
    down(w);
    if(r <= mid)
        rt = ask(w << 1, l, r);
    else if(l > mid)
        rt = ask(w << 1 | 1, l, r);
    else
        rt = ask(w << 1, l, mid) + ask(w << 1 | 1, mid + 1, r);
    up(w); return rt;
} 

void merge(lo s, lo t, lo l, lo r)//s t二分值域,l r二分询问 
{
    if(s == t)//如果值域答案确定,相应询问也确定了 
    {
        for(ri i = l; i <= r; i ++)
            if(ter[i].type == 2)
                ter[i].ans = s;
        return;
    }
    lo mid = (s + t) >> 1, ll = 0, rr = 0, lin;
    for(ri i = l; i <= r; i ++)
    {
        if(ter[i].type == 1)
        {
            if(ter[i].c <= mid)//对于插入的数比二分的答案较小的,这对于答案为mid以上的没有贡献,放左边 
                lx[++ ll] = ter[i];
            else//否则放在右边 
                change(1, ter[i].a, ter[i].b, 1), ly[++ rr] = ter[i];
        }
        if(ter[i].type == 2)
        {
            lin = ask(1, ter[i].a, ter[i].b);
            if(lin < ter[i].c)//同理,当查询的数排名靠后,我们就把它放在左区间 
                ter[i].c -= lin, lx[++ ll] = ter[i];
            else//否则放在右区间 
                ly[++ rr] = ter[i];
        }
    }
    for(ri i = l; i <= r; i ++)//清空线段树 
        if(ter[i].c > mid && ter[i].type == 1)
            change(1, ter[i].a, ter[i].b, -1);
    bool fa = 0, fb = 0;
    for(ri i = 1; i <= ll; i ++)//重新丢回原来数组 
        ter[i + l - 1] = lx[i], fa = 1;
    for(ri i = 1; i <= rr; i ++)
        ter[i + ll + l - 1] = ly[i], fb = 1;
    if(fa)//剪枝 
        merge(s, mid, l, l + ll - 1);
    if(fb)
        merge(mid + 1, t, l + ll, r);
}

int main()
{
    re(n), re(m); build(1, 1, n);
    for(ri i = 1; i <= m; i ++)
        re(la), re(lb), re(lc), re(ld), ter[i] = (in){la, lb, lc, ld, 0, i};
    merge(-n, n, 1, m);
    for(ri i = 1; i <= m; i ++)
        pri[ter[i].pos] = ter[i].ans;
    for(ri i = 1; i <= m; i ++)
        if(pri[i] != 0)
            printf("%d\n", pri[i]);
}