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

Sort by

recency

|

8 Discussions

|

  • 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;

    }

  • DamiNoel
     + 0 comments

    Your code is very clean and easy to understand. wazifa for husband to come back

  • phibrain
     + 1 comment

    I got 150 using 26 data structures, each of them got the update value in O(1) because of the constraint (m<=101), you can generate all posible remainders to each of the posibles values of m, and then you find the period in no more than m^2 . But when you read the editorial, they use binpow to get all the updates that cost a lot, but they solve the problem with just 5 data structures... nice problem!

  • SANJAY_GOLCHHA
     + 0 comments

    how to handle such very big numbers stuck on this half passed rest test cases failed can anybody explain me how to handle such big numbers even unsigned long long int is not suitable for this ?

  • sharma_avneesh78
     + 0 comments

    For Big Numbers ((10^18)^(10^18)), try considering the constraint on m (m <= 101).