given an array $$$a$$$ of length $$$n$$$, you have to answer $$$m$$$ queries:

• decrease the numbers greater than $$$x$$$ by $$$x$$$ in the interval $$$[l,r]$$$
• count the occurrence of $$$x$$$ in the interval $$$[l, r]$$$

i have no progress so far.

i wanted to vc EGOI with FZ_Laabidi (totally needed to include this here) and couldn't find any OJ that have it although the testcases are public, are y'all aware of any OJ that have them?

all i could've find is oj.uz which only have 2024, thanks in advance!

i was tackling C. Experience the other day and had a "clever" idea (well it's perhaps the intended but whatever) to support all the queries mentioned in the problem in $$$O(\alpha(n))$$$, using both union by size/rank and path compression, i thought it was nice and didn't see it documented elsewhere so here it is, the idea is to basically notice that if we merge two teams (with union by size/rank ofc), we can set the experience of the child representative node to that of it self minus of it's parent representative experience, so basically:

now if we want the experience of B, we can traverse the tree up and sum, so $$$x-y+y = x$$$ and if we at some point added some value m to A, we'll have B equal x + A, and when path compression we'll just add experience of the recursion, let's describe what each dsu part will do:

sunion(a, b): regular union by size, but we set experience of the children representative to itself minus of it's parent

void sunion(int a, int b) {
  a = find(a);
  b = find(b);
  if(a == b) return;
  if(size[a] > size[b]) {
    parents[b] = a;
    size[a] += size[b];
    exp[b] -= exp[a];
  }
  
  else {
    parents[a] = b;
    size[b] += size[a];
    exp[a] -= exp[a];
  }
}

find(v): regular path compression, we go up the tree and move the link, but we add a twist that for each move up we sum the experience, code: (**incorrect code but the idea is there, can anyone help me figure out what's wrong? i spent two days on this :sob:**)

pair<int, int> find_backend(int v) {
  if(v == parents[v]) return {v, exp[v]};
  else {
    parents[v] = find_backend(parents[v]).first;
    exp[v] += find_backend(parents[v]).second;
    return {parents[v], exp[v]};
  }
}

int find(int v) {
  return find_backend(v).first;
}

get_exp(v): and add_exp(v, m) both trivial

int get_exp(int v) {
  return find_backend(v).second;
}

void add_exp(int v, int m) {
  exp[find(v)] += m; 
}

and yes that's it, we solved the problem in $$$O(\alpha(n))$$$! very cleanly, very nicely! i'd really appreciate some debugging help to make the code correct, sorry for my lack of implementation skills!

i was trying to solve this cool cses problem the other minute and i stumbled across a problem relating modulo: im pretty sure there is nothing wrong with my usage of spoiler dirichlet's hyperbola method, basically what i did was computing the first two sums modulo M then subtracting the last chunk modulo then modulo the actual result applying the rule (a mod m) — (b mod m) mod m = (a — b mod m), but there is a case when b mod m is just greater than a mod m and not b > a, i don't know what to do! can anyone please correct my usage of modulo! thanks in advance :3

#include <bits/stdc++.h>

using namespace std;
#define int unsigned long long

int G(int n) {
  return n*(n+1)/2;
}

signed main() {
  int n; cin >> n;
  int res = 0, MOD = 1e9 + 7, t = (int)sqrt(n);
  for(int i = 1; i <= t ; i++) {
    res += G(n/i)%MOD;
    res += (i * (n/i))%MOD;
    res %= MOD;
  }

  res -= (G(t)*t)%MOD;
  res %= MOD;
  cout << res;
}