ABC350题解（E-G）

E

直接搜一下 \(N\) 的可能到达的值的个数，发现不多（大约 \(10^4\) 个），直接暴力 dp（记忆化搜索）。

转移式 \(f_i=\max(X \log_{A}N,\dfrac{\sum\limits_{j=1}^6f_{i/j}}{6}+Y)\)。

化简得到 \(f_i=\max(X \log_{A}N,\dfrac{\left(\sum\limits_{j=2}^6f_{i/j}\right)+6Y}{5})\)。

F

文艺平衡树直接区间翻转 \(O(n\log n)\)，然后大小写离线下来扫一遍就行了，总复杂度 \(O(n\log n)\)。

G

lct 板子题。

\(1\ u\ v\) 操作即 lct 的 link(u,v)。

\(2\ u\ v\) 操作考虑先 makeroot(u) 把 \(u\) 放到根节点，然后 access(v)，然后 \(v\) 向上跳两步（找父亲即 splay 的获得前驱操作）看一下是不是 \(u\) 就行了。

代码

E

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

#define int ll

set<int> s;
map<int, int> pos, val;
void dfs(int x)
{
    if(!x || s.count(x)) return;
    s.insert(x);
    for(int i = 2; i <= 6; i ++) dfs(x / i);
}

const int N = 1e5;
long double f[N];
int n, a, x, y;

int logA(int x)
{
    int ans = 1; __int128 r = 1;
    while(r <= x) ans ++, r *= a;
    return ans - 1;
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> a >> x >> y;
    dfs(n);
    int c = 0;
    for(int i : s) c ++, pos[i] = c, val[c] = i;
    pos[0] = 0;
    for(int i = 1; i <= c; i ++)
    {
        long double s = 0;
        for(int j = 2; j <= 6; j ++)
            s += f[pos[val[i] / j]] / 6;
        f[i] = min(1.L * x * logA(val[i]), (s + y) * 6.L / 5.L);
        // cerr << i << " " << val[i] << " " << f[i] << endl;
    }
    printf("%.15Lf", f[c]);

    return 0;
}

F

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

const int N = 5e5 + 5;

struct node
{
    int v, tag, sz;
    node *s[2], *p;
    void init(node *_p, int _v)
    {
        sz = 1, v = _v, p = _p;
    }
    void swp() {swap(s[0], s[1]);}
    void pd()
    {
        if(!tag) return;
        swp();
        if(s[0]) s[0]->tag ^= 1;
        if(s[1]) s[1]->tag ^= 1;
        tag = 0;
    }
    void pu() {sz = (s[0] ? s[0]->sz : 0) + (s[1] ? s[1]->sz : 0) + 1;}
}a[N], *root;

int idx = 0;

void rotate(node *x)
{
    if(x->p == NULL) return;
    node *y = x->p, *z = y->p;
    int k = y->s[1] == x;
    x->p = z;
    if(z) z->s[z->s[1] == y] = x;
    y->s[k] = x->s[k ^ 1];
    if(x->s[k ^ 1]) x->s[k ^ 1]->p = y;
    y->p = x, x->s[k ^ 1] = y;
    y->pu();x->pu();
}

void pushd(node *x) {if(x == NULL) return; pushd(x->p); x->pd();}

void splay(node *x, node *k)
{
    if(x == NULL) assert(a[0].p->v);
    pushd(x);
    while(x->p != k)
    {
        node *y = x->p, *z = y->p;
        if(z != k)
            if((y->s[1] == x) ^ (z->s[1] == y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if(k == NULL) root = x;
}

node* find(int x)
{
    node *u = root;
    while(u != NULL)
    {
        u->pd();
        if(u->s[0] && u->s[0]->sz >= x) u = u->s[0];
        else if((u->s[0] ? u->s[0]->sz : 0) + 1 == x) return splay(u, NULL), u;
        else x -= (u->s[0] ? u->s[0]->sz : 0) + 1, u = u->s[1];
    }
    return NULL;
}

void rev(int l, int r)
{
    node *xl = find(l), *xr = find(r + 2); // [l + 1, r + 1]
    splay(xl, NULL);splay(xr, xl);
    xr->s[0]->tag ^= 1;
    splay(xr->s[0], NULL);
}

node* insert(node *x, int v)
{
    splay(x, NULL);
    x->s[1] = &a[++idx];
    a[idx].init(x, v);
    splay(&a[idx], NULL);
    return &a[idx];
}

int n, ans[N], nown;

void print(node *x)
{
    if(x == NULL) return;
    x->pd();
    print(x->s[0]);
    if(x->v) nown ++, ans[nown] = x->v;
    print(x->s[1]);
}

string s;
vector<pair<int, int>> pr;

void read()
{
    string s0; cin >> s0;
    stack<int> stk;
    int nowu = 0;
    for(char c : s0)
    {
        if(c == '(')
        {
            nowu ^= 1;
            stk.push(s.size() + 1);
        }
        else if(c == ')')
        {
            nowu ^= 1;
            pr.push_back({stk.top(), (int)s.size()});
            stk.pop();
        }
        else
        {
            if(nowu)
            {
                if(c >= 'A' && c <= 'Z') s += (c - 'A' + 'a');
                else s += (c - 'a' + 'A');
            }
            else s += c;
        }
    }
    n = s.size();
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    read();
    idx = 1;a[1].init(NULL, 0);root = &a[1];
    node* lst = &a[1];
    for(int i = 1; i <= n; i ++)
        lst = insert(lst, i);
    insert(lst, 0);
    for(auto o : pr)
    {
        int l = o.first, r = o.second;
        if(l > r) continue;
        rev(l, r);
    }
    print(root);
    for(int i = 1; i <= n; i ++)
    {
        cout << s[ans[i] - 1];
    }

    return 0;
}

G

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

#define int ll

const int N = 1e5 + 5;
struct node {int p, s[2], v, w, tg;} a[N];

bool isr(int x) {return a[a[x].p].s[0] != x && a[a[x].p].s[1] != x;}

void pu(int x) {a[x].w = a[a[x].s[0]].w ^ a[a[x].s[1]].w ^ a[x].v;} // v, w

void pd(int x) {if(a[x].tg) {swap(a[x].s[0], a[x].s[1]); if(a[x].s[0]) a[a[x].s[0]].tg ^= 1; if(a[x].s[1]) a[a[x].s[1]].tg ^= 1; a[x].tg = 0;}}

void pdp(int x) {if(!isr(x)) pdp(a[x].p); pd(x);}

void rotate(int x)
{
    int y = a[x].p, z = a[y].p;
    int k = a[y].s[1] == x;
    if(!isr(y)) a[z].s[a[z].s[1] == y] = x;
    a[x].p = z;
    a[y].s[k] = a[x].s[k ^ 1], a[a[x].s[k ^ 1]].p = y;
    a[x].s[k ^ 1] = y, a[y].p = x;
    pu(y); pu(x);
}

void splay(int x)
{
    pdp(x);
    while(!isr(x))
    {
        int y = a[x].p, z = a[y].p;
        if(!isr(y))
            if((a[z].s[1] == y) ^ (a[y].s[1] == x)) rotate(x);
            else rotate(y);
        rotate(x);
    }
}

int pre(int x)
{
    splay(x); pd(x);
    if(!a[x].s[0]) return 0;
    int u = a[x].s[0];
    while(pd(u), a[u].s[1]) u = a[u].s[1];
    splay(u); return u;
}

void access(int x)
{
    int lst = 0;
    while(x) splay(x), a[x].s[1] = lst, pu(x), lst = x, x = a[x].p;
}

void mkrt(int x) {access(x); splay(x); a[x].tg ^= 1;}

int findrt(int x) {access(x); splay(x); while(pd(x), a[x].s[0]) x = a[x].s[0]; return splay(x), x;} // pushdown

void link(int x, int y) {mkrt(x); if(findrt(y) == x) return; a[x].p = y;}

int getf(int x)
{
    access(x);
    return pre(x);
}

int qry(int x, int y) {mkrt(x); access(y); splay(x); return a[x].w;}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n, q; cin >> n >> q;
    int lans = 0;
    while(q --)
    {
        int op, x, y; cin >> op >> x >> y;
        op = 1 + ((op * (1 + lans) % 998244353) % 2);
        x = 1 + ((x * (1 + lans) % 998244353) % n);
        y = 1 + ((y * (1 + lans) % 998244353) % n);
        if(op == 1)
        {
            link(x, y);
        }
        else
        {
            mkrt(x);
            if(findrt(y) != x) {lans = 0; cout << 0 << "\n";}
            else
            {
                int fy = getf(y);
                if(!fy) {lans = 0; cout << 0 << "\n";}
                else
                {
                    int ffy = getf(fy);
                    if(ffy != x) {lans = 0; cout << 0 << "\n";}
                    else lans = fy, cout << fy << "\n";
                }
            }
        }
    }

    return 0;
}

后记

好像 F 做法有点唐。。这下成暴力大师了。。