This is not the end.

0%

20200325 联考

Posted on Edited on

A - string

经典题目。

B - tree

容易想到 $f_u$ 表示把 $u$ 子树变成 $T_1$ 中它们对应的子树，能够有的最大深度和。

设个中间量 $dp_{u,j}$ 表示 $u$ 子树中，$u$ 在的那条链的长度是 $j$ 时，最大深度和。

合并子树的时候，因为 $T_2$ 必须是二叉树，所以状态中再加入大小为 $2^2$ 的一维表示左右儿子选过没有。

总时间复杂度 $O(n^2)$ 。

C - sort

思路和实现细节

考场上想的是线段树套trie，修改的时候需要支持可持久化分裂/合并，空间是两个 $\log$ 的，其中一个还是 $\log V$ ，用脚趾头想都知道开不下。

考后看题解发现自己 zz 了：如果不需要实时查询区间信息，就不需要在节点里维护整个子树的信息。 题解还是很妙的，用平衡树维护每个排过序的段，段内用 trie 维护元素。在这一段被再次分裂之前进行的操作都不要打到 trie 上，这样 trie 中的元素的大小关系就是它们在序列中的位置关系。输出答案的函数中传入对这整个 trie 进行过的操作，然后按照它们操作前的大小关系顺序输出。

1
2
3
4
5
6
7
8
9
10
void getans(int u,int d,uint v,TAG t) {
    if(d==-1) {
        v&=t.t0,v|=t.t1,v^=t.r;
        for(int i=1;i<=sz[u];++i) printf("%u ",v);
        return;
    }
    push_down(u,d);
    if(ch[u][0]) getans(ch[u][0],d-1,v,t);
    if(ch[u][1]) getans(ch[u][1],d-1,v|1u<<d,t);
}

外层用的是 fhq_treap ，因为这样区间操作很舒服。考虑到分裂的时候可能会分裂一个节点，给每个节点随机一个权值可能就不太均匀了，所以写的是这样的 merge ：

1
2
3
4
5
6
7
void mer(int &r,int a,int b) {
    if(!a||!b) return (void)(r=a+b);
    push_down(a),push_down(b);
    if(rnd()&1) mer(ch[r][0],a,ch[r=b][0]);
    else mer(ch[r][1],ch[r=a][1],b);
    push_up(r);
}

其中 rnd 是返回随机数。

关于操作的标记的处理：把 AND 和 OR 想象成赋值，XOR 想象成取反。优先操作 AND 和 OR ，加入 XOR 标记的时候要计算它对 AND 和 OR 标记的影响。也就是没有被 AND 和 OR 覆盖到的位才去考虑 XOR 标记的影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const uint S=~0u;
struct TAG {
    uint t0,t1,r;
    TAG(): t0(S),t1(0),r(0) {}
    void add0(uint a) { t0&=a,t1&=a,r&=a; }
    void add1(uint a) { t0|=a,t1|=a,r&=~a; }
    void addr(uint a) {
        uint A0=(~t0)&a,A1=t1&a;
        t1^=A1,t1|=A0;
        t0^=A0,t0&=~A1;
        r=(r^a)&((~t1)&t0);
    }
    void add(TAG B) {
        t0&=B.t0,t0|=B.t1;
        t1&=B.t0,t1|=B.t1;
        r=r&((~t1)&t0);
        addr(B.r);
    }
};

关于 trie 中下放标记的时候合并左右子树的复杂度：可以用和线段树合并复杂度同理的分析，得到复杂度均摊 $O(\log n)$ （可参看我的这篇题解的结尾处的分析）。是的你没看错下面这个反复递归调用的玩意的复杂度居然 TMD 只有一个 $\log$ ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void push_down(int c,int d);
void mer(int &u,int v,int d) {
    if(!u||!v) return (void)(u=u+v);
    sz[u]+=sz[v];
    push_down(u,d),push_down(v,d);
    mer(ch[u][0],ch[v][0],d-1),mer(ch[u][1],ch[v][1],d-1);
}
void push_down(int c,int d) {
    if(!(tg[c].t0>>d&1)) mer(ch[c][0],ch[c][1],d-1),ch[c][1]=0;
    if(tg[c].t1>>d&1) mer(ch[c][1],ch[c][0],d-1),ch[c][0]=0;
    if(tg[c].r>>d&1) swap(ch[c][0],ch[c][1]);
    if(ch[c][0]) tg[ch[c][0]].add(tg[c]);
    if(ch[c][1]) tg[ch[c][1]].add(tg[c]);
    tg[c]=TAG();
}

其它的感觉就和这些数据结构的正常写法没有什么区别。

代码

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
196
197
198
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define PB push_back
#define MP make_pair
#define PII pair<int,int>
#define FIR first
#define SEC second
#define ll long long
#define uint unsigned
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=1e5+10;
const uint S=~0u;
struct TAG {
    uint t0,t1,r;
    TAG(): t0(S),t1(0),r(0) {}
    void add0(uint a) { t0&=a,t1&=a,r&=a; }
    void add1(uint a) { t0|=a,t1|=a,r&=~a; }
    void addr(uint a) {
        uint A0=(~t0)&a,A1=t1&a;
        t1^=A1,t1|=A0;
        t0^=A0,t0&=~A1;
        r=(r^a)&((~t1)&t0);
    }
    void add(TAG B) {
        t0&=B.t0,t0|=B.t1;
        t1&=B.t0,t1|=B.t1;
        r=r&((~t1)&t0);
        addr(B.r);
    }
};
namespace trie {
    const int M=1e7+N;
    TAG tg[M];
    int ch[M][2],sz[M],ncnt;
    int st[1000000],top;
    void rec(int x) { if(x&&top<1000000) st[top++]=x; }
    int newnode() {
    	if(top) {
    		int u=st[--top];
    		ch[u][0]=ch[u][1]=sz[u]=0,tg[u]=TAG();
    		return u;
    	}
    	else return ++ncnt;
    }
    void push_up(int c) { sz[c]=sz[ch[c][0]]+sz[ch[c][1]]; }
    void push_down(int c,int d);
    void mer(int &u,int v,int d) {
        if(!u||!v) return (void)(u=u+v);
        sz[u]+=sz[v];
        push_down(u,d),push_down(v,d);
        mer(ch[u][0],ch[v][0],d-1),mer(ch[u][1],ch[v][1],d-1);
    }
    void push_down(int c,int d) {
        if(!(tg[c].t0>>d&1)) mer(ch[c][0],ch[c][1],d-1),ch[c][1]=0;
        if(tg[c].t1>>d&1) mer(ch[c][1],ch[c][0],d-1),ch[c][0]=0;
        if(tg[c].r>>d&1) swap(ch[c][0],ch[c][1]);
        if(ch[c][0]) tg[ch[c][0]].add(tg[c]);
        if(ch[c][1]) tg[ch[c][1]].add(tg[c]);
        tg[c]=TAG();
    }
    void init(int &rt,uint x) {
        int cur=rt=newnode(); sz[cur]++;
        for(int i=31;i>=0;--i) {
            int c=(x>>i)&1;
            if(!ch[cur][c]) ch[cur][c]=newnode();
            cur=ch[cur][c],sz[cur]++;
        }
    }
    void split(int c,int &u,int &v,int k,int d) {
        if(k==0) return (void)(u=0,v=c);
        if(k==sz[c]) return (void)(u=c,v=0);
        if(!u) u=newnode();
        if(!v) v=newnode();
        if(d==-1) {
            sz[u]=k,sz[v]=sz[c]-k;
            return;
        }
        push_down(c,d);
        if(sz[ch[c][0]]>=k) {
            ch[v][1]=ch[c][1],ch[u][1]=0;
            split(ch[c][0],ch[u][0],ch[v][0],k,d-1);
        }
        else {
            ch[u][0]=ch[c][0],ch[v][0]=0;
            split(ch[c][1],ch[u][1],ch[v][1],k-sz[ch[c][0]],d-1);
        }
        push_up(u),push_up(v);
        rec(c);
    }
    void getans(int u,int d,uint v,TAG t) {
        if(d==-1) {
            v&=t.t0,v|=t.t1,v^=t.r;
            for(int i=1;i<=sz[u];++i) printf("%u ",v);
            return;
        }
        push_down(u,d);
        if(ch[u][0]) getans(ch[u][0],d-1,v,t);
        if(ch[u][1]) getans(ch[u][1],d-1,v|1u<<d,t);
    }
}
namespace treap {
    uint seed=128;
    uint rnd() {
        seed^=seed<<13,seed^=seed>>17,seed^=seed<<5;
        return seed;
    }
    const int M=N+N*4;
    int ch[M][2],ncnt;
    int len[M],sz[M],rt[M];
    TAG tg[M],val[M];
    int RT;
    int newnode() { return ++ncnt; }
    void add(int c,TAG t) { tg[c].add(t),val[c].add(t); }
    void push_down(int c) {
        if(ch[c][0]) add(ch[c][0],tg[c]);
        if(ch[c][1]) add(ch[c][1],tg[c]);
        tg[c]=TAG();
    }
    void push_up(int c) { sz[c]=sz[ch[c][0]]+sz[ch[c][1]]+len[c]; }
    void split(int x,int k,int &a,int &b) {
        if(!x) return (void)(a=b=0);
        push_down(x);
        if(sz[ch[x][0]]<k&&sz[ch[x][0]]+len[x]>k) {
            a=newnode(),b=newnode();
            val[a]=val[b]=val[x];
            trie::split(rt[x],rt[a],rt[b],k-sz[ch[x][0]],31);
            ch[a][0]=ch[x][0],ch[b][1]=ch[x][1];
            ch[a][1]=ch[b][0]=0;
            len[a]=k-sz[ch[x][0]],len[b]=len[x]-len[a];
            push_up(a),push_up(b);
            return;
        }
        if(sz[ch[x][0]]>=k) split(ch[x][0],k,a,ch[b=x][0]);
        else split(ch[x][1],k-sz[ch[x][0]]-len[x],ch[a=x][1],b);
        push_up(x);
    }
    void mer(int &r,int a,int b) {
        if(!a||!b) return (void)(r=a+b);
        push_down(a),push_down(b);
        if(rnd()&1) mer(ch[r][0],a,ch[r=b][0]);
        else mer(ch[r][1],ch[r=a][1],b);
        push_up(r);
    }
    void split_rng(int l,int r,int &x,int &y,int &z) {
        split(RT,l-1,x,y);
        split(y,r-l+1,y,z);
    }
    void dfs_mer(int u) {
        push_down(u);
        trie::tg[rt[u]].add(val[u]),val[u]=TAG();
        if(ch[u][0]) dfs_mer(ch[u][0]),trie::mer(rt[u],rt[ch[u][0]],31);
        if(ch[u][1]) dfs_mer(ch[u][1]),trie::mer(rt[u],rt[ch[u][1]],31);
    }
    void opt() {
        int op,l,r,v; rd(op),rd(l),rd(r); if(op<=3) rd(v);
        int x,y,z; split_rng(l,r,x,y,z);
        if(op<=3) {
            TAG tmp;
            if(op==1) tmp.add1(v);
            if(op==2) tmp.add0(v);
            if(op==3) tmp.addr(v);
            add(y,tmp);
        }
        else dfs_mer(y),len[y]=trie::sz[rt[y]],ch[y][0]=ch[y][1]=0,push_up(y);
        mer(RT,x,y),mer(RT,RT,z);
    }
    void build(uint *a,int n) {
        for(int i=1;i<=n;++i) {
            int u=newnode();
            trie::init(rt[u],a[i]),len[u]=1,push_up(u);
            mer(RT,RT,u);
        }
    }
    void getans(int u=RT) {
        push_down(u);
        if(ch[u][0]) getans(ch[u][0]);
        trie::getans(rt[u],31,0,val[u]);
        if(ch[u][1]) getans(ch[u][1]);
    }
}
uint a[N],n,q;
int main() {
    rd(n),rd(q);
    for(int i=1;i<=n;++i) rd(a[i]);
    treap::build(a,n);
    for(int i=1;i<=q;++i) treap::opt();
    treap::getans();
    return 0;
}