2022-9-13总结

tree

考虑怎么询问一个点 $x$ 的编号最大的祖先，可以先把树拍到 dfs 序上，用每个节点的编号在它的子树里取 $\max$，然后查询 $dfn[x]$ 处的 $\max$ 值即为 $x$ 的编号最大的祖先。

而这时我们还需要保证取到的 $\max$ 值在另一棵树上是 $y$ 的祖先，我们可以只把 $y$ 的祖先插入到线段树中，这样询问出来的就一定是 $y$ 的祖先了。

直接暴力插入不太行，因为这题不带修，我们可以用主席树维护 $y$ 到根的路径构成的线段树，时间复杂度 $O((n+m) \log n)$。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

const int N = 100005;

namespace HJT_tree {
    struct node {
        int ls, rs, max;
    } a[N*32];
    int root[N], lim, node_cnt;
    void modify(int &i, int ql, int qr, int val, int l = 1, int r = lim);
    int query(int i, int pos, int l = 1, int r = lim);
}
using namespace HJT_tree;


int n, m;
int ldfn[N], rdfn[N], dft;
vector<int> ver1[N], ver2[N];

void euler_tour(int x);
void dfs(int x, int fa);


int main()
{
    cin >> n >> m;
    for(int i = 2; i <= n; i++)
    {
        int f; cin >> f;
        ver1[f].push_back(i);
    }
    for(int i = 2; i <= n; i++)
    {
        int f; cin >> f;
        ver2[f].push_back(i);
    }
    HJT_tree::lim = n*2;
    euler_tour(1);
    dfs(1, 0);
    
    int lastans = 0;
    for(int i = 1; i <= m; i++)
    {
        int x, y; cin >> x >> y;
        x = (x+lastans)%n+1;
        y = (y+lastans)%n+1;
        lastans = HJT_tree::query(root[x], ldfn[y]);
        cout << lastans << "\n";
    }
}

void euler_tour(int x)
{
    ldfn[x] = ++dft;
    for(auto y : ver2[x])
        euler_tour(y);
    rdfn[x] = ++dft;
}
void dfs(int x, int fa)
{
    root[x] = root[fa];
    HJT_tree::modify(root[x], ldfn[x], rdfn[x], x);
    for(auto y : ver1[x]) dfs(y, x);
}

namespace HJT_tree {
    #define ls(i) a[i].ls
    #define rs(i) a[i].rs
    #define lmid ((l+r)>>1)
    #define rmid ((l+r+2)>>1)
    void modify(int &i, int ql, int qr, int val, int l, int r)
    {
        a[++node_cnt] = a[i]; i = node_cnt;
        if(ql <= l and r <= qr)
        {
            a[i].max = max(a[i].max, val);
            return void();
        }
        if(ql <= lmid) modify(ls(i), ql, qr, val, l, lmid);
        if(qr >= rmid) modify(rs(i), ql, qr, val, rmid, r);
    }
    int query(int i, int pos, int l, int r)
    {
        if(l == r) return a[i].max; int ans = a[i].max;
        if(pos <= lmid) ans = max(ans, query(ls(i), pos, l, lmid));
        if(pos >= rmid) ans = max(ans, query(rs(i), pos, rmid, r));
        return ans;
    }
}

Simple Math 3

如果区间长度 $len \ge D$ 的话肯定不满足条件，所以 $i$ 就有一个枚举上界： $\frac{D-1}{C-B}$，将其设为 $n$

现在保证了区间长度 $len < D$，如果区间中有一个 $D$ 的倍数，那么 $\left\lfloor \frac{A+C_i}{D} \right\rfloor - \left\lfloor \frac{A+B_i-1}{D} \right\rfloor = 1$，否则这个值为 $0$。

考虑去除不合法的答案: $n - \sum_{i=1}^{n}\left( \left\lfloor \frac{A+C_i}{D} \right\rfloor - \left\lfloor \frac{A+B_i-1}{D} \right\rfloor \right)$。

直接类欧几里得解决即可， 时间复杂度 $O(T \log n)$。

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;

ll solve(ll a, ll b, ll c, ll n)
{
    if(a == 0)
        return (b/c)*(n+1);
    if(a >= c or b >= c)
        return n*(n+1)/2*(a/c) + (n+1)*(b/c) + solve(a%c, b%c, c, n);
    else
    {
        ll m = (a*n+b)/c;
        return n*m - solve(c, c-b-1, a, m-1);
    }
}


int main()
{
    int t; cin >> t;
    while(t --> 0)
    {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        ll m = (d-1)/(c-b);
        ll ans = m - solve(c, a, d, m) + solve(b, a-1, d, m);
        cout << ans << endl;
    }
}

Robots and Exits

因为只有机器人离开时的出口不同时方案才算不同，所以我们考虑一个机器人在哪个出口出去。

直接做的话不好做，考虑一个机器人到左边第一个出口的距离为 $l$, 到右边第一个出口的距离为 $r$，我们把一个机器人看成一个坐标为 $(l,r)$ 的点，将其放在坐标系上。

我们画一条 $x=k$ 的线，就会使所有的 $l \le k$ 的点从它左边的出口出去，画一条 $y=k$ 的线就会使所有 $r \le k$ 的点从它右边的出口出去。

将所有机器人分配一个出口的方案对应在坐标系上就是一条只能往右或往上的折线，而我们求的就是一条折线划分点集的方案数。

为了保证方案不重，我们只考虑紧贴点的折线就行。

这个可以用树状数组优化DP解决。

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;
const int N = 200005;
const int P = 1e9+7;

namespace bit {
    #define lowbit(x) (x&-x)
    ll a[N]; int lim;
    void add(int x, ll val);
    ll query(int x);
}

struct node {
    int x, y;
};

int n, m, cnt;
ll pos[N], quit[N];
ll lsh[N], lcnt;
node rob[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> pos[i];
    for(int i = 1; i <= m; i++)
        cin >> quit[i];
    
    for(int i = 1; i <= n; i++)
    {
        int p = lower_bound(quit+1, quit+m+1, pos[i])-quit;
        if(p == 1 or p == m+1) continue;
        cnt++;
        rob[cnt].x = pos[i]-quit[p-1];
        rob[cnt].y = quit[p]-pos[i];
        lsh[cnt] = rob[cnt].y;
    }
    
    sort(rob+1, rob+cnt+1, [](node a, node b){
        if(a.x != b.x)
            return a.x < b.x;
        else
            return a.y > b.y;
    });
    
    sort(lsh+1, lsh+cnt+1);
    lcnt = unique(lsh+1, lsh+cnt+1)-lsh-1;
    for(int i = 1; i <= cnt; i++)
        rob[i].y = lower_bound(lsh+1, lsh+lcnt+1, rob[i].y)-lsh;
    
    bit::lim = lcnt+1;
    bit::add(0, 1);
    for(int i = 1; i <= cnt; i++)
    {
        if(rob[i].x == rob[i-1].x and rob[i].y == rob[i-1].y) continue;
        bit::add(rob[i].y, bit::query(rob[i].y-1));
    }
    
    cout << bit::query(lcnt) << endl;
}

namespace bit {
    void add(int x, ll val)
    {
        for(x += 1; x <= lim; x += lowbit(x))
            (a[x] += val) %= P;
    }
    ll query(int x)
    {
        ll ans = 0;
        for(x += 1; x >= 1; x -= lowbit(x))
            (ans += a[x]) %= P;
        return ans;
    }
}