序列（sequence）

不妨把所有的 b_i 变成 b_i-a_i，这样所有 a_i 就变成 0 了。然后考虑建图。把 i 号点的权值设为 a_i 的值，对于每个 t_i=2 的操作，在图中连一条无向边 (u_i,v_i)。那么每条这样的边的意义就是把它其中一个端点的部分权值“转运”到另一个端点，但对总权值没有影响。可以看出每个连通块中的任意两点的权值都是可以互相转运的。若某个连通块内所有点的权值之和等于 b_i 之和，这个连通块就是有解的。答案为 YES 当且仅当所有连通块都有解。下面记点 u 所在的连通块编号为 bel_u。

而 t_i=1 的操作就可以对总权值产生影响了。我们把它也看成这张图里的一条边，由上面的内容容易看出 u_i 或 v_i 连在同一个连通块中的任意一点都是相同的（对该连通块的权值和贡献相同）。那么我们把连通块缩点，在新图上连边 (bel_{u_i},bel_{v_i}) 即可。若 u_i 和 v_i 所在连通块相同，则将这个连通块打上标记 tag=1，表示该连通块内部可以对自身权值和产生 2 的倍数的贡献。

考虑新图的一条路径 (x,y)（不一定是简单路径），发现若这条路径长度为偶数，则 x 与 y 之间的权值也是可以相互转运的（可以画图看一下）。那么对于新图中包含奇环的连通块，任意两点间一定存在一条长度为偶数的路径。也就是说，可以将这个大的连通块再次缩成一个点。由于这个连通块里一定有 t_i=1 的边，所以可以认为它的 tag=1，那么它有解的条件就是权值和为偶数。

而对于不包含奇环的连通块，它一定是一个二分图。将其黑白染色，那么黑点到黑点、白点到白点的权值都可以互相转运，我们将黑点集和白点集分别缩点。黑点与白点之间只有长度为奇数的路径，即可以将黑点集的权值和 与 白点集的权值和同时加上一个值。那么我们现在已经可以得出这个连通块有解的条件了：

1. 权值和为偶数；
2. 若该连通块中所有点的 tag 都为 0，则黑点和白点的 b_i 之和相等。

证明比较显然。第二次的“缩点”不需要真缩，DFS 判断一下就可以了。

于是这道题就做完了，复杂度 O(Tn)。记得开 long long。

代码：

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN=110000;
struct Edge
{
    int u, v;
    Edge() {}
    Edge(int a, int b): u(a), v(b) {}
} e[MAXN];
vector<int> g[MAXN], h[MAXN];
int a[MAXN];
int bel[MAXN], bw[MAXN];
ll sum[MAXN];
bool tag[MAXN];
void dfs1(int u, int c)
{
    bel[u]=c, sum[c]+=a[u];
    for (int i=0; i<g[u].size(); i++)
    {
        int v=g[u][i];
        if (!bel[v]) dfs1(v, c);
    }
}
bool dfs2(int u, int c, bool& t, ll& sb, ll& sw)
{
    if (~bw[u]) return bw[u]==c;
    bw[u]=c, t|=tag[u];
    if (c==0) sb+=sum[u];
    else sw+=sum[u];
    bool ret=1;
    for (int i=0; i<h[u].size(); i++)
    {
        int v=h[u][i];
        ret&=dfs2(v, c^1, t, sb, sw);
    }
    return ret;
}
int main()
{
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, m, p=0, k=0;
        scanf("%d%d", &n, &m);
        for (int i=1; i<=n; i++) scanf("%d", &a[i]);
        for (int i=1; i<=n; i++)
        {
            int x; scanf("%d", &x); a[i]=x-a[i];
            g[i].clear(), h[i].clear();
        }
        for (int i=1; i<=m; i++)
        {
            int t, u, v;
            scanf("%d%d%d", &t, &u, &v);
            if (t==1) e[++p]=Edge(u, v);
            else g[u].push_back(v), g[v].push_back(u);
        }
        memset(bel, 0, sizeof bel);
        memset(sum, 0, sizeof sum);
        memset(tag, 0, sizeof tag);
        for (int i=1; i<=n; i++)
            if (!bel[i]) dfs1(i, ++k);
        for (int i=1; i<=p; i++)
            if (bel[e[i].u]==bel[e[i].v]) tag[bel[e[i].u]]=1;
            else
            {
                h[bel[e[i].u]].push_back(bel[e[i].v]);
                h[bel[e[i].v]].push_back(bel[e[i].u]);
            }
        memset(bw, -1, sizeof bw);
        bool ans=1;
        for (int i=1; i<=k; i++)
            if (bw[i]==-1)
            {
                bool tg=0; ll sumb=0, sumw=0;
                if (dfs2(i, 0, tg, sumb, sumw))
                    if (tg) ans&=(sumb+sumw)%2==0;
                    else ans&=sumb==sumw;
                else ans&=(sumb+sumw)%2==0;
            }
        puts(ans?"YES":"NO");
    }
    return 0;
}

冒泡排序（bubble）

考虑每一轮冒泡排序会对序列产生什么影响。记 c_i 为第 i 个位置前比 p_i 大的元素个数，发现每轮排序所有 c_i 会减一但不为负，整个序列 c 左移一位。因为对于每个前面有更大的元素的位置，它都会与这个元素交换，此时逆序对数减一。考虑维护 k 轮排序后的答案，发现第 i 个位置会对答案有 \max(k-a_i,0) 的贡献。可以维护 a_i 的前缀和和次数和，修改则只会影响 x 和 x+1 两个位置，在树状数组上暴力修改即可。复杂度 O((n+q)\log n)。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN=220000;
int n, m;
template<typename T>
struct BIT
{
    T s[MAXN];
    static int lb(int x) { return x&-x; }
    void clr() { for (int i=1; i<=n; i++) s[i]=0; }
    void add(int x, int k) { while (x>0) s[x]+=k, x-=lb(x); }
    T sum(int x) { T r=0; while (x<=n) r+=s[x], x+=lb(x); return r; }
};
int p[MAXN], c[MAXN];
BIT<int> bit1; BIT<ll> bit2;
void change(int x, int k)
{
    bit1.add(c[x], k);
    bit2.add(c[x], k*c[x]);
}
int main()
{
    freopen("bubble.in", "r", stdin);
    freopen("bubble.out", "w", stdout);
    scanf("%d%d", &n, &m);
    ll sum=0;
    for (int i=1; i<=n; i++)
    {
        scanf("%d", &p[i]);
        sum+=c[i]=bit1.sum(p[i]);
        bit1.add(p[i], 1);
    }
    bit1.clr();
    for (int i=1; i<=n; i++) change(i, 1);
    while (m--)
    {
        int op, x;
        scanf("%d%d", &op, &x);
        if (op==1)
        {
            change(x, -1), change(x+1, -1);
            swap(c[x], c[x+1]);
            if (p[x]<p[x+1]) c[x+1]++, sum++;
            else c[x]--, sum--;
            change(x, 1), change(x+1, 1);
            swap(p[x], p[x+1]);
        }
        else
        {
            if (x>n) puts("0");
            else if (x==0) printf("%lld\n", sum); 
            else printf("%lld\n", bit2.sum(x)-1ll*x*bit1.sum(x));
        }
    }
    return 0;
}

最小环（ring）

为了方便后面的操作，首先将 a_i 从小到大排序。对于一个固定的 k，我们可以得到一个 O(n) 的算法：

• 将序列拆成若干个模 k 的环，一个环中相邻元素距离为 k，不同环之间不影响；
• 将 a_i 按顺序分给这些环，每个环中贪心地选最小的放在中间，然后在右边放次小的，左边放第三小的……以此类推。

进一步观察，发现对于 \gcd(n,k) 相同的 k，环的构成是一样的，因此答案也相同。而 \gcd(n,k) 是 n 的因数，因此可以 O(\sqrt n) 枚举 n 的每个因数求出答案。复杂度 O(n\sqrt n+q)。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN=220000;
int n, m, a[MAXN];
bool b[MAXN];
ll ans[MAXN];
ll calc(const vector<int>& c)
{
    int l=c[0], r=0; ll ret=0;
    for (int i=0; i<c.size(); i++)
        if (i&1) ret+=1ll*l*c[i], l=c[i];
        else ret+=1ll*r*c[i], r=c[i];
    ret+=1ll*l*r;
    return ret;
}
void work(int d)
{
    memset(b, 0, sizeof b);
    int k=0;
    for (int i=0; i<n; i++)
        if (!b[i])
        {
            vector<int> c;
            int j=i;
            do
            {
                c.push_back(a[k++]);
                b[j]=1, j=(j+d)%n;
            }
            while (j!=i);
            ans[d]+=calc(c);
        }
}
int main()
{
    freopen("ring.in", "r", stdin);
    freopen("ring.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
    sort(a, a+n);
    for (int i=1; i*i<=n; i++)
        if (n%i==0)
        {
            work(i);
            if (i*i!=n) work(n/i);
        }
    while (m--)
    {
        int k; scanf("%d", &k);
        printf("%lld\n", ans[__gcd(n, k)]);
    }
    return 0;
}