「Solution」中国好代码

考试时真就是写了个《中国好代码》呗。。。

link

分析

其实就是道一眼题。
可以发现，如果要写同余方程的话，每个学生的第一次转身时间是余数，转身周期是模数。
那么问题可以转化为:
给定$n$个模方程(下标从$1$到$n$)，支持两种操作：

• 交换$i,j$两个方程。
• 查询$[l,r]$的方程组成方程组后是否有解。
  根据刚学的扩展中国剩余定理的思路可以知道：我们能在$nlog$的时间复杂度里合并$n$个方程为一个。并满足区间可合并性。
  那么既然求区间内有无解，并且可以等价的合并，那么我们用线段树维护即可，每个节点维护一段区间内合并后的方程的模数与余数。
  然后就做完了。

代码

考试时真就是写了个《中国好代码》。。。
开始在push_up里面写了个ExCRT，后来发现查询时不那么方便，又写了个merge用来合并方程，发现丢线段树节点到merge里面不那么舒服，又开了个结构体装方程，然后merge里的ExCRT写错了，把r1(特解)写成了r2(当前方程的余数)。。。
有趣的是我写了两个ExCRT，第一个没错，第二个马上就挂了(早知道我就直接复制第一遍)。
然后代码很冗长。
写完就不想看了，跑去看了会第一题，结果考完发现写炸了。。。
混乱代码给我留下了深深的伤痛。。。
我应该好好学习如何把代码写好看精简代码。

#include <cstdio>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int MAXN = 1e5 + 5;

int t, n, q, tg[5];

struct node {
    int m, r;
    int flag;
} a[MAXN];

struct SegmentTree {
    int m, ri, flag;
    int l, r;
} s[MAXN * 4];

int gcd(int x, int y) {
    if (y == 0)
        return x;
    else
        return gcd(y, x % y);
}

void exgcd(int& x, int& y, int a, int b) {
    if (b == 0) {
        x = 1, y = 0;
        return;
    }
    exgcd(x, y, b, a % b);
    int t = x;
    x = y, y = t - a / b * y;
    return;
}

void push_up(int p) {
    if (s[p << 1].flag == -1 || s[p << 1 | 1].flag == -1) {
        s[p].flag = s[p].m = s[p].ri = -1;
        return;
    }
    int m1 = s[p << 1].m, r1 = s[p << 1].ri;
    int m2 = s[p << 1 | 1].m, r2 = s[p << 1 | 1].ri;
    int g = gcd(m1, m2);
    int tmp = r2 - r1;
    if (tmp % g != 0) {
        s[p].flag = s[p].m = s[p].ri = -1;
        return;
    }
    int k1, k2;
    exgcd(k1, k2, m1 / g, m2 / g);
    k1 = (tmp / g * k1) % (m2 / g);
    r1 += k1 * m1;
    m1 = m1 / g * m2;
    r1 = (r1 + m1) % m1;
    s[p].flag = 1, s[p].m = m1, s[p].ri = r1;
}

node merge(node x, node y) {
    node res;
    res.flag = 1;
    if (x.flag == -1 || y.flag == -1) {
        res.flag = res.m = res.r = -1;
        return res;
    }
    int m1 = x.m, r1 = x.r;
    int m2 = y.m, r2 = y.r;
    int g = gcd(m1, m2);
    int tmp = r2 - r1;
    if (tmp % g != 0) {
        res.flag = res.m = res.r = -1;
        return res;
    }
    int k1, k2;
    exgcd(k1, k2, m1 / g, m2 / g);
    k1 = (tmp / g * k1) % (m2 / g);
    r1 += k1 * m1;
    m1 = m1 / g * m2;
    r1 = (r1 + m1) % m1;
    res.m = m1, res.r = r1, res.flag = 1;
    //此处的r1写成了r2...
    return res;
}

void build(int p, int l, int r) {
    s[p].l = l, s[p].r = r;
    if (l == r) {
        s[p].flag = 1;
        s[p].m = a[l].m, s[p].ri = a[l].r;
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    push_up(p);
}

void update(int p, int x, int l, int r, node val) {
    if (s[p].l == s[p].r) {
        s[p].m = val.m, s[p].ri = val.r;
        return;
    }
    int mid = (s[p].l + s[p].r) >> 1;
    if (x <= mid) {
        update(p << 1, x, l, r, val);
    } else
        update(p << 1 | 1, x, l, r, val);
    push_up(p);
}

node query(int p, int l, int r) {
    if (s[p].l >= l && s[p].r <= r) {
        node res;
        res.flag = 1;
        if (s[p].flag == -1) {
            res.flag = res.m = res.r = -1;
            return res;
        } else {
            res.m = s[p].m, res.r = s[p].ri;
            return res;
        }
    }
    int mid = (s[p].l + s[p].r) >> 1;
    node res;
    res.flag = 1;
    if (l <= mid) {
        res = query(p << 1, l, r);
        if (r > mid) {
            res = merge(res, query(p << 1 | 1, l, r));
        }
        return res;
    } else if (r > mid) {
        res = query(p << 1 | 1, l, r);
        return res;
    }
}

signed main() {
    //	freopen ("goodcode.in", "r", stdin);
    //	freopen ("goodcode.out", "w", stdout);
    scanf ("%lld", &t);
    while (t--) {
    	scanf ("%lld %lld", &n, &q);
        for (int i = 1; i <= 3; i++) {
        	scanf ("%lld", &tg[i]);
        }
        for (int i = 1, g; i <= n; i++) {
        	scanf ("%lld %lld", &a[i].r, &g);
            a[i].m = tg[g];
        }
        build(1, 1, n);
        while (q--) {
            int op, l, r;
            scanf ("%lld %lld %lld", &op, &l, &r);
            if (op == 0) {
                update(1, l, 1, n, a[r]);
                update(1, r, 1, n, a[l]);
                swap(a[r], a[l]);
            } else {
                node res = query(1, l, r);
                if (res.flag == -1) {
                    printf("No\n");
                } else {
                    printf("Yes\n");
                }
            }
        }
    }
    return 0;
}