ZJ Day9

卡密：

观察发现一个点的改动只影响其下标质因数及其相关的数，又为了保证修改次数最小，只改动与最大质因数相关的值，因此只需求出在[1,n]内修改点的下标的最大质因数的倍数数量再排除修改点自身（-1）即可。

划分:

发现某一区间越大肯定越不优，因此可以通过魔改背包dp求出当右端点为r时且区间和为i时最短点最大值（即最小区间）。随后枚举左端l点求一区间和S，判断S是否为偶数且f(S/2)是否<l即可.

陷阱:

用行和列建立二分图，存在交点连边，若发现存在环则有偶数解，否则考虑奇数解。最终间图的结果如果不含环则为森林，使用树形dp求解。

文艺平衡树：

通过平衡树维护序列区间操作，但此时我们需要的只是平衡树的结构和处理方式，不需要额外的键值，不必在意二叉排序树本身的某些性质，因此保证答案正确。同线段树给区间打上翻转的懒标记，需要时pushdown即可。
code:

#include
#define N 100010
using namespace std;
int n,m;
int tot,rt,ls[N],rs[N],pri[N],num[N],siz[N],tag[N];
mt19937 rng(time(0));
void pushup(int q)
{
    siz[q]=siz[ls[q]]+siz[rs[q]]+1;
    return;
}
void change(int q)
{
    swap(ls[q],rs[q]);
    return;
}
void pushdown(int q)
{
    if(!tag[q]) return;
    tag[ls[q]]^=1;
    tag[rs[q]]^=1;
    tag[q]=0;
    change(q);
    return;
}
int merge(int l,int r) //lpri[r]) 
    {
        pushdown(l);
        rs[l]=merge(rs[l],r);
        pushup(l);
        return l;
    }
    else
    {
        pushdown(r);
        ls[r]=merge(l,ls[r]);
        pushup(r);
        return r;
    }
}
void split(int q,int k,int &l,int &r)
{
    if(q==0)
    {
        l=r=0;
        return;
    }
    pushdown(q);
    if(siz[ls[q]]+1<=k)
    {
        l=q;
        split(rs[q],k-siz[ls[q]]-1,rs[q],r);
    }
    else
    {
        r=q;
        split(ls[q],k,l,ls[q]);
    }
    pushup(q);
    return;
}
void insert(int x)
{
    tot++;
    pri[tot]=rng();
    num[tot]=x;
    siz[tot]=1;
    rt=merge(rt,tot);
    return;
}
void dfs(int q)
{
    if(q==0) return;
    pushdown(q);
    dfs(ls[q]);
    cout<<num[q]<>n>>m;
    for(int i=1;i>X>>Y;
        int l,r,p;
        split(rt,X-1,l,r);
        split(r,Y-X+1,p,r);
        tag[p]^=1;
        rt=merge(l,merge(p,r));
    }
    dfs(rt);
    return 0;
}