MLE自动机的博客

发表于 更新于 Changyan： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
mt19937 rnd(20130825);
template<int N>
class treap
{
private:
	struct node
	{
		int l, r, sz, v, w, pr;
	} tr[N];
	int cnt, root;
	void update(int rt)
	{
		tr[rt].sz = tr[tr[rt].l].sz + tr[tr[rt].r].sz + tr[rt].w;
	}
	void lturn(int &rt)
	{
		int x = tr[rt].r;
		tr[rt].r = tr[x].l;
		tr[x].l = rt;
		tr[x].sz = tr[rt].sz;
		update(rt); rt = x;
	}
	void rturn(int &rt)
	{
		int x = tr[rt].l;
		tr[rt].l = tr[x].r;
		tr[x].r = rt;
		tr[x].sz = tr[rt].sz;
		update(rt); rt = x;
	}
	bool _insert(int &rt, int v)
	{
		if (!rt) return tr[rt = ++ cnt] = {0, 0, 1, v, 1, (int)rnd()}, 1;
		tr[rt].sz ++;
		if (tr[rt].v == v) return tr[rt].w ++, 0;
		else if (v < tr[rt].v)
		{
			bool res = _insert(tr[rt].l, v);
			if (tr[tr[rt].l].pr < tr[rt].pr) rturn(rt);
			return res;
		}
		else
		{
			bool res = _insert(tr[rt].r, v);
			if (tr[tr[rt].r].pr < tr[rt].pr) lturn(rt);
			return res;
		}
	}
	bool _erase(int &rt, int v)
	{
		if (!rt) return 0;
		if (tr[rt].v == v)
		{
			if (tr[rt].w > 1) return tr[rt].sz --, tr[rt].w --, 1;
			if (!(tr[rt].l && tr[rt].r)) rt = tr[rt].l | tr[rt].r;
			else if (tr[tr[rt].l].pr < tr[tr[rt].r].pr)
				return rturn(rt), _erase(rt, v);
			else return lturn(rt), _erase(rt, v);
		}
		else
		{
			if (v < tr[rt].v) {if (_erase(tr[rt].l, v)) tr[rt].sz --;}
			else {if (_erase(tr[rt].r, v)) tr[rt].sz --;}
		}
		return 1;
	}
	int _prev(int rt, int v)
	{
		if (!rt) return -INF;
		if (tr[rt].v < v) return max(tr[rt].v, _prev(tr[rt].r, v));
		else return _prev(tr[rt].l, v);
	}
	int _next(int rt, int v)
	{
		if (!rt) return INF;
		if (tr[rt].v > v) return min(tr[rt].v, _next(tr[rt].l, v));
		else return _next(tr[rt].r, v);
	}
	int _rank(int rt, int v)
	{
		if (!rt) return 1;
		if (tr[rt].v == v) return tr[tr[rt].l].sz + 1;
		else if (v < tr[rt].v) return _rank(tr[rt].l, v);
		else return tr[tr[rt].l].sz + tr[rt].w + _rank(tr[rt].r, v);
	}
	int _kth(int rt, int k)
	{
		if (!rt) return -INF;
		if (k <= tr[tr[rt].l].sz) return _kth(tr[rt].l, k);
		else if (k > tr[tr[rt].l].sz + tr[rt].w)
			return _kth(tr[rt].r, k - tr[tr[rt].l].sz - tr[rt].w);
		else return tr[rt].v;
	}
public:
	int size() {return tr[root].sz;}
	bool insert(int v) {return _insert(root, v);}
	bool erase(int v) {return _erase(root, v);}
	int prev(int v) {return _prev(root, v);}
	int next(int v) {return _next(root, v);}
	int rank(int v) {return _rank(root, v);}
	int kth(int k) {return _kth(root, k);}
};

可以通过 P3369 & P6136。

发表于 Changyan：

忘了写了，现在补一下。

这次还是发着低烧打的，对成绩比较满意。

T1

水题，二分+前缀和过了。

$实得\ 100 / 应得\ 100$

T2

bitset+树形dp秒了。

$实得\ 100 / 应得\ 100$

T3

第一反应是单调队列，但是维护不了第 k 小。

后来想到了对顶堆，稍微调了一会过了。

$实得\ 100 / 应得\ 100$

T4

一丁点思路没有，打了暴力。

$实得\ 20 / 应得\ 20$

通过讲解得知正解为扫描线。竟然是没学过的新算法，就当我 ak 了吧（bushi）

总结

一分没挂，出乎意料。

收获了新知识扫描线。

排名

rk4，去掉重修和作弊的就是rk3。肥肠蛮夷。

发表于 Changyan：

从这里转移过来的。

一劳永逸，封装进类里了，支持取模。

欢迎指出问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
template<typename T>
class Matrix
{
private:
    vector<vector<T>> a; int n, m; T mod = 0;
public:
    Matrix(int h, int w) {n = h; m = w; a.resize(n + 1, vector<T>(m + 1));}
    Matrix(const Matrix &b) {n = b.n; m = b.m; a = b.a; mod = b.mod;}
    explicit Matrix(const vector<vector<T>> &b)
    {
        n = b.size();
        m = b[0].size();
        a.resize(n + 1, vector<T>(m + 1));
        rep(i, 1, n) rep(j, 1, m) a[i][j] = b[i - 1][j - 1];
    }
    Matrix &operator=(const Matrix &b) {a = b.a; return *this;}
    T &operator()(int i, int j) {return a[i][j];}
    Matrix operator+(const Matrix &b) const
    {
        Matrix<T> res(n, m); res.setmod(mod);
        rep(i, 1, n) rep(j, 1, m)
            if (mod) res.a[i][j] = (a[i][j] + b.a[i][j]) % mod;
            else res.a[i][j] = a[i][j] + b.a[i][j];
        return res;
    }
    Matrix operator+=(const Matrix &b) {return *this = *this + b;}
    Matrix operator*(const Matrix &b) const
    {
        if (m != b.n) return Matrix(0, 0);
        Matrix<T> res(n, b.m); res.setmod(mod);
        rep(i, 1, n) rep(j, 1, b.m) rep(l, 1, m)
            if (mod) (res.a[i][j] += a[i][l] * b.a[l][j] % mod) %= mod;
            else res.a[i][j] += a[i][l] * b.a[l][j];
        return res;
    }
    Matrix operator*=(const Matrix &b) {return *this = *this * b;}
    Matrix operator^(T b) const
    {
        if (n != m) return Matrix(0, 0);
        Matrix<T> res(n, n), a(*this); res.setmod(mod);
        rep(i, 1, n) rep(j, 1, n) res.a[i][j] = i == j;
        for (; b; b >>= 1, a *= a) if (b & 1) res *= a;
        return res;
    }
    Matrix operator^=(T b) {return *this = *this ^ b;}
    void print() const
    {
        rep(i, 1, n)
        {
            rep(j, 1, m) cout << a[i][j] << ' ';
            cout << '\n';
        }
    }
    void input()
    {
        rep(i, 1, n) rep(j, 1, m) cin >> a[i][j];
    }
    void setmod(int x) {mod = x;}
};

可以AC洛谷B2104，B2105，P3390。

发表于 Changyan：

第一篇文章

0%