分类目录归档:

洛谷 P3369 【模板】普通平衡树

手写Splay成功。庆祝能写出来的第一个BBST!
代码如下:

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include<iostream>
#include<cassert>
using namespace std;
class Splay {
private:
    struct Node {
        int v; //值
        Node* f, * l, * r; //父,左孩子,右孩子
        int cnts; //本子树下包含自身的所有**元素**数目
        int rep; //该值重复了多少次
        Node(int v, Node* f) :v(v), f(f), l(NULL), r(NULL), cnts(1), rep(1) {}
    };
    Node* _root;
#define root _root->r
    void update(Node* p) { //更新cnts值
        p->cnts = p->rep;
        if (p->l)p->cnts += p->l->cnts;
        if (p->r)p->cnts += p->r->cnts;
    }
    bool identify(Node* s, Node* f) { //确定本节点是左孩子还是右孩子,左孩子false,右孩子true
        return !f || s == f->r;
    }
    void connect(Node* s, Node* f, bool r) { //儿子地址,父亲地址,连接到左儿子还是右儿子
        if (f)(r ? f->r : f->l) = s; //父亲更新新儿子
        if (s)s->f = f; //儿子更新新父亲
    }
    void rotate(Node* s) { //儿子节点的旋转
        Node* f = s->f, * gf = s->f->f;
        if (!identify(s, f)) { //左孩子
            connect(s->r, f, false);
            connect(f, s, true);
            connect(s, gf, identify(f, gf));
        }
        else { //右孩子
            connect(s->l, f, true);
            connect(f, s, false);
            connect(s, gf, identify(f, gf));
        }
        update(f);
        update(s);
    }
    void splay(Node* s, Node* e) { //伸展操作,将节点s旋转到节点e所在的位置
        e = e->f;
        while (s->f != e) {
            Node* f = s->f;
            if (f->f == e)rotate(s); //s是e的直系儿子,只需做单旋
            else if (identify(f, f->f) == identify(s, f)) { //Zig-Zig或Zag-Zag,需要先旋父亲节点,再旋儿子节点
                rotate(f);
                rotate(s);
            }
            else { //Zig-Zag或Zag-Zig
                rotate(s);
                rotate(s);
            }
        }
    }

public:
    Splay() {
        _root = new Node(0, NULL);
    }
    ~Splay() {
        delete _root;
    }
    Node* find(int v) {
        Node* cur = root;
        if (!cur)return NULL;
        while (1) {
            if (cur->v == v) break;
            Node* next = v < cur->v ? cur->l : cur->r;
            if (!next)break;
            cur = next;
        }
        splay(cur, root);
        root = cur;
        if (cur->v == v)return cur;
        else return NULL;
    }
    void del(int v) {
        Node* cur = find(v);
        if (!cur)return;
        if (cur->rep > 1) { //节点个数出现多于1次
            cur->rep--;
            cur->cnts--;
            return;
        }
        if (!cur->l && !cur->r) { //删除最后一个仅剩的节点
            root = NULL;
        }
        else if (!cur->l) { //无左子树时直接把右子树拼到根
            root = cur->r;
            root->f = _root;
        }
        else { //有左子树时,把左子树的最大值旋到根的左子,将根的右子放到根的左子的右子,删根后补左子树
            Node* l = cur->l;
            while (l->r)l = l->r;
            splay(l, cur->l);
            Node* r = cur->r;
            connect(r, l, true);
            root = l;
            root->f = _root;
            update(l);
        }
        delete cur;
    }
    void insert(int v) {
        Node* cur = find(v);
        if (!root) { //特判空树
            root = new Node(v, _root);
            return;
        }
        if (cur && cur->v == v) { //元素存在,直接把次数+1
            cur->rep++;
            cur->cnts++;
            return;
        }
        Node* newNode = new Node(v, _root);
        if (root->v < v) { //将v接入右侧
            connect(root, newNode, false);
            connect(root->r, newNode, true);
            root->r = NULL;
        }
        else { //将v接入左侧
            connect(root, newNode, true);
            connect(root->l, newNode, false);
            root->l = NULL;
        }
        update(root);
        update(newNode);
        root = newNode;
        newNode->f = _root;
    }
    int rank(int v) {
        Node* cur = find(v);
        if (!cur)return -1;
        int lCnts = cur->l ? cur->l->cnts : 0;
        return lCnts + 1;
    }
    int atrank(int rank) {
        Node* cur = root;
        while (cur) {
            int lCnts = cur->l ? cur->l->cnts : 0;
            if (lCnts < rank && rank <= lCnts + cur->rep) {
                splay(cur, root);
                return cur->v;
            }
            if (rank <= lCnts)cur = cur->l;
            else {
                rank -= lCnts + cur->rep;
                cur = cur->r;
            }
        }
        return -1;
    }
    int upper(int v) {
        Node* cur = find(v);
        int lCnts = root->l ? root->l->cnts : 0;
        if (root->v <= v)return atrank(lCnts + root->rep + 1);
        return root->v;
    }
    int lower(int v) {
        Node* cur = find(v);
        int lCnts = root->l ? root->l->cnts : 0;
        if (root->v >= v)return atrank(lCnts);
        return root->v;
    }
#undef root
};
int main() {
    Splay splay;
    int n;
    cin >> n;
    while (n--) {
        int op1, op2;
        cin >> op1 >> op2;
        if (op1 == 1) {
            splay.insert(op2);
        }
        else if (op1 == 2) {
            splay.del(op2);
        }
        else if (op1 == 3) {
            cout << splay.rank(op2) << endl;
        }
        else if (op1 == 4) {
            cout << splay.atrank(op2) << endl;
        }
        else if (op1 == 5) {
            cout << splay.lower(op2) << endl;
        }
        else if (op1 == 6) {
            cout << splay.upper(op2) << endl;
        }
    }
}

参考资料:
https://www.luogu.com.cn/blog/user19027/solution-p3369
非常感谢rentenglong同学

洛谷 P2580 于是他错误的点名开始了

Trie树练手题,然而空间不够用最后一个点MLE,90

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
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int MaxN = 5000000;
int trie[MaxN][26];
int cnts[MaxN];
int tot;
int trieInsert(string s) {
    int node = 0;
    for (int i = 0; i < s.size(); i++) {
        if (!trie[node][s[i] - 'a'])node = trie[node][s[i] - 'a'] = ++tot;
        else node = trie[node][s[i] - 'a'];
    }
    return node;
}
int main() {
    int n,m;
    string s;
    cin >> n;
    while (n--) {
        cin >> s;
        int node=trieInsert(s);
        cnts[node]=1;
    }
    cin >> m;
    while (m--) {
        cin >> s;
        int node = trieInsert(s);
        if (cnts[node] == 1){
            cout << "OK" << endl;
            cnts[node]=2;
        }
        else if (cnts[node] == 0)cout << "WRONG" << endl;
        else if (cnts[node] == 2)cout << "REPEAT" << endl;
    }
}

洛谷 P1481 魔族密码

今学习Trie树:https://blog.csdn.net/weixin_43792276/article/details/98977397

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
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int MaxN = 5000;
int trie[MaxN][26];
int cnts[MaxN];
int tot;
void trieInsert(string s) {
    int node = 0;
    for (int i = 0; i < s.size(); i++) {
        if (!trie[node][s[i] - 'a'])node = trie[node][s[i] - 'a'] = ++tot;
        else node = trie[node][s[i] - 'a'];
    }
    cnts[node]++;
}
void trieAccumulate(int node) {
    for (int i = 0; i < 26; i++) {
        if (trie[node][i]) {
            cnts[trie[node][i]] += cnts[node];
            trieAccumulate(trie[node][i]);
        }
    }
}
int main() {
    int n;
    string s;
    cin >> n;
    while (n--) {
        cin >> s;
        trieInsert(s);
    }
    trieAccumulate(0);
    int result = 0;
    for (int i = 0; i <= tot; i++)result = max(result, cnts[i]);
    cout << result;
}

洛谷 P1972 [SDOI2009]HH的项链

参考题解:https://www.luogu.org/blog/skylee/solution-p1972

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
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int arr[500005];
int c[500000];
int last[1000001];
int flag=0;
struct question{
    int id,l,r,ans;
    bool operator < (const question& q2) const{
        if(flag==0)return r<q2.r;
        else return id<q2.id;
    }
}qs[200005];
inline int lowbit(int i){
    return i&(-i);
}
int query(int x){
    int sum=0;
    while(x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
void update(int i,int v){
    while(i<=n){
        c[i]+=v;
        i+=lowbit(i);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>qs[i].l>>qs[i].r;
        qs[i].id=i;
    }
    sort(qs+1,qs+m+1);
    int ptr=1;
    for(int i=1;i<=m;i++){
        for(;ptr<=qs[i].r;ptr++){
            if(last[arr[ptr]]!=0)update(last[arr[ptr]],-1);
            update(last[arr[ptr]]=ptr,1);
        }
        qs[i].ans=query(qs[i].r)-query(qs[i].l-1);
    }
    flag=1;
    sort(qs+1,qs+m+1);
    for(int i=1;i<=m;i++){
        cout<<qs[i].ans<<endl;
    }
}

洛谷 P2023 [AHOI2009]维护序列

没啥说的,和上一道题一模一样。。只是把输入改掉就可以了。。

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
#include<iostream>
using namespace std;
struct segmentTree{
    typedef long long ll;
    const static int MAX=100000;
    ll MOD;
    ll v[4*MAX],aTg[4*MAX],mTg[4*MAX];
    inline static ll lson(ll r){return r*2;}
    inline static ll rson(ll r){return r*2+1;}
    void build(ll r,ll* a,ll s,ll e){
        aTg[r]=0;mTg[r]=1;
        if(s==e){v[r]=a[s]%MOD;return;}
        ll m=(s+e)>>1;
        build(lson(r),a,s,m);
        build(rson(r),a,m+1,e);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
    void pushDown(ll r,ll s,ll e){
        if(aTg[r]==0&&mTg[r]==1)return;
        ll m=(s+e)>>1;
        v[lson(r)]=(v[lson(r)]*mTg[r]%MOD+aTg[r]*(m-s+1)%MOD)%MOD;
        v[rson(r)]=(v[rson(r)]*mTg[r]%MOD+aTg[r]*(e-m)%MOD)%MOD;
        aTg[lson(r)]=(aTg[lson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        aTg[rson(r)]=(aTg[rson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        mTg[lson(r)]=(mTg[lson(r)]*mTg[r])%MOD;
        mTg[rson(r)]=(mTg[rson(r)]*mTg[r])%MOD;
        aTg[r]=0;mTg[r]=1;
    }
    ll query(ll r,ll cs,ll ce,ll qs,ll qe){
        if(qe<cs||ce<qs)return 0;
        if(qs<=cs&&ce<=qe)return v[r]%MOD;
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        return (query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe))%MOD;
    }
    void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv=0,ll mulv=1){
        if(ue<cs||ce<us)return;
        if(us<=cs&&ce<=ue){
            v[r]=(v[r]*mulv%MOD+addv*(ce-cs+1))%MOD;
            aTg[r]=(aTg[r]*mulv%MOD+addv)%MOD;
            mTg[r]=(mTg[r]*mulv)%MOD;
            return;
        }
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        update(lson(r),cs,cmd,us,ue,addv,mulv);
        update(rson(r),cmd+1,ce,us,ue,addv,mulv);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
}ST;
typedef long long ll;
ll n,m,p;
ll a[100005];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>p;
    for(int i=1;i<=n;i++)cin>>a[i];
    cin>>m;
    ST.MOD=p;
    ST.build(1,a,1,n);
    for(int i=1;i<=m;i++){
        ll op,x,y,k;
        cin>>op;
        if(op==1||op==2){
            cin>>x>>y>>k;
            if(op==1)ST.update(1,1,n,x,y,0,k);
            else ST.update(1,1,n,x,y,k);
        }else{
            cin>>x>>y;
            cout<<ST.query(1,1,n,x,y)%p<<endl;
        }
    }
}

洛谷 P3373 【模板】线段树 2

总算写出来了。。。线段树同时维护乘法和加法,欢迎体验!

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
#include<iostream>
using namespace std;
struct segmentTree{
    typedef long long ll;
    const static int MAX=100000;
    ll MOD;
    ll v[4*MAX],aTg[4*MAX],mTg[4*MAX];
    inline static ll lson(ll r){return r*2;}
    inline static ll rson(ll r){return r*2+1;}
    void build(ll r,ll* a,ll s,ll e){
        aTg[r]=0;mTg[r]=1;
        if(s==e){v[r]=a[s]%MOD;return;}
        ll m=(s+e)>>1;
        build(lson(r),a,s,m);
        build(rson(r),a,m+1,e);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
    void pushDown(ll r,ll s,ll e){
        if(aTg[r]==0&&mTg[r]==1)return;
        ll m=(s+e)>>1;
        v[lson(r)]=(v[lson(r)]*mTg[r]%MOD+aTg[r]*(m-s+1)%MOD)%MOD;
        v[rson(r)]=(v[rson(r)]*mTg[r]%MOD+aTg[r]*(e-m)%MOD)%MOD;
        aTg[lson(r)]=(aTg[lson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        aTg[rson(r)]=(aTg[rson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        mTg[lson(r)]=(mTg[lson(r)]*mTg[r])%MOD;
        mTg[rson(r)]=(mTg[rson(r)]*mTg[r])%MOD;
        aTg[r]=0;mTg[r]=1;
    }
    ll query(ll r,ll cs,ll ce,ll qs,ll qe){
        if(qe<cs||ce<qs)return 0;
        if(qs<=cs&&ce<=qe)return v[r]%MOD;
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        return (query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe))%MOD;
    }
    void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv=0,ll mulv=1){
        if(ue<cs||ce<us)return;
        if(us<=cs&&ce<=ue){
            v[r]=(v[r]*mulv%MOD+addv*(ce-cs+1))%MOD;
            aTg[r]=(aTg[r]*mulv%MOD+addv)%MOD;
            mTg[r]=(mTg[r]*mulv)%MOD;
            return;
        }
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        update(lson(r),cs,cmd,us,ue,addv,mulv);
        update(rson(r),cmd+1,ce,us,ue,addv,mulv);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
}ST;
typedef long long ll;
ll n,m,p;
ll a[100005];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++)cin>>a[i];
    ST.MOD=p;
    ST.build(1,a,1,n);
    for(int i=1;i<=m;i++){
        ll op,x,y,k;
        cin>>op;
        if(op==1||op==2){
            cin>>x>>y>>k;
            if(op==1)ST.update(1,1,n,x,y,0,k);
            else ST.update(1,1,n,x,y,k);
        }else{
            cin>>x>>y;
            cout<<ST.query(1,1,n,x,y)%p<<endl;
        }
    }
}

洛谷 P3368 【模板】树状数组 2

看起来实际上也挺好做的,就是只要把树状数组维护的对象改成原序列的差分数组即可。这样每次树状数组所谓的query求1到n的前缀和也就变成了就单点n的值。

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
#include<iostream>
#include<cstring>
using namespace std;
struct BTA{//Update Section,Query Single Point
    const static int MAX=500000;
    int C[MAX+5];
    BTA(){
        memset(C,0,sizeof(C));
    }
    int lowbit(int i){
        return i&(-i);
    }
    int query(int x){
        int sum=0;
        while(x>0){
            sum+=C[x];
            x-=lowbit(x);
        }
        return sum;
    }
    void update(int i,int v){
        while(i<=MAX){
            C[i]+=v;
            i+=lowbit(i);
        }
    }
    void updateSection(int l,int r,int v){
        update(l,v);
        update(r+1,-v);
    }
}TA;
int n,m;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int v;
        cin>>v;
        TA.updateSection(i,i,v);
    }
    for(int i=1;i<=m;i++){
        int op,v1,v2,v3;
        cin>>op;
        if(op==1){
            cin>>v1>>v2>>v3;
            TA.updateSection(v1,v2,v3);
        }
        else{
            cin>>v1;
                cout<<TA.query(v1)<<endl;
        }
    }
}

洛谷 P1197 [JSOI2008]星球大战

总算是没看题解自己A了一道题,呜呜呜。

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
#include<iostream>
#include<vector>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
int father[400005];
int _find(int node){
    if(father[node]==-1)return node;
    return father[node]=_find(father[node]);
}
bool _union(int x,int y){
    if(_find(x)==_find(y))return false;
    father[_find(x)]=_find(y);
    return true;
}
int n,m,k;
bool alive[400005];
vector<int> edges[400005];
stack<int> ans;
stack<int> q;
int cnt,cntn;
int main(){
    ios::sync_with_stdio(false);
    memset(father,-1,sizeof(father));
    memset(alive,true,sizeof(alive));
    cin>>n>>m;
    cnt=0;cntn=n;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    cin>>k;
    for(int i=1;i<=k;i++){
        int v;
        cin>>v;
        alive[v]=false;
        q.push(v);
        cntn--;
    }
    for(int i=0;i<n;i++){
        if(!alive[i])continue;
        for(int j=0;j<edges[i].size();j++){
            if(!alive[edges[i][j]])continue;
            if(_union(i,edges[i][j]))cnt++;
        }
    }
    ans.push(cntn-cnt);
    while(!q.empty()){
        int cur=q.top();q.pop();
        cntn++;
        alive[cur]=true;
        for(int i=0;i<edges[cur].size();i++){
            if(!alive[edges[cur][i]])continue;
            if(_union(cur,edges[cur][i]))cnt++;
        }
        ans.push(cntn-cnt);
    }
    while(!ans.empty()){
        cout<<ans.top()<<endl;
        ans.pop();
    }
}

洛谷 P3367 【模板】并查集

明明记得之前应该有并查集的板子在博客里?怎么找不到了??

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
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int father[10005];
int _find(int num) {
    if (father[num] == -1)return num;
    else return father[num] = _find(father[num]);
}
void _union(int v1, int v2) {
    if (_find(v1) == _find(v2))return;
    father[_find(v2)] = v1;
}
int n, m;
int main(){
    memset(father, -1, sizeof(father));
    cin >> n >> m;
    while (m--) {
        int z, x, y;
        cin >> z >> x >> y;
        if (z == 1)_union(x, y);
        else cout << (_find(x) == _find(y) ? 'Y' : 'N') << endl;
    }
}