We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Advanced
  4. Dynamic Summation
  5. Discussions

Dynamic Summation

  • esmailzadeh_ayu1
     + 0 comments

    using namespace std;

    const int MAXN = 100000;

    vector v[MAXN + 1]; vector child[MAXN + 1]; bool visited[MAXN + 1]; int startTime[MAXN + 1], endTime[MAXN + 1];

    int dfs(int now, int start) { startTime[now] = start; visited[now] = true; int sz = (int)v[now].size(); for (int i = 0; i < sz; i++) { if (!visited[v[now][i]]) { child[now].push_back(v[now][i]); start = dfs(v[now][i], start + 1); } } endTime[now] = start; return start; }

    const int NMOD = 5; int MOD[NMOD] = { 11 * 101 * 13 * 97 * 17 * 89, 19 * 83 * 23 * 81 * 25 * 29, 31 * 79 * 37 * 73 * 41, 43 * 47 * 49 * 53 * 59, 61 * 64 * 67 * 71 }; int p[26] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101 };

    int modidx[102];

    int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

    void init() { for (int i = 1; i <= 101; i++) { for (int j = 0; j < NMOD; j++) { if (gcd(i, MOD[j]) != 1) { modidx[i] = j; break; } } } }

    long long tree[NMOD][4 * MAXN], lazy[NMOD][4 * MAXN];

    long long ext_euclid(long long a, long long b, long long& x, long long& y) { long long t, d; if (b == 0) { x = 1; y = 0; return a; } d = ext_euclid(b, a%b, x, y); t = x, x = y, y = t - a / b*y; return d; }

    /* long long linear_modular_equation_system(long long B[], long long W[], long long k) { long long d, x, y, m, n = 1; long long a = 0; for (long long i = 0; i < k; i++) n *= W[i]; for (long long i = 0; i < k; i++) { m = n / W[i]; d = ext_euclid(W[i], m, x, y); while (y < 0) y += W[i]; a += y * (m * B[i] % n); } while (a < 0) a += n; return a % n; } */

    long long linear_modular_equation_system(long long B[], long long W[], long long k) { long long d, x, y, m, n = 1; long long a = 0; for (long long i = 0; i < k; i++) n *= W[i]; for (long long i = 0; i < k; i++) { m = n / W[i]; d = ext_euclid(W[i], m, x, y); a = (a + y*m*B[i]) % n; } if (a>0) return a; else return a + n; }

    void updateTree(long long node, long long a, long long b, long long i, long long j, long long value, long long modidx) { if (lazy[modidx][node] != 0) { tree[modidx][node] = (tree[modidx][node] + (long long)(b - a + 1) * lazy[modidx][node]) % MOD[modidx];

        if (a != b)
    {
        lazy[modidx][node * 2] = (lazy[modidx][node * 2] + lazy[modidx][node]) % MOD[modidx];
        lazy[modidx][node * 2 + 1] = (lazy[modidx][node * 2 + 1] + lazy[modidx][node]) % MOD[modidx];
    }

    lazy[modidx][node] = 0;
}

if (a > b || a > j || b < i) return;

if (a >= i && b <= j)
{
    tree[modidx][node] = (tree[modidx][node] + (long long)(b - a + 1) * value) % MOD[modidx];

    if (a != b)
    {
        lazy[modidx][node * 2] = (lazy[modidx][node * 2] + value) % MOD[modidx];
        lazy[modidx][node * 2 + 1] = (lazy[modidx][node * 2 + 1] + value) % MOD[modidx];
    }

    return;
}

updateTree(node * 2, a, (a + b) / 2, i, j, value, modidx);
updateTree(node * 2 + 1, (a + b) / 2 + 1, b, i, j, value, modidx);

tree[modidx][node] = (tree[modidx][node * 2] + tree[modidx][node * 2 + 1]) % MOD[modidx];

    }

    long long queryTree(long long node, long long a, long long b, long long i, long long j, long long modidx) { if (a > b || a > j || b < i) return 0;

    if (lazy[modidx][node] != 0)
{
    tree[modidx][node] = (tree[modidx][node] + (long long)(b - a + 1) * lazy[modidx][node]) % MOD[modidx];
    if (a != b)
    {
        lazy[modidx][node * 2] = (lazy[modidx][node * 2] + lazy[modidx][node]) % MOD[modidx];
        lazy[modidx][node * 2 + 1] = (lazy[modidx][node * 2 + 1] + lazy[modidx][node]) % MOD[modidx];
    }
    lazy[modidx][node] = 0;
}

if (a >= i && b <= j) return tree[modidx][node];

long long q1 = queryTree(node * 2, a, (a + b) / 2, i, j, modidx);
long long q2 = queryTree(node * 2 + 1, (a + b) / 2 + 1, b, i, j, modidx);
long long tmp = q1 + q2;
return tmp % MOD[modidx];

    }

    int ModExp(long long a, long long b, int mod) { a %= mod; long long c = 1, d = a; while (b) { if (b & 1) c = (c*d) % mod; d = (d*d) % mod; b >>= 1; } return (int)c; }

    int calc(long long a, long long b, int mod) { long long sum1 = ModExp(a, b, mod); long long sum2 = ModExp(a + 1, b, mod); long long sum3 = ModExp(b + 1, a, mod); return (sum1 + sum2 + sum3) % mod; }

    int binarySearchChild(int root, int st, int en) { int lo = 0, hi = (int)child[root].size(), mid = 0;

    while (lo < hi - 1)
{
    mid = (lo + hi) / 2;
    int st_mid = startTime[child[root][mid]];
    int en_mid = endTime[child[root][mid]];

    if (st >= st_mid && en <= en_mid) return mid;
    else if (en <= st_mid) hi = mid;
    else lo = mid + 1;
}
return lo;

    }

    int main() { init();

    int n;
scanf("%d", &n);
for (int i = 0; i < n - 1; i++)
{
    int x, y;
    scanf("%d%d", &x, &y);
    v[x].push_back(y);
    v[y].push_back(x);
}
dfs(1, 1);

int q;
scanf("%d", &q);
getchar();
while (q--)
{
    char ch;
    int r, t, m;
    long long a, b;
    ch = getchar();
    if (ch == 'U')
    {
        scanf("%d%d%lld%lld", &r, &t, &a, &b);
        getchar();

        int sr = startTime[r], er = endTime[r];
        int st = startTime[t], et = endTime[t];

        int val[NMOD];

        for (int i = 0; i < NMOD; i++)
            val[i] = calc(a, b, MOD[i]);

        if (sr == st && er == et)
        {
            for (int i = 0; i < NMOD; i++)
                updateTree(1, startTime[1], endTime[1], startTime[1], endTime[1], val[i], i);
        }
        else if (sr > st && er <= et)
        {
            for (int i = 0; i < NMOD; i++)
                updateTree(1, startTime[1], endTime[1], startTime[1], endTime[1], val[i], i);
            int childIdx = binarySearchChild(t, sr, er);
            for (int i = 0; i < NMOD; i++)
                updateTree(1, startTime[1], endTime[1], startTime[child[t][childIdx]], endTime[child[t][childIdx]], MOD[i] - val[i], i);
        }
        else
        {
            for (int i = 0; i < NMOD; i++)
                updateTree(1, startTime[1], endTime[1], st, et, val[i], i);
        }
    }
    else
    {
        scanf("%d%d%d", &r, &t, &m);
        getchar();

        if (m == 1)
        {
            printf("0\n");
            continue;
        }

        int sr = startTime[r], er = endTime[r];
        int st = startTime[t], et = endTime[t];

        int _m = m;

        long long W[6], B[6], k = 0;
        for (int i = 0; i < 26; i++)
        {
            int tmp = 1;
            bool flag = false;
            while (m % p[i] == 0)
            {
                flag = true;
                m /= p[i];
                tmp *= p[i];
            }
            if (flag)
                W[k++] = tmp;
        }

        if (sr == st && er == et)
        {
            for (int i = 0; i < k; i++)
                B[i] = queryTree(1, startTime[1], endTime[1], startTime[1], endTime[1], modidx[W[i]]) % W[i];
            printf("%lld\n", linear_modular_equation_system(B, W, k) % _m);
        }
        else if (sr > st && er <= et)
        {
            int childIdx = binarySearchChild(t, sr, er);
            for (int i = 0; i < k; i++)
            {
                long long tmp1 = queryTree(1, startTime[1], endTime[1], startTime[1], endTime[1], modidx[W[i]]) % W[i];
                long long tmp2 = queryTree(1, startTime[1], endTime[1], startTime[child[t][childIdx]], endTime[child[t][childIdx]], modidx[W[i]]) % W[i];
                B[i] = (tmp1 + W[i] - tmp2) % W[i];
            }
            printf("%lld\n", linear_modular_equation_system(B, W, k) % _m);
        }
        else
        {
            for (int i = 0; i < k; i++)
                B[i] = queryTree(1, startTime[1], endTime[1], st, et, modidx[W[i]]) % W[i];
            printf("%lld\n", linear_modular_equation_system(B, W, k) % _m);
        }
    }
}
return 0;

    }