343686875

I have used SPFA algo which is modification of Bellman-Ford algo, works in average O(n) worst O(n^2) and in cnt array if value > n it means it was part of the cycle

343688111

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define f(i, a, b) for (int i = a; i < b; i++)
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

void build(int ind, int lo, int hi, vector<int> &seg, vector<int> &a)
{
    if (lo == hi)
    {
        seg[ind] = a[lo];
        return;
    }
    int mid = lo + (hi - lo) / 2;
    build(2 * ind + 1, lo, mid, seg, a);
    build(2 * ind + 2, mid + 1, hi, seg, a);
    seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
}

void sumrangeupdate(vector<int> &seg, vector<int> &lazy, int ind, int lo, int hi, int l, int r)
{
    if (lazy[ind] != 0)
    {
        seg[ind] = (-seg[ind]);
        if (lo != hi)
        {
            lazy[2 * ind + 1] = 1 - lazy[2 * ind + 1];
            lazy[2 * ind + 2] = 1 - lazy[2 * ind + 2];
        }
        lazy[ind] = 0;
    }
    if (lo > r || hi < l || lo > hi)
        return;
    if (l <= lo && hi <= r)
    {
        seg[ind] = (-seg[ind]);
        if (lo != hi)
        {
            lazy[2 * ind + 1] = 1 - lazy[2 * ind + 1];
            lazy[2 * ind + 2] = 1 - lazy[2 * ind + 2];
        }
        return;
    }
    int mid = lo + (hi - lo) / 2;
    sumrangeupdate(seg, lazy, 2 * ind + 1, lo, mid, l, r);
    sumrangeupdate(seg, lazy, 2 * ind + 2, mid + 1, hi, l, r);
    seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
}

int querysumlazy(vector<int> &seg, vector<int> &lazy, int ind, int lo, int hi, int l, int r)
{
    if (lazy[ind] != 0)
    {
        seg[ind] = (-seg[ind]);
        if (lo != hi)
        {
            lazy[2 * ind + 1] = 1 - lazy[2 * ind + 1];
            lazy[2 * ind + 2] = 1 - lazy[2 * ind + 2];
        }
        lazy[ind] = 0;
    }
    if (lo > r || hi < l || lo > hi)
        return 0;
    if (l <= lo && hi <= r)
    {
        return seg[ind];
    }
    int mid = lo + (hi - lo) / 2;
    return querysumlazy(seg, lazy, 2 * ind + 1, lo, mid, l, r) + querysumlazy(seg, lazy, 2 * ind + 2, 1 + mid, hi, l, r);
}

void dfs(int node, int par, vector<int> g[], vector<int> &v, vector<int> &a, vector<int> &in, vector<int> &out, int &t)
{
    in[node] = t++;
    v.pb(a[node]);
    for (auto &child : g[node])
    {
        if (par == child)
            continue;
        dfs(child, node, g, v, a, in, out, t);
    }
    out[node] = t++;
    v.pb(a[node]);
}
void solve()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    vector<int> g[n];
    f(i, 0, n - 1)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].pb(v);
        g[v].pb(u);
    }
    vector<int> v;
    vector<int> in(n);
    vector<int> out(n);
    int t = 0;
    dfs(0, -1, g, v, a, in, out, t);
    vector<int> seg(8 * n);
    vector<int> lazy(8 * n, 0);
    build(0, 0, 2 * n - 1, seg, v);
    while (q--)
    {
        int type, a;
        cin >> type >> a;
        a--;
        if (type == 1)
        {
            cout << querysumlazy(seg, lazy, 0, 0, 2 * n - 1, in[a], out[a]) / 2 << endl;
        }
        else
        {
            sumrangeupdate(seg, lazy, 0, 0, 2 * n - 1, in[a], out[a]);
        }
    }
}
signed main()
{
    fastio

        int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

Dp Approach 343695682

Matrix Exponentiation 343707696

Other Approaches:-

Binary Exponentiation type DP approach. 343113871

Maths approach. 343091287

Count of elements from $$$a+1$$$ to $$$b$$$ divisible by $$$k$$$

= Count of elements from $$$1$$$ to $$$b$$$ divisible by $$$k$$$ — Count of elements from $$$1$$$ to $$$a$$$ divisible by $$$k$$$

= $$$\lfloor b/k \rfloor - \lfloor a/k \rfloor$$$.

Does Modular Division work like arithmetic division, even when $$$a$$$ is not exactly divisible by $$$k$$$? No, it doesn't.

Let us consider the problem simply without the constraints first. Let us assume $$$a$$$ and $$$b$$$ are both give in integer form.

Count of elements from $$$a+1$$$ to $$$b$$$ divisible by $$$k$$$

= Count of elements from $$$1$$$ to $$$b$$$ divisible by $$$k$$$ — Count of elements from $$$1$$$ to $$$a$$$ divisible by $$$k$$$

= $$$\lfloor b/k \rfloor - \lfloor a/k \rfloor$$$.

Our entire solution focusses on implementing this formula for very large numbers.

As the numbers are very big, it is not possible to directly implement this formula. We need the answer mod $$$6991$$$. Using modular arithmetic the equation can be changed to

$$$((b\pmod{6991}*k^{-1}) - (a\pmod{6991}*k^{-1}) + (6991)) \mod{6991}$$$ where $$$k^{-1}$$$ is the modular multiplicative inverse of $$$k$$$ wrt $$$6991$$$.

To efficiently compute $$$b\pmod{6991}$$$ and $$$a\pmod{6991}$$$ we will use the following way:

1. Start with number $$$0$$$.

2. For every new digit, compute number = number * base + digit.

3. Take remainder at each step.

This gives us our required modulus result irrespective of the base of the number.

Our implementation has a problem however. Modular division does not work like arithmetic division. Eg: $$$(44/2)$$$ mod $$$6991$$$ = $$$22$$$, but $$$(45/2)$$$ mod $$$6991$$$ = $$$3518$$$. We need to ensure floor at both computations.

Thus our modified equation becomes:

$$$((b - (b \mod k))/k) - ((a - (a \mod k))/k)$$$ .

Using modular arithmetic the required answer is:

$$$T1 = ((b\pmod{6991}-b\pmod{k}+6991) * k^{-1}) \mod{6991}$$$

$$$T2 = ((a\pmod{6991}-a\pmod{k}+6991) * k^{-1}) \mod{6991}$$$

$$$Ans = (T1 - T2 + 6991) \mod 6991$$$

#include<bits/stdc++.h>
using namespace std;
 #define int long
 const int MOD = 6991;
 long long exp(long long x, long long n, long long m) {
     x %= m;
     long long res = 1;
     while (n > 0) {
         if (n % 2 == 1) { res = res * x % m; }
         x = x * x % m;
         n /= 2;}
     return res;}
  long long fun(string &a, int m, int base){
    int res=0;
    for(int i=0;i<a.size();i++){
      res = (res*base + int(a[i]-'0'))%m;}
      return res%m;}
 signed main() {
     ios_base::sync_with_stdio(false); 
     cin.tie(NULL);
     cout.tie(NULL);
     int t;
     cin>>t;
     while(t--){
     int a1,b1,k;
     cin>>a1>>b1>>k;
     string a,b;
     cin>>a>>b;
     int k_inv = exp(k, MOD-2, MOD);
     int term1 = (((fun(a,MOD,2) - fun(a,k,2) + MOD)%MOD) * (k_inv%MOD))%MOD;
     int term2 = (((fun(b,MOD,10) - fun(b,k,10) + MOD)%MOD) * (k_inv%MOD))%MOD;
     int res = (term2 - term1 + MOD)%MOD;
     cout<<res<<endl;}
     return 0;}

Can we use a DFS based approach to count the number of violations?

Can we use Small to Large Merging to optimize our solution?

To solve this problem efficiently, we can leverage appropriate data structures to store the Binary Tree and perform operations on it. Here's a step-by-step approach:

1. DFS for Counting Violations: We can use Depth-First Search (DFS) to count the number of nodes that violate the BST properties in each subtree. To check each node's validity in the BST, we compare its value with the maximum and minimum permissible values for that node as we move from the root down to the leaves.

2. Complexity Analysis: This approach allows us to check the entire tree in $$$O(N)$$$ time, where $$$N$$$ is the number of nodes, because each node is visited only once. At each node, we compare its value with the maximum and minimum bounds passed from its parent, updating these bounds as we recurse deeper.

3. Tracking Violating Nodes in Order: We can use sets to keep track of nodes that violate the BST property, storing them in ascending order by node number. To efficiently merge these sets as we move up the tree, we can use a technique called small to large merging.

4. Small to Large Merging Strategy: Starting from the leaf nodes and moving up toward the root in DFS, we store query nodes in the required order (ascending by node number within each query). For each query, the required nodes are stored, allowing us to merge the child node sets with their respective parent sets efficiently.

This approach provides an efficient solution that respects the problem's constraints, ensuring that the operations required per query are minimized through effective data structure usage and ordered processing.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
 
vector<pair<int, char>> tree[MAXN];
int node_values[MAXN];
int violations_count[MAXN];
set<int> violations_set[MAXN];
set<int> query_nodes;
int level[MAXN];
vector<int> queries[MAXN];
vector<int> query_nodes_vec;
vector<int> result[MAXN];
bool is_violated[MAXN];
map<int, set<int>> violations;
 
void dfs(int node, int parent, int min_val, int max_val, int lvl) {
    level[node] = lvl;
    if (!(min_val < node_values[node] && node_values[node] < max_val)) {
        is_violated[node] = true;
        violations_set[node].insert(node);
        violations_count[node] = 1;
    } else {
        violations_count[node] = 0;
    }
    for (auto &[child, direction] : tree[node]) {
        if (child == parent) continue;
        if (direction == 'l') {
            dfs(child, node, min_val, min(max_val, node_values[node]), lvl + 1);
        } else {
            dfs(child, node, max(min_val, node_values[node]), max_val, lvl + 1);
        }
         if (violations_set[child].size() > violations_set[node].size()) {
            swap(violations_set[node], violations_set[child]);
        }
        violations_set[node].insert(violations_set[child].begin(), violations_set[child].end());
        violations_count[node] += violations_count[child];
    }
    if (query_nodes.find(node) != query_nodes.end()) {
        violations[node] = violations_set[node];
    }
}
 
int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> node_values[i];
    }
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        char dir;
        cin >> u >> v >> dir;
        u--; v--;
        tree[u].emplace_back(v, dir);
        tree[v].emplace_back(u, dir);
    }
    int Q;
    cin>>Q;
    for (int i = 0; i < Q; i++) {
        int x; cin>>x; x--;
        query_nodes.insert(x);
        query_nodes_vec.push_back(x);
    }
    dfs(0, -1, INT_MIN, INT_MAX, 0);
 
    for(auto node:query_nodes_vec){
        cout<<node+1<<" ";
        if (violations[node].empty()) {
            cout << -1;
        } else {
            for (int v : violations[node]) {
                cout << v + 1 << " ";
            }
        }
        cout<<endl;
    }
 
    for (int i = 0; i < N; i++) {
        cout << violations_count[i]<< " ";
    }
    cout << endl;
    return 0;
}

Try using ordered set with difference array approach.

For every element $$$a_i$$$ try to find the number of elements bigger than it on the right side of the array and the number of elements smaller than it on the left side of the array.

#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key
#define endl            "\n"
#define int long long
int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;cin>>n;
    vector<int> a(n+1,0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int q;cin>>q;
    map<int,int> diff;
    pbds start,end;
    for(int i=1;i<=n;i++){
        int now=start.order_of_key(make_pair(a[i],i));
        diff[a[i]+1]-=now;
        start.insert(make_pair(a[i],i));
    }
    for(int i=n;i>=1;i--){
        int now=end.order_of_key(make_pair(a[i],i));
        int val=((int)end.size())-now;
        diff[a[i]]+=val;
        end.insert(make_pair(a[i],i));
    }
    auto it=diff.begin();
    it++;
    auto it1=diff.begin();
    for(;it!=diff.end();it++){
        it->second+=it1->second;
        it1=it;
    }
    while(q--){
        int x;cin>>x;
        auto it2=diff.upper_bound(x);
        if(it2==diff.begin()){
            cout<<0<<endl;
            continue;
        }
        else{
            it2--;
            cout<<(it2->second)<<endl;
        }
    }
    return 0;
}