E

构造 二分图 拆位

给一个序列$A$，给一堆约束$(x,y,z)$，要求$A_x\oplus A_y=z$

需要构造一个$A$序列，使得$\sum A_i$最小，或报告无解。

位运算，尤其是异或，他是不进位的，不同位之间完全没有影响，考虑拆位。对于每一位就是一个只有$0,1$的情况。这样约束只有两类，$z=0/1$，也就是$A_x,A_y$在这一位相同$(0)$，或不同$(1)$。利用这个关系建图，会发现我们实际上就得到了一个二分图。

于是问题转化成给一堆关系，每个关系是$x,y$是同一类，或不是同一类。现在问这些约束能否都成立，互不冲突。在此基础上还要使得这一位是$0$对应的那一个集合，尽可能小。

这显然可以染色法/拓展域并查集判断二分图。如果是二分图就能能满足所有约束。满足约束后，还要最小化$0$集合的大小，可以比较$0,1$集合的大小，如果$0$集合较小，就交换$0,1$集合，这是可以交换的，因为约束只规定了，两个点的集合是否相同，没有规定每个点到底是$0$还是$1$。

这样计算出每一位的结果后，拼起来就知道所有$A_i$的值了

void solve()
{
    int n, m;
    cin >> n >> m;
    vvi e;
    rep(i, 1, m)
    {
        int x, y, z;
        cin >> x >> y >> z;

        e.push_back({x, y, z});
    }

    vi ans(n + 1);
    rep(i, 0, 30)
    {
        vector<vector<pii>> g(n + 1);
        for (auto &t : e)
        {
            g[t[0]].push_back({t[1], t[2] >> i & 1});
            g[t[1]].push_back({t[0], t[2] >> i & 1});
        }

        vi co(n + 1, -1);
        rep(j, 1, n)
        {
            if (co[j] == -1)
            {
                int c0 = 0, c1 = 0;
                vi cur;
                auto &&dfs = [&](auto &&dfs, int u, int c) -> bool
                {
                    co[u] = c;
                    cur.push_back(u);
                    if (c == 0)
                        c0++;
                    else
                        c1++;
                    for (auto [v, w] : g[u])
                    {
                        if (co[v] == -1 && !dfs(dfs, v, c ^ w))
                            return false;
                        if (w == 1 && co[v] == c || w == 0 && co[v] != c)
                            return false;
                    }
                    return true;
                };
                if (!dfs(dfs, j, 0))
                {
                    cout << -1;
                    return;
                }
                if (c1 > c0)
                {
                    for (int x : cur)
                    {
                        co[x] = -1;
                    }
                    dfs(dfs, j, 1);
                }
            }
        }

        rep(j, 1, n)
        {
            if (co[j] == 1)
            {
                ans[j] += (1ll << i);
            }
        }
    }

    rep(i, 1, n)
    {
        cout << ans[i] << ' ';
    }
}

F

逆序对 线段树

初始给一个序列，接下来$m$轮，每轮给所有元素加$1$，模$m$。问每一轮操作完序列的逆序对个数。或者说第$k$轮是$a_i+k$，问$k=0,...,m-1$每一轮的逆序对个数。

一个静态序列的逆序对是好求的，但是这相当于给我们$n$个序列，肯定不能每个都$O(n\log n)$求

这种问题一般就两个思路，要么是每一次操作后，新的结果只是在原本结果的基础上，有一个变化量，我们初始维护一下第一轮的结果，后面每一轮只用维护变化量即可

另一种思路是考虑贡献法，枚举每个元素，计算每个元素，对一系列情况的答案的贡献。

我开始想的是贡献法。考虑每一对元素$(a_i,a_j),i<j$，如果$a_i>a_j$，那么这对元素，有贡献的$k$实际上是两个区间$[0,m-(a_i-1)],[m-a_j,m-1]$。也就是只有$a_i$已经被取模了，但$a_j$还没有被取模这段时间，是没贡献的，其他都有贡献。

如果$a_i<a_j$，那么在$a_j$已经被取模，$a_i$还没被取模的这段时间，会形成逆序对，也就是$[m-a_j,m-a_i-1]$

每一个的贡献了都是一个差分，但似乎还是不能做，因为这样的元素对有$n^2$对。不能每一个都去差分。考虑类扫描线的思想，枚举$a_j$，一次处理$a_j$和所有$a_i$的贡献。注意到对于一个$a_j$，贡献里和$j$相关的都是可以立刻确定的，但是$i$可能有多个，不能确定。那么实际上我们这个时候就是只能确定$a_j$相关的，不用去处理$a_i$的。以$[m-a_j,m-a_i-1]$为例，枚举到$a_j$的时候，只用计算$[1,j]$里比$a_j$小的元素个数$k$，那么就有$k$次$[m-a_j,m]$区间加的贡献。对于$m-a_i-1$这一端的，则是我们在枚举$a_i$时，计算$[i,n]$里有多少个比$a_i$大的元素，对$[m-a_i,m]$进行$k$此区间减

struct Tree
{
#define ls u << 1
#define rs u << 1 | 1
    struct Node
    {
        int l, r;
        ll mx, add;
    } tr[N << 2];

    void pushup(int u)
    {
        tr[u].mx = tr[ls].mx + tr[rs].mx;
    }

    void pushdown(int u)
    {
        if (tr[u].add)
        {
            tr[ls].mx += tr[u].add * (tr[ls].r - tr[ls].l + 1);
            tr[rs].mx += tr[u].add * (tr[rs].r - tr[rs].l + 1);
            tr[ls].add += tr[u].add;
            tr[rs].add += tr[u].add;
            tr[u].add = 0;
        }
    }

    void build(int u, int l, int r)
    {
        tr[u] = {l, r, 0, 0};
        if (l == r)
        {
            tr[u].mx = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(ls, l, mid);
        build(rs, mid + 1, r);
        pushup(u);
    }

    void modify(int u, int l, int r, int val)
    {
        if (tr[u].l >= l && tr[u].r <= r)
        {
            tr[u].mx += val * (tr[u].r - tr[u].l + 1);
            tr[u].add += val;
            return;
        }
        else
        {
            int mid = (tr[u].l + tr[u].r) >> 1;
            pushdown(u);
            if (mid >= l)
                modify(ls, l, r, val);
            if (r > mid)
                modify(rs, l, r, val);
            pushup(u);
        }
    }

    ll query(int u, int l, int r)
    {
        if (l <= tr[u].l && tr[u].r <= r)
            return tr[u].mx;
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (r <= mid)
            return query(ls, l, r);
        if (l > mid)
            return query(rs, l, r);
        return query(ls, l, r) + query(rs, l, r);
    }
} t;
void solve()
{
    int n, m;
    cin >> n >> m;
    vi a(n + 1);
    rep(i, 1, n)
    {
        cin >> a[i];
    }

    vi ans(m + 1);

    t.build(1, 0, m);
    rep(i, 1, n)
    {
        int cnt = t.query(1, a[i] + 1, m);
        int x = m - a[i];
        ans[x] += cnt;

        if (a[i] != 0)
        {
            cnt = t.query(1, 0, a[i] - 1);
            ans[x] += cnt;
        }
        t.modify(1, a[i], a[i], 1);
    }

    t.build(1, 0, m);
    rep1(i, n, 1)
    {
        if (a[i] != 0)
        {
            int cnt = t.query(1, 0, a[i] - 1);
            int x = m - a[i];
            ans[0] += cnt;
            ans[x] -= cnt;
        }

        int cnt = t.query(1, a[i] + 1, m);
        int x = m - a[i];
        ans[x] -= cnt;

        t.modify(1, a[i], a[i], 1);
    }

    rep(i, 0, m - 1)
    {
        if (i)
            ans[i] += ans[i - 1];
        cout << ans[i] << '\n';
    }
}

当然这题考虑变化量也能做，考虑第$k$轮，会对答案产生影响的实际上只有在这一轮达到$m$然后变成$0$的元素，也就是初始值为$m-k$的元素。他们变成$0$之后会把原本存在的一些逆序对搞没，也就是后面比他小的元素，还会引入一些新的逆序对，也就是前面比他大的元素。注意由于变成$0$了，比他大和小都是很显然的，实际上只用统计前面的非$0$元素个数