CF757G

给定一棵树和一个排列 pp，每次可以给定 l,r,xl,r,x 询问 ∑i=lrdis(pi,x)\sum\limits_{i=l}^rdis(p_i,x)，或者交换排列相邻两项。强制在线。
n,q≤2×105n,q\leq2\times 10^5

这题告诉我们边分治有多么优秀。考虑区间问题可以转化成前缀和相减，然后发现容易往可持久化想。考虑到是与点对距离相关，那么考虑使用边分治。而边分树是天然的二叉树形态，那么可以支持可持久化。节点上维护左子树内激活的点的个数和距离和即可查询。而交换 px,px+1p_x,p_{x+1} 只对第 xx 棵边分树有影响。重新在第 x−1x-1 棵基础上建一下即可。

AGC047D

两棵树的题，考虑 暴力写挂，通道 等题的套路，可以考虑先在一棵树上枚举，再在另一棵树上计算。考虑这里点对的代价是路径，通常考虑树上路径时都要套树分治，再在另一棵树上虚树，但是这里并不用。考虑完全二叉树的性质，树高是 log⁡\log 的。于是直接枚举第一棵树的 lca，这时把这个 lca 的两个儿子的子树染成不同颜色，即只能不同颜色的点造成贡献。然后其实也不用建虚树，再次利用深度log的性质：考虑把lca的贡献差分，用白色的点在第二棵树上跳，给祖先都累加上对应的贡献，再用黑色的点往上跳，统计上即可。lca的贡献差分是经典套路。

AGC047E

这个题非常有意思啊，题意是用加法器和比较器来实现一个乘法器。

考虑我们有加法器，所以天然支持乘 22。那么转成二进制串的乘法可能会比较方便。
而 0101 变量的乘法是可以比较容易地支持的。它相当于与，全 11 则为 11。于是加起来与 00 比较即可。

具体地，考虑二进制串的乘法与高精乘类似，是一个卷积。那么从结果的高位往低位考虑，累加上卷到这位的贡献，每次 i−−i-- 时乘 22 即可。

那么现在就是要支持数转二进制串。只要从高往低考虑，能减就减。不能支持减法，维护一个 nownow，判断 now+2i≤anow+2^i\leq a 即可。≤\leq 只需把数加一用 << 代替。棘手的是无法支持条件判断。但幸运的是我们需要加的都是 22 的幂。那么只需将条件判断用 now+=[check]∗2inow+=[check]*2^i 替代即可。至此，我们实现了乘法器。操作次数是 O(log⁡2val)O(\log^2 val) 的。

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
struct node{char op;int x,y,z;};
int now=199999,p[63],a[31],b[31],tmp;
int New(){return now--;}
vector<node>ans;
int Add(int x,int y){
    int p=New();ans.pb(node{'+',x,y,p});
    return p;
}
void Add2(int x,int y){ans.pb(node{'+',x,y,x});}
void Shift(int x,int y){
    for(int i=0;i<y;i++)
        ans.pb(node{'+',x,x,x});
}
int cmp(int x,int y){
    int p=New();ans.pb(node{'<',x,y,p});
    return p;
}
void get(int *a,int pp){
    tmp=New();
    for(int i=30;~i;i--){
        a[i]=cmp(Add(tmp,p[i]),pp);
        int q=cmp(Add(tmp,p[i]),pp);
        Shift(q,i);Add2(tmp,q);
    }
}
int main(){
    // freopen("data.txt","w",stdout);
    p[0]=cmp(2,Add(0,1));
    ans.pb(node{'+',0,p[0],0});
    ans.pb(node{'+',1,p[0],1});
    for(int i=1;i<31;i++)
        p[i]=Add(p[i-1],p[i-1]);
    get(a,0);get(b,1);
    for(int i=60;~i;i--){
        Add2(2,2);
        for(int j=max(0,i-30);j<=min(30,i);j++)
            Add2(2,cmp(p[0],Add(a[j],b[i-j])));
    }
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();i++)
        printf("%c %d %d %d\n",ans[i].op,ans[i].x,ans[i].y,ans[i].z);
    return 0;
}

「CEOI2017」Mousetrap

QAQ我菜菜，想不到

考虑这棵树以捕鼠夹为根。

主要思路是考虑老鼠如果某个时刻不能动，我们就可以把该做的都做了，再放它直通捕鼠夹。

再看老鼠和夹子相邻的部分分，可以想到一个比较简单的dp：设 fif_i 表示老鼠在 ii 点，要往子树走，把它逼回 ii 点的最小代价。因为在老鼠走之前可以堵一个子树，那么一定堵 ff 最大的。那么老鼠会去次大的，然后在某个点停住不能动，此时把 ii 的其他子树也都堵住即可。即 fi=di+secif_i=d_i+sec_i，其中 did_i 表示儿子数，secisec_i 表示儿子中次大的 ff 值。这样即可解决这个部分分。

而其他的情况棘手的地方在于老鼠还可以往上走。在老鼠走的时候我们并不知道应该堵哪条路比较优。比如当老鼠在点 xx，我们如果堵 xx 的某个儿子，老鼠可以再往父亲走，我们这时只能堵父亲的最大，老鼠可以走次大。然而次大可能也很大，如果老鼠在 xx 时我们可以堵父亲的最大，到父亲时可以堵父亲的次大，就可能变得更优。看起来简单的 dp 不可行了，考虑二分答案。

考虑我们只要确定老鼠第一次向下走是去哪个点，那么之后的答案也就确定了，即 fxf_x 加上上面需要堵住的边。那么二分答案之后只需堵住会使答案超过二分的值的子树即可。如果堵不住或者这样的子树数量超过二分的值，都不可行，否则可行。