mxh带窝打多校之Contest 4

OI mxh带窝飞

约定

题意

1006 Test for Rikka

对于给定的$K$，请构造$N, M$和$N\times N$的$01$矩阵$A$，使得$(A^M)_{1,N}=K$。

1007 Undirected Graph

给出一个无向图$G=\{V,E\}$，每次询问给出$l,r$，询问若只保留端点都在$[l,r]$内的边，图中有多少个连通块。

1012 ZZX and Permutations

给定一个置换$p$的一种表示$a$，求字典序最大的原置换。

题解

1006 Test for Rikka

按照$01$矩阵来做显然是十分苦难的，不妨以图的邻接矩阵来考虑问题。
问题转化成构造一个$N, M$与无重边有向图$G=\{V, E\}$使得节点$1$到节点$N$走$M$步的方案数为$K$。

我们考虑完全图（含自环）有非常适合本题的性质：$c$个点的完全图上任意一点走$i$步的方案数是$c^i$。
我们在完全图下准备一条链一直连到终点，这样我们可以控制可以$i$步走到终点的点数。

令$c=10$就可以在限制内构造出来了。

# include <cstdio>
# define REP(i, n) for (int i = 1; i <= n; i ++)
bool g[100][100];
int q0, a[100];
long long K;
int main ()
{
    for (scanf ("%d", &q0); q0; q0 --)
    {
        scanf ("%I64d", &K);
        if (!K) {printf ("1 1\n0\n"); continue;}
        int len = 0;
        while (K) a[++ len] = K % 10, K /= 10;
        int n = 10 + len + 1, m = len + 2;
        REP (i, n) REP (j, n) g[i][j] = (i <= 10 && j <= 10);
        REP (i, len) {REP (j, a[i]) g[j][10 + i] = 1; g[10 + i][11 + i] = 1;}
        printf ("%d %d\n", n, m);
        REP (i, n) {REP (j, n) putchar ('0' + g[i][j]); putchar ('\n');}
    }
    return 0;
}

1007 Undirected Graph

……很老旧的LCT思路…………
令每条边为$(x,y)(x<y)$。
考虑扫描线，每加一条边，替换掉环上$x$最小的边。
在线段树上更新答案即可。
时间复杂度$O(N\log N)$。

# include <cstdio>
# include <iostream>
# include <algorithm>
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0N(i, n) for (int i = 0; i <= n; i ++)
# define FOR(i, a, b) for (int i = a; i <= b; i ++)
using namespace std;
const int NR = 401000;
# define u t[x]
# define o t[y]
# define lc ch[0]
# define rc ch[1]
# define tc ch[ty]
# define vc ch[!ty]
# define ulfc t[u.lc]
# define urtc t[u.rc]
struct Lct {int ch[2], par, min, val; bool rev; void Rev () {rev ^= 1, swap (lc, rc);} void Set (int q) {min = val = q;}} t[NR];
struct Arr {int l, r, id;} q[NR], g[NR];
int n, m, q0, den[NR], ans[NR], dsz;
bool Cmp (Arr a, Arr b) {if (a.r != b.r) return a.r < b.r; return a.l < b.l;}
namespace Se
{
    struct Seg {int ch[2], tag; inline void Add (int d) {tag += d;}} t[NR << 2];
    int sz;
    inline void PD (int x) {if (!x || !u.tag) return ; ulfc.Add (u.tag), urtc.Add (u.tag), u.tag = 0;}
    void Build (int x, int l, int r) 
    {
        u.tag = 0;
        if (l == r) return ;
        int mid = (l + r) >> 1;
        Build (u.lc = ++ sz, l, mid), Build (u.rc = ++ sz, mid + 1, r);
    }
    void SegInc (int x, int l, int r, int il, int ir)
    {
        if (il <= l && r <= ir) {u.Add (1); return ;}
        PD (x); int mid = (l + r) >> 1;
        if (il <= mid) SegInc (u.lc, l, mid, il, ir); 
        if (ir > mid) SegInc (u.rc, mid + 1, r, il, ir);
    }
    int SegVal (int x, int l, int r, int p)
    {
        if (l == r) return u.tag;
        PD (x); int mid = (l + r) >> 1;
        if (p <= mid) return SegVal (u.lc, l, mid, p);
        return SegVal (u.rc, mid + 1, r, p);
    }
    inline void Inc (int l, int r) {SegInc (1, 1, n, l, r);}
    inline int Val (int p) {return SegVal (1, 1, n, p);}
}
# define p u.par
inline void PD (int x)
{
    if (!x || !u.rev) return ;
    if (u.lc) ulfc.Rev (); if (u.rc) urtc.Rev (); u.rev = 0;
}
inline void Upd (int x)
{
    u.min = u.val;
    if (g[ulfc.min].l < g[u.min].l) u.min = ulfc.min;
    if (g[urtc.min].l < g[u.min].l) u.min = urtc.min;
}
inline int sgn (int x) {return t[p].rc == x ? 1 : t[p].lc == x ? 0 : -1;}
inline void sc (int x, int y, bool ty) {u.tc = y, o.par = x;}
inline void Fix (int x) {if (~ sgn (x)) Fix (p); PD (x);}
inline void Rot (int x, bool ty) 
{
    int y = p, z = o.par;
    if (~ sgn (y)) sc (z, x, sgn (y)); else p = z;
    sc (y, u.vc, ty), sc (x, y, !ty), Upd (y), Upd (x);
}
int Splay (int x)
{
    Fix (x); int t0, t1, y;
    while (~ (t0 = sgn (x)))
    {
        if (~ (t1 = sgn (y = p))) Rot (t0 ^ t1 ? x : y, t0), Rot (x, t1);
        else Rot (x, t0);
    }
    return Upd (x), x;
}
inline int Acs (int tx) {for (int x = tx, y = 0; x; Upd (y = x), x = p) Splay (x), u.rc = y; return Splay (tx);}
# define us t[Acs (x)]
inline int gf (int x) {for (Acs (x); PD (x), u.lc; x = u.lc); return x;}
inline void Evt (int x) {us.Rev ();}
inline void Link (int x, int y) {Evt (x), p = y;}
inline void Cut (int x) {t[us.lc].par = 0, u.lc = 0;}
inline void Cut (int x, int y) {Evt (x), Cut (y);}
inline int Min (int x, int y) {return Evt (y), us.min;}
int main ()
{
    g[0].l = 1 << 30;
    while (scanf ("%d%d%d", &n, &m, &q0) != EOF)
    {
        Se::Build (Se::sz = 1, 1, n);
        dsz = n;
        REP_0N (x, n + m) u.lc = u.rc = u.par = u.rev = u.val = u.min = 0; 
        REP (i, m) 
        {
            scanf ("%d%d", &g[i].l, &g[i].r);
            if (g[i].l > g[i].r) swap (g[i].l, g[i].r);
        }
        REP (i, q0) scanf ("%d%d", &q[i].l, &q[i].r), q[i].id = i;
        sort (g + 1, g + m + 1, Cmp);
        sort (q + 1, q + q0 + 1, Cmp);
        int qi = 1; g[m + 1].r = g[0].r = -1;
        REP (i, m)
        {
            if (g[i].r != g[i - 1].r)
                while (qi <= q0 && q[qi].r < g[i].r)
                    ans[q[qi].id] = n - Se::Val (q[qi].l), qi ++;
            if (gf (g[i].l) != gf (g[i].r))
            {
                t[den[i] = ++ dsz].Set (i), Link (den[i], g[i].l), Link (den[i], g[i].r); 
                Se::Inc (1, g[i].l);
            }
            else
            {
                int d = Min (g[i].l, g[i].r);
                if (g[d].l < g[i].l)
                {
                    den[i] = den[d];
                    Cut (den[d], g[d].l), Cut (den[d], g[d].r);
                    t[den[i]].Set (i);
                    Link (den[i], g[i].l), Link (den[i], g[i].r);
                    Se::Inc (g[d].l + 1, g[i].l);
                }
            }
        }
        while (qi <= q0) ans[q[qi].id] = n - Se::Val (q[qi].l), qi ++;
        REP (i, q0) printf ("%d\n", ans[i]);
    }
    return 0;
}

1012 ZZX and Permutations

考虑贪心地定原置换$p$每一个位置的值。
位置$i$在环中的下一个元素即为$p_i$。
有两种情况，$i$是环的最后一个元素或其他元素。
若是最后一个元素，那么第一个值应该在前面。
否则应该是在$a$中的下一个元素。
注意到环不能嵌套后用线段树与set维护即可。

# include <cstdio>
# include <iostream>
# include <algorithm>
# include <map>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; i ++)
const int NR = 100100;
# define u t[x]
# define lc ch[0]
# define rc ch[1]
# define ulfc t[u.lc]
# define urtc t[u.rc]
struct Seg {int ch[2], max; bool cov;} t[NR << 2];
map <int, int> pos;
int n, a[NR], tp[NR], sz, q0, fa[NR];
int gf (int x) {return fa[x] == x ? x : (fa[x] = gf (fa[x]));}
inline void Upd (int x)
{
    u.max = 0;
    if (a[ulfc.max] > a[u.max]) u.max = ulfc.max;
    if (a[urtc.max] > a[u.max]) u.max = urtc.max;
}
int Max (int x, int l, int r, int ql, int qr)
{
    if (u.cov) return 0;
    if (ql <= l && r <= qr) return u.max;
    int mid = (l + r) >> 1, ret = 0, tmp;
    if (ql <= mid && a[tmp = Max (u.lc, l, mid, ql, qr)] > a[ret]) ret = tmp; 
    if (qr > mid && a[tmp = Max (u.rc, mid + 1, r, ql, qr)] > a[ret]) ret = tmp; 
    return ret;
}
void Del (int x, int l, int r, int cl, int cr)
{
    if (u.cov) return ;
    if (cl <= l && r <= cr) {u.cov = 1, u.max = 0; return ;}
    int mid = (l + r) >> 1, ret = 0;
    if (cl <= mid) Del (u.lc, l, mid, cl, cr);
    if (cr > mid) Del (u.rc, mid + 1, r, cl, cr);
    Upd (x);
}
int Build (int l, int r)
{
    int x = ++ sz, mid = (l + r) >> 1; u.cov = 0;
    if (l == r) return u.max = l, x;
    return u.lc = Build (l, mid), u.rc = Build (mid + 1, r), Upd (x), x;
}
bool Cmp (int i, int j) {return a[i] < a[j];}
int main ()
{
    for (scanf ("%d", &q0); q0; q0 --)
    {
        scanf ("%d", &n), sz = 0;
        REP (i, n) scanf ("%d", &a[i]), tp[i] = i, fa[i] = 0;
        sort (tp + 1, tp + n + 1, Cmp), Build (1, n);
        pos.clear (), pos[0] = 0;
        REP (p, n)
        {
            int i = tp[p];
            map <int, int>::iterator it = pos.upper_bound (i); it --;
            char sc = (p == n ? '\n' : ' ');
            if (it->first<it->second) 
            {
                printf ("%d%c", a[i + 1], sc);
                continue;
            }
            if (fa[i])
            {
                int j = gf (i);
                if (i == n || pos.find (i + 1) != pos.end () || a[j] > a[i + 1]) 
                    printf ("%d%c", a[j], sc), pos[i] = j, pos[j] = i;
                else 
                    Del (1, 1, n, i + 1, i + 1), fa[i + 1] = i, printf ("%d%c", a[i + 1], sc);
                continue;
            }
            int j = Max (1, 1, n, it->first + 1, i);
            if (i == n || pos.find (i + 1) != pos.end () || a[j] > a[i + 1])
                Del (1, 1, n, j, i), pos[i] = j, pos[j] = i, printf ("%d%c", a[j], sc);
            else Del (1, 1, n, i, i + 1), fa[i] = i, fa[i + 1] = i, printf ("%d%c", a[i + 1], sc);
        }
    }
    return 0;
}