UESTC暑假前集训—数据结构-解题报告

A、对一个有n个数的区间进行四种操作,该区间内每个数的初始值为$ a_i $,在输入的第二行进行输入

op = 1时,输入三个数$ L、R、k $,表示对区间$ [L,R] $的数全部加上$ k $
op = 2时,输入三个数$ L、R、k $,表示对区间$ [L,R] $的数全部乘上$ k $
op = 3时,输入三个数$ L、R、k $,表示对区间$ [L,R] $的数全部变成$ k $
op = 4时,输入两个数$ L、R $,要求输出区间方差乘上样本数的平方后的结果

线段树 lazy标记

答案最后要求输出的是$ n^2S^2 $

那么把方差的公式展开:

那么最后就可以考虑用线段树维护区间元素的和以及区间元素平方的和,线段树我每个结点在维护左右区间端点的同时维护区间和以及区间平方和,同时加上两个lazy标记进行加操作和乘的操作,对于第三个操作直接对区间乘0然后加上k就可以了,考虑到lazy标记的先后性,对于区间的操作先乘后加以保证pushdown的方便;
建树时时间复杂度为$ O(n) $,查询以及修改时最深可以到$ logn $的深度(我瞎b分析的别打我),那么操作时的复杂度为$O(logn)$,一共q次操作,总的时间复杂度是$ O(n + qlogn) $

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

struct Node{
ll sum;
ll sum2;
ll l,r;
ll add,mul;
Node *lchild,*rchild;
};

Node *rt = new Node;
ll ssum2,ssum;
ll n,q,o,L,R,k;
ll ans = 0;

void pushup(Node *root){
root -> sum = (root -> lchild -> sum + root -> rchild -> sum) % mod;
root -> sum2 = (root -> lchild -> sum2 + root -> rchild -> sum2) % mod;
}

void build(Node *root,ll l,ll r){
root -> l = l;
root -> r = r;
root -> add = 0;
root -> mul = 1;
root -> sum = 0;
root -> sum2 = 0;
if(l == r){
long long tmp;
cin>>tmp;
root -> sum = tmp % mod;
root -> sum2 = ((tmp % mod) * (tmp % mod)) % mod;
root -> lchild = root -> rchild = NULL;
return ;
}
ll mid = (l + r) / 2;
root -> lchild = new Node;
root -> rchild = new Node;
build(root -> lchild,l,mid);
build(root -> rchild,mid + 1,r);
pushup(root);
}

void pushdown(Node *root){
ll add = root -> add % mod;
ll mul = root -> mul % mod;
root -> lchild -> add = (root -> lchild -> add * mul % mod + add) % mod;
root -> rchild -> add = (root -> rchild -> add * mul % mod + add) % mod;
root -> lchild -> mul = root -> lchild -> mul * mul % mod;
root -> rchild -> mul = root -> rchild -> mul * mul % mod;
root -> lchild -> sum2 = ((root -> lchild -> sum2 * mul % mod) * mul % mod + ((2 * (add * mul % mod) % mod) * root -> lchild -> sum) % mod + ((root -> lchild -> r - root -> lchild -> l + 1) * add % mod) *add % mod);
root -> rchild -> sum2 = ((root -> rchild -> sum2 * mul % mod) * mul % mod + ((2 * (add * mul % mod) % mod) * root -> rchild -> sum) % mod + ((root -> rchild -> r - root -> rchild -> l + 1) * add % mod) *add % mod);
root -> lchild -> sum = (root -> lchild -> sum * mul % mod + (root -> lchild -> r - root -> lchild -> l + 1) * add % mod) % mod;
root -> rchild -> sum = (root -> rchild -> sum * mul % mod + (root -> rchild -> r - root -> rchild -> l + 1) * add % mod) % mod;
root -> add = 0;
root -> mul = 1;
}

void add(Node *root,ll l,ll r,ll a){
ll nl = root -> l,nr = root -> r;
if(l <= nl && nr <= r){
root -> add = (root -> add + a) % mod;
root -> sum2 = (root -> sum2 + (root -> sum * 2 * a) % mod +((nr - nl + 1) * a % mod ) * a % mod) % mod;
root -> sum = (root -> sum + (nr - nl + 1) * a % mod) % mod;
return ;
}
pushdown(root);
ll mid = (root -> l + root -> r) / 2;
if(r <= mid) add(root -> lchild,l,r,a);
else if (l > mid) add(root -> rchild,l,r,a);
else {
add(root -> lchild,l,mid,a);
add(root -> rchild,mid + 1,r,a);
}
pushup(root);
}

void mul(Node *root,ll l,ll r,ll m){
ll nl = root -> l,nr = root -> r;
if(l <= nl && nr <= r){
root -> mul = (root -> mul * m) % mod;
root -> sum2 = (root -> sum2 * m % mod) * m % mod;
root -> sum = root -> sum * m % mod;
root -> add = root -> add * m % mod;
return ;
}
pushdown(root);
ll mid = (root -> l + root -> r) / 2;
if(r <= mid) mul(root -> lchild,l,r,m);
else if (l > mid) mul(root -> rchild,l,r,m);
else {
mul(root -> lchild,l,mid,m);
mul(root -> rchild,mid + 1,r,m);
}
pushup(root);
}

void query(Node *root,ll l,ll r){
ll nl = root -> l,nr = root -> r;
if(l <= nl && nr <= r){
ssum2 = (ssum2 + root -> sum2) % mod;
ssum = (ssum + root -> sum) % mod;
return ;
}
pushdown(root);
ll mid = (root -> l + root -> r) / 2;
if(r <= mid) query(root -> lchild,l,r);
else if (l > mid) query(root -> rchild,l,r);
else {
query(root -> lchild,l,mid);
query(root -> rchild,mid + 1,r);
}
}

int main(){
cin>>n>>q;
build(rt,1,n);
for(int i = 1;i<=q;i++){
cin>>o;
if(o == 4){
cin>>L>>R;
ll N = R - L + 1;
ssum = ssum2 = ans = 0;
query(rt,L,R);
ans = ((N * ssum2) % mod - (ssum * ssum) % mod + mod) % mod;
cout<<ans<<endl;
}
else{
cin>>L>>R>>k;
if(o == 1) add(rt,L,R,k);
else if(o == 2) mul(rt,L,R,k);
else if(o == 3){
mul(rt,L,R,0);
add(rt,L,R,k);
}
}
}
return 0;
}

B、给出一棵树,每条边都有一定的权值$w_i$,每次询问给出两个点$u、v$,要求输出从$u$到$v$的最短路径上的最小权值

树链剖分

看到的第一眼觉得是个树剖(虽然那个时候我已经忘了树剖怎么写),然后康到有人说lct,但是lct我写不来就先学树剖了,但是后面M题还是逃不过lct。。
先dfs一遍分出轻链和重链,第二次dfs给访问的链编号并且把链连接起来,然后放入线段树里进行查询维护
查询两个点的时候把它们两个一直往上提到同一条链上,查询对应区间上的最小值
因为query少写了个min一直没过去,感谢xyy帮我康了一下
查询的时间复杂度是$O (logn*logn) $(我证明不了(逃))<\del>

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
 struct Node{
int l,r;
int minn;
}tr[maxn * 5];

int n,q,u,v,w;
vector<Edge> G;
vector<int> edges[maxn];
int fa[maxn],siz[maxn],dep[maxn],minn[maxn],son[maxn],pos[maxn],top[maxn];
int mn[maxn],tid = 0;

void Addedge(int u,int v,int d){
G.push_back(Edge(u,v,d));
G.push_back(Edge(v,u,d));
edges[u].push_back(G.size() - 2);
edges[v].push_back(G.size() - 1);
}

void dfs1(int now,int pre,int deep){
fa[now] = pre;
siz[now]++;
dep[now] = deep;
int len = edges[now].size();
for(int i = 0;i<len;i++){
int v = G[edges[now][i]].to;
if(v == pre) continue;
minn[v] = G[edges[now][i]].dist;
dfs1(v,now,deep+1);
siz[now] += siz[v];
if(son[now] == -1 || siz[son[now]] < siz[v]) son[now] = v;
}
}

void dfs2(int now,int chain){
pos[now] = tid++;
top[now] = chain;
mn[pos[now]] = minn[now];
int len = edges[now].size();
if(son[now] == -1) return ;
dfs2(son[now],chain);
for(int i = 0;i<len;i++){
int v = G[edges[now][i]].to;
if(v != fa[now] && v != son[now]){
dfs2(v,v);
}
}
}

void build(int k,int l,int r){
tr[k].l = l;
tr[k].r = r;
if(l == r){
tr[k].minn = mn[l];
return ;
}
int mid = (l + r)/2;
build(k<<1,l,mid);
build(k<<1|1,mid + 1,r);
tr[k].minn = min(tr[k<<1].minn,tr[k<<1|1].minn);
}


int query(int s,int t,int l,int r,int k){
if(s == l&& t == r){
return tr[k].minn;
}
int mid = (l + r)>>1;
if(t <= mid) return query(s,t,l,mid,k<<1);
else if (s > mid) return query(s,t,mid+1,r,k<<1|1);
else return min(query(s,mid,l,mid,k<<1),query(mid + 1,t,mid + 1,r,k<<1|1));
}

int Query(int s,int t){
int ans = 1e9 + 7;
int chain1 = top[s],chain2 = top[t];
while(chain1 != chain2){
if(dep[chain1] < dep[chain2]) swap(chain1,chain2),swap(s,t);
if(chain1 == 1) ans = min(ans,query(pos[chain1] + 1,pos[s],1,tid - 1,1));
else ans = min(ans,query(pos[chain1],pos[s],1,tid-1,1));
s = fa[chain1];
chain1 = top[s];
}
if(s == t) return ans;
if(dep[s] > dep[t]) swap(s,t);
ans = min(ans,query(pos[son[s]],pos[t],1,tid - 1,1));
return ans;
}

int main(){
mst(son,-1);
cin>>n>>q;
for(int i = 1;i<n;i++){
cin>>u>>v>>w;
Addedge(u,v,w);
}
dfs1(1,0,1);
dfs2(1,1);
build(1,1,tid - 1);
for(int i = 1;i<=q;i++){
cin>>u>>v;
cout<<Query(u,v)<<endl;
}
return 0;
}

C、给出n个区间,对于每次给出的区间在覆盖之前的区间之后,输出连通区间数量

set 暴力求解

一开始我想的是利用并查集维护每个区间的连通性,然后用集合合并插入集合的左右区间,结果越写越复杂
突然想起来操作的方式可以直接单独使用set进行操作,对于每次插入的区间,先放到集合里面,然后再取出来,向左右两边合并之后放回集合,那么集合的大小就是连通区间的数量
合并的时候要向左合并到最左边的一个区间的右端点不再当前区间内部,向右边合并的时候到最右边的区间的左端点不在当前区间的内部
对于一个集合,其本质是红黑树,那么插入操作是$ O(logn) $的,查询操作也是$ O(logn) $的,而在合并操作的时候向左右合并的最坏情况是插入的时候之前都没有区间可以合并并且当前区间可以覆盖其他区间,那么最坏的情况下,总体的时间复杂度应该是$ O(nlogn) $其实我并不会分析时间复杂度<\del>

  • 对于区间按照其左右端点作为两个权值进行排序
  • 每次插入区间之后取出来进行合并
  • 左右区间合并要注意条件
    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
    struct node{
    pair<int,int> lr;
    int pos;

    bool operator < (const node b) const{
    return this -> lr < b.lr;
    }
    };

    set<node> all;
    vector<node> query;
    node tmp;
    int n;
    int ans = 0;

    int main(){
    cin>>n;
    for(int i = 0;i<n;i++){
    fa[i] = i;
    cin>>tmp.lr.first>>tmp.lr.second;
    tmp.pos = i;
    query.push_back(tmp);
    }
    all.insert(query[0]);
    ans ++;
    for(int i = 1;i<n;i++){
    all.insert(query[i]);
    set<node>::iterator now;
    now = all.find(query[i]);
    set<node>::iterator nxt;
    while(now != all.begin()){
    set<node>::iterator pre = now;
    pre --;
    node x = *pre,y = *now;
    if(x.lr.second < y.lr.first) break;
    all.erase(x);
    if(x.lr.second >= y.lr.first){
    x.lr.first = min(x.lr.first,y.lr.first);
    x.lr.second = max(x.lr.second,y.lr.second);
    all.erase(y);
    all.insert(x);
    now = all.find(x);
    }
    }
    nxt = now;
    nxt ++;
    while(nxt != all.end()){
    node x = *nxt,y = *now;
    if(x.lr.first > y.lr.second) break;
    all.erase(x);
    if(x.lr.first <= y.lr.second){
    x.lr.first = min(x.lr.first,y.lr.first);
    x.lr.second = max(x.lr.second,y.lr.second);
    all.erase(y);
    all.insert(x);
    now = all.find(x);
    nxt = now;
    nxt ++;
    }
    }
    cout<<ans<<" ";
    ans = all.size();
    }
    cout<<ans<<endl;
    return 0;
    }

D、给出一个n位的16进制数,输出取$k$位相对位置不变的最大的16进制数

贪心 stack

换一个思路,删除$ n - k $位数字,使得剩下的k位数的数值最大。那么就需要保证在前面的数字要尽量大,其实这里是和十进制下的删数问题是一个道理,只是用16进制进行表示而已。
考虑使用一个栈,当栈为空或者栈顶元素比要插入的元素小的时候,栈顶弹出,直到栈顶比要插入的数大的时候为止,然后插入这个元素,直到删去了$n - k $位之后,剩下的数全部进栈,那么就算一个最优解,显然时间复杂度可以做到$O(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
stack<int> all;
vector<int> ans;
int n,k;
char c;

int getnum(char c){
if(c <= '9' && c >= 0) return c - '0';
else return c-'a'+10;
}

char getc(int num){
if(num <= 9 && num >= 0) return '0'+num;
else return 'a'+num-10;
}

int main(){
while(cin>>n>>k){
k = n - k;
while(!all.empty()) all.pop();
ans.clear();
for(int i = 1;i<=n;i++){
cin>>c;
int tmp = getnum(c);
while(!all.empty() && all.top() < tmp && k > 0) all.pop(),k--;
all.push(tmp);
}
while(k) all.pop(),k--;
int len = all.size();
for(int i = 1;i<=len;i++){
ans.push_back(all.top());
all.pop();
}
for(int i = len - 1;i>=0;i--) cout<<getc(ans[i]);
cout<<endl;
}
return 0;
}

E、给出一个序列,每个数值为$v_i$,然后每次询问为$L、R$,第一次询问时令$ans = 0$,然后后面的询问区间是令$l = (L + ans - 1) % n + 1$、$r = (R + ans - 1) % n + 1$,$l > r$的时候,交换,然后正确的询问区间是$[l,r]$

分块 在线 区间众数
这题我一开始看的时候以为是要查找LIS的个数,但是后面发现和顺序无关,然后找到了一个洛谷上面的原题,那个题我一直TLE但是交过来就A了我也很懵潇神不要锤我,因为代码逻辑和正解的差不多,但是我的代码就会T,感觉自己撞了鬼emm
主要是分块,先选取一个块大小,将整个区间分开,然后依次处理一个块到另外一个块的众数的个数。
开一个vector存数字在序列中的位置,同时离散化的时候把位置存进去,那么在后面查询的时候,对于不在上面区间中的数字,依次处理,处理左边的时候,查询当前数的位置加上当前解的和对应在vector中的位置小于查询右边界的话答案加1,右边也类似。
时间复杂度是$ O((n + m) \sqrt 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
54
55
56
57
58
59
60
61
62
63
64
65
int n,m,l,r,anss = 0,siz = 150;
int A[maxn],a[maxn],block[maxn],cnt[maxn],pos[maxn];
int f[1000][1000];
int L[1000],R[1000];
vector<int> all[maxn];

void init(int now){
mst(cnt,0);
int mmax = 0;
for(int i = L[now];i <= n;i++){
cnt[a[i]] ++;
mmax = max(mmax,cnt[a[i]]);
if(i == R[block[i]]){
f[now][block[i]] = mmax;
}
}
}

int Query(int nowl,int nowr){
int res = 0;
if(block[nowl] == block[nowr]){
for(int i = nowl;i <= nowr;i++){
int len = all[a[i]].size();
while(pos[i] + res < len && all[a[i]][pos[i] + res] <= nowr) res++;
}
}
else{
if(block[nowl] + 1 < block[nowr]) res = f[block[nowl] + 1][block[nowr] - 1];
for(int i = nowl;i <= R[block[nowl]];i++){
int len = all[a[i]].size();
while(pos[i] + res < len && all[a[i]][pos[i] + res] <= nowr) res++;
}
for(int i = L[block[nowr]];i <= nowr;i++){
while(pos[i] >= res && all[a[i]][pos[i] - res] >= nowl) res++;
}
}
return res;
}

int main(){
cin>>n>>m;
for(int i = 1;i <= n;i++){
cin>>A[i];
a[i] = A[i];
}
sort(A + 1,A + n + 1);
for(int i = 1;i <= n;i++) {
a[i] = lower_bound(A + 1,A + n + 1,a[i]) - A;
all[a[i]].push_back(i);
pos[i] = all[a[i]].size() - 1;
}
for(int i = 1;i <= n;i++) block[i] = i / siz + 1;
for(int i = 1;i <= block[n];i++) L[i] = (i - 1) * siz + 1,R[i] = i * siz;
L[1] = 1;R[block[n]] = n;
for(int i = 1;i <= block[n];i++) init(i);
for(int i = 1;i <= m;i++){
cin>>l>>r;
l = (l + anss - 1) % n + 1;
r = (r + anss - 1) % n + 1;
if(l > r) swap(l,r);
anss = Query(l,r);
cout<<anss<<endl;
}
return 0;
}

F、与E题一样,给出一个序列,每个数值为$v_i$,然后每次询问为$L、R$,但是查询区间就是$[L,R]$,不需要在线查询

分块 莫队 区间众数

复习了一遍莫队算法。
将查询区间进行排序,然后用两个指针处理区间,开两个数组,一个维护某个数的出现次数,另外一个维护出现次数为某个值的数的个数的数组。然后对查询区间进行排序,用两个指针在数组上移动到查询区间,如果当前的众数个数变成0了的话答案减一,如果当前加进来的数大于答案的话答案更新。
时间复杂度$O(n \sqrt 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
54
55
56
57
58
59
60
61
int n,m,block;
int A[maxn],a[maxn],cnt[maxn],anss[maxn],sum[maxn];

struct query{
int l,r,id;

bool operator < (const query& a) const{
return (l / block == a.l / block) ? (r < a.r):(l / block < a.l / block);
}
}q[maxn];

int main(){
mst(sum,0);
mst(anss,0);
mst(cnt,0);
cin>>n>>m;
block = sqrt(n);
for(int i = 1;i <= n;i++){
cin>>A[i];
a[i] = A[i];
}
sort(A + 1,A + n + 1);
for(int i = 1;i <= n;i++) a[i] = lower_bound(A + 1,A + n + 1,a[i]) - A;
for(int i = 1;i <= m;i++){
cin>>q[i].l>>q[i].r;
q[i].id = i;
}
sort(q + 1,q + m + 1);
int l = 1,r = 0,ans = 0;
for(int i = 1;i <= m;i++){
while(l < q[i].l){
sum[cnt[a[l]]]--;
if(cnt[a[l]] == ans && !sum[cnt[a[l]]]) ans--;
sum[--cnt[a[l]]]++;
l++;
}
while(r > q[i].r){
sum[cnt[a[r]]]--;
if(cnt[a[r]] == ans && !sum[cnt[a[r]]]) ans--;
sum[--cnt[a[r]]]++;
r--;
}
while(l > q[i].l){
l--;
sum[cnt[a[l]]] --;
sum[++cnt[a[l]]] ++;
ans = max(ans,cnt[a[l]]);
}
while(r < q[i].r){
r++;
sum[cnt[a[r]]] --;
sum[++cnt[a[r]]] ++;
ans = max(ans,cnt[a[r]]);
}
anss[q[i].id] = ans;
}
for(int i = 1;i <= m;i++){
cout<<anss[i]<<endl;
}
return 0;
}

G、长度为n的数组和一个长度为n-1的数组,有两个操作,增大某个元素并对后续元素进行处理,查询求区间和

线段树 差分序列

这题得感谢hrdg提醒了差分
首先可以知道差分是类似这样:$d_i = a_i - a_{i - 1}$
那么要求一个区间的区间和,根据差分的定义,可以知道在一个差分数组中:

那么要求取一个区间和,可以考虑先求出前缀和

那么只需要维护差分数组的区间和以及$i * d_i$的区间和就可以了
这样的话开一个差分数组,对数的差分进行记录,然后再用线段树来维护区间和
每次对差分数组进行操作的时候,当修改这个值增大的时候,其后面的差分会减小,那么需要把后面的差分改成$b_i$,依次向后进行,直到某个位置差分大于等于$b _ i$的时候停止
然后对线段树进行修改,使得区间元素和差分数组对应区间相同,每次查询的时候查询左端点和右端点的前缀和相减一下即可
每次修改的复杂度是$O(nlogn)$,查询的复杂度是$O(logn)$
如果数据改得强的话我能被卡到$O(n^2logn)$,就是每次都是修改并且修改能从头改到位的情况。。
看了std,我的这是个假算法,还被xyy叫上去讲了一下,丢人QAQ
然而看了std现在我也不想改了。。就直接交这一个了。。

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
struct Node{
ll l,r;
ll sum1,sum2;
Node *lchild,*rchild;
};

ll n,q,a[maxn],b[maxn],L,R,p,x,op;
ll delta[maxn],ssum1,ssum2,ans;

Node *root = new Node;

void build(Node*root,ll l,ll r){
root -> l = l;
root -> r = r;
if(l == r){
root -> sum1 = delta[l];
root -> sum2 = delta[l] * l;
root -> lchild = root ->rchild = NULL;
return ;
}
root -> lchild = new Node;
root -> rchild = new Node;
ll mid = (l + r) / 2;
build(root -> lchild,l,mid);
build(root -> rchild,mid + 1,r);
root -> sum1 = root -> lchild -> sum1 + root -> rchild -> sum1;
root -> sum2 = root -> lchild -> sum2 + root -> rchild -> sum2;
}

void modify(Node *root,ll l,ll r){
if(root -> l == root -> r){
root -> sum1 = delta[l];
root -> sum2 = delta[l] * l;
return ;
}
ll mid = (root -> l + root -> r) / 2;
if(r <= mid) modify(root -> lchild,l,r);
else if(l > mid) modify(root -> rchild,l,r);
else{
modify(root -> lchild,l,mid);
modify(root -> rchild,mid+1,r);
}
root -> sum1 = root -> lchild -> sum1 + root -> rchild -> sum1;
root -> sum2 = root -> lchild -> sum2 + root -> rchild -> sum2;
}

void query(Node *root,ll l,ll r){
if(l <= root -> l && root -> r <= r){
ssum1 += root -> sum1;
ssum2 += root -> sum2;
return ;
}
ll mid = (root -> l + root -> r) / 2;
if(r <= mid) query(root -> lchild,l,r);
else if(l > mid) query(root -> rchild,l,r);
else {
query(root -> lchild,l,mid);
query(root -> rchild,mid+1,r);
}
}

ll getsum(ll x){
if(x == 0) return 0;
ll num;
ssum1 = ssum2 = 0;
query(root,1,x);
num = (x + 1)*ssum1 - ssum2;
return num;
}

int main(){
cin>>n;
for(int i = 1;i <= n;i++){
cin>>a[i];
delta[i] = a[i] - a[i -1];
}
for(int i = 2;i<=n;i++) cin>>b[i];
build(root,1,n);
cin>>q;
for(ll i = 1;i<=q;i++){
cin>>op;
if(op == 1){
cin>>p>>x;
delta[p] += x;
delta[p + 1] -= x;
ll rr = p;
for(ll j = p + 1;j <= n;j++){
if(delta[j] < b[j]){
ll de = b[j] - delta[j];
ll mul = de / b[j] + (de % b[j] != 0);
ll add = mul * b[j];
delta[j] += add;
delta[j + 1] -= add;
rr = j + 1;
}
else break;
}
modify(root,p,rr);
}
else{
cin>>L>>R;
ll sum1,sum2;
sum1 = getsum(L - 1);
sum2 = getsum(R);
ans = sum2 - sum1;
cout<<ans<<endl;
}
}
return 0;
}

H、给定一个长为n的序列,要求输出长度不超过m的子序列的最大值

单调队列

将问题转化为求一个单调上升的前缀和问题,因为要求子序列和最大值,那么只要前缀和在增加的话对应区间中的和就是在上升的。那么维护一个单调队列,每次在长度大于m的时候前面的出队列,后面的入队列的元素中有递减的就出队列,保证队列的单调性
时间复杂度$O(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
long long ans = 0;
int n,m,q[100007];
int l = 1,r = 1;
long long sum[100007];

int main(){
cin>>n>>m;
for(int i = 1;i<=n;i++){
cin>>sum[i];
sum[i] += sum[i - 1];
}
q[r++] = 0;
ans = sum[1];
for(int i = 1;i<=n;i++){
while(l < r && i - q[l] > m){
l++;
}
ans = max(ans,sum[i] - sum[q[l]]);
while(l < r && sum[q[r - 1]] >= sum[i]){
r--;
}
q[r++] = i;
}
cout<<ans<<endl;
return 0;
}

I、每次给出一个队伍的过题罚时,然后对过题数以及罚时进行排名,要求输出一号队伍每次的排名

Treap 平衡树

这题。。作死敲了一整天的splay心态爆炸最后写了个treap
把每个题当作一个二元组进行处理,重载一个比较符号,然后放到treap里面维护就行了
其他的操作和treap一样。。
查询,插入,删除操作的操作时间复杂度是$O(logn)$

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
struct Node{
int id,pass,time;
int siz;
Node *ch[2];

operator > (const Node a){
if(this -> time == a.time && this -> pass == a.pass) return this -> id > a.id;
else if(this -> pass == a.pass) return this -> time > a.time;
else return this -> pass < a.pass;
}

int cmp(int x,int pa,int ti){
if(pa == pass && ti == time && x == id) return -1;
else if(pa == pass && ti == time) return id > x ? 0 : 1;
else if(pa == pass) return time > ti ? 0 : 1;
else return pass < pa ? 0 : 1;
}

void maintain() {
siz = 1;
if(ch[0] != NULL) siz += ch[0]->siz;
if(ch[1] != NULL) siz += ch[1]->siz;
}
};

int a,b,m,n;
int pas[100007],tim[100007];

bool comp(Node *node,int x,int pa,int ti){
if(pa == node -> pass && ti == node -> time && x == node -> id) return -1;
else if(pa == node -> pass && ti == node -> time) return node -> id > x;
else if(pa == node -> pass) return node -> time > ti;
else return node -> pass < pa;
}

void rotate(Node* &o, int d){
Node* k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o;
o->maintain(); k->maintain(); o = k;
}

void insert(Node* &o,int x,int pa,int ti){
if(o==NULL){
o=new Node();
o -> ch[0]=o->ch[1]=NULL;
o -> id=x;
o -> pass = pa;
o -> time = ti;
o -> siz = 1;
}
else{
int d = o->cmp(x,pa,ti);
insert(o->ch[d],x,pa,ti);
if(o->ch[d] > o);
rotate(o,d^1);
}
o->maintain();
};

int tfind(Node *o,int x){
while(o != NULL){
int d = o -> cmp(x,pas[x],tim[x]);
if(d == -1) return 1;
else o = o -> ch[d];
}
return 0;
}

int query(Node *o,int x,int pa,int ti){
int res;
if(o->ch[0] == NULL)
res=0;
else
res=o->ch[0]->siz;
if(o -> id == x)
{
return res+1;
}
if(comp(o,x,pa,ti)) return query(o->ch[0],x,pa,ti);
return res + 1 + query(o->ch[1],x,pa,ti);
}

void remove(Node* &o,int x) {
int d = o->cmp(x,pas[x],tim[x]);
Node* u = o;
if(d == -1) {
if(o->ch[0] != NULL && o->ch[1] != NULL){
int d2 = o->ch[0] > o->ch[1] ? 1 : 0;
rotate(o,d2);
remove(o->ch[d2],x);
}
else {
if(o->ch[0] == NULL) o = o->ch[1]; else o = o->ch[0];
delete u;
}
}
else remove(o->ch[d],x);
if(o != NULL) o->maintain();
}

Node *root = NULL;

int main(){
cin>>n>>m;
insert(root,1,0,0);
int ans;
for(int i = 1;i <= m;i++){
cin>>a>>b;
if(tfind(root,a)) remove(root,a);
pas[a] += 1;
tim[a] += b;
insert(root,a,pas[a],tim[a]);
ans = query(root,1,pas[1],tim[1]);
cout<<ans<<endl;
}
return 0;
}

J、给出一个环形的序列,从1到n进行编号,选择m个不相邻的区域使得序列和最大

priority_queue 贪心

一开始能想到的算法是直接放到优先队列里面贪心,但是这样不能保证每次选取的是不相邻的,而且就算保证了不相邻也会使得出现这样一种情况,选取1 4的位置,这样的话中间空出两个位置不能选,这样会导致有解的情况出现无解。
然后我第二次修改了一下,每次插入的时候如果这个编号的位置边上被选择了就看被选择的这个区域它边上两个加起来是不是最优,如果是的话就把原来选择了的替换成它边上的两个,但是现在这样的话也不能保证区域不相邻。。
那么就考虑每次选择的时候把选择的区域和边上的三个区域缩成一个区域,然后再放入优先队列中,当然每次修改的时候要对原来的Node数组中的数据进行修改,后面操作的时候操作的只是优先队列中对应的编号。
时间复杂度$O(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
struct Node{
int value;
int id,pre,nxt;

bool operator < (const Node& a) const{
return this -> value < a.value;
}
}all[200007];

priority_queue<Node> q;
int n,m,maxx;
int now = 0,ans = -INF,max_cnt = 0,vis[200007];

int main(){
//freopen("std.in","r",stdin);
//freopen("std1.out","w",stdout);
cin>>n>>m;
for(int i = 0;i < n;i++){
cin>>all[i].value;
all[i].id = i;
all[i].pre = (i + n - 1) % n;
all[i].nxt = (i + 1) % n;
q.push(all[i]);
}
if(n / 2 < m){
cout<<"Error!"<<endl;
return 0;
}
int value_sum = 0,cnt = 0;
while(!q.empty() && cnt != m){
Node Now = q.top();
q.pop();
if(vis[Now.id]) continue;
now = Now.id;
value_sum += Now.value;
int pre = all[now].pre,nxt = all[now].nxt;
vis[pre] = vis[nxt] = 1;
all[now].value = all[pre].value + all[nxt].value - all[now].value;
all[now].nxt = all[nxt].nxt;
all[all[nxt].nxt].pre = now;
all[now].pre = all[pre].pre;
all[all[pre].pre].nxt = now;
q.push(all[Now.id]);
cnt ++;
}
max_cnt = cnt;
ans = value_sum;
cout<<ans<<endl;
return 0;
}

K、每次给出一个区间,表示这个区间的和是奇数或者是偶数,然后要求输出第一个不满足之前条件的询问的

区间并查集

用并查集,表示这个数到它父节点的和为奇数还是偶数,也就是模是0还是1,每次压缩路径的时候沿着父节点向上加和取模。
检查的时候对于相同的区间直接大减小然后取模运算验证,不同区间就进行合并
时间复杂度在多次操作之后压缩路径接近于线性。

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int fa[1000007],val[1000007];
int a,b,v,n,q;
string s;

int tfind(int x){
if(x != fa[x]){
int f = fa[x];
fa[x] = tfind(fa[x]);
val[x] = (val[x] + val[f]) % 2;
}
return fa[x];
}

int main(){
cin>>n>>q;
for(int i = 0;i <= n;i++){
fa[i] = i;
val[i] = 0;
}
for(int i = 1;i <= q;i++) {
cin>>a>>b>>s;
if(s == "odd") v = 1;
else v = 0;
int ta = tfind(a - 1), tb = tfind(b);
if ( ta == tb){
if((val[a - 1] + v) % 2 == val[b]) continue;
else {
cout<<i - 1<<endl;
return 0;
}
}
else {
fa[tb] = ta;
val[tb] = (val[a - 1] + v - val[b] + 2) % 2;
}
}
cout<<"ORZQHQH"<<endl;
return 0;
}

L、给定一个长度为$n$的数列,初始值都是0,有两种操作

op = 1、输入$ L、P、a、k、p $,表示给$ [L,p] $区间上依次加上一个首项为$ a $,公差为$k$的等差数列,然后给$ (p,R] $区间上依次加上一个以前一个加上数列的末项减去k为首项,$ -k $作为公差的等差数列
op = 2、输入$ L、R $,输出这个区间中最长的等差数列的长度

把数列直接加上去太麻烦了,那么考虑维护一棵差分线段树,令公差$d_i = a_{i} - a_{i - 1}$,存到线段树中。
线段树维护当前区间左边的值$ lval $,右边的值$ rval $,从左边开始最长的相等差分$ llen $,从右边开始的最长的相等差分$ rlen $,中间的最长的相等差分$ mlen $,区间长度$ size $,区间最长的相等差分长度$ maxlen $。
那么每次向上合并操作的时候,先看一下左右子树中间那个位置的树是不是相同的,如果是的话中间位置的长度就是左子树的右边长度加上右子树的左边长度,否则取两颗子树中间最长的长度
而对于左长度和右长度,先看左子树的左长度是不是等于区间长度,并且中间值是否相等,是的话就是左子树的左长度加上右子树的右长度,否则就直接是左子树的左长度,右长度同理
而左右的值直接pushup就行了。
pushdown是修改操作的时候的add操作,add操作后可以pushup维护长度,所以直接pushdown就可以。
修改的操作,把第一个直接加上首项$a$,然后区间内部直接$ +k $或者$ -k $就可以,注意对最后一个位置的操作是如果$R < n$的话就对$R + 1$的位置减去$a + k (2 p - L - R)$
查询的时候考虑到最长的差分可能在查询区间的第一个位置开始,那么在查询左右端点不相等的时候直接把左端点挪一个位置,然后结果加上一就是最后的答案
线段树维护,每次查询和修改时间复杂度$O (logn) $,m次操作,总时间复杂度应该是 $O(mlogn) $?(瞎分析的)
差分序列 线段树

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
int n,m,op,L,R,a,k,p;

struct Node{
int l,r,siz;
int add;
int lval,rval;
int llen,rlen,mlen,maxlen;
Node *lchild,*rchild;
};

Node *rt = new Node;


void pushup(Node *root){
root -> siz = root -> r - root -> l + 1;
root -> lval = root -> lchild -> lval;
root -> rval = root -> rchild -> rval;
root -> maxlen = max(root -> lchild -> maxlen,root -> rchild -> maxlen);
root -> siz = root -> r - root -> l + 1;
if(root -> lchild ->rval == root -> rchild -> lval) root -> mlen = root -> lchild -> rlen + root -> rchild -> llen;
else root -> mlen = max(root -> lchild -> rlen,root -> rchild -> llen);
if(root -> lchild -> llen == root -> lchild -> siz){
if(root -> lchild ->rval == root -> rchild -> lval) root -> llen = root -> lchild -> llen + root -> rchild -> llen;
else root ->llen = root -> lchild ->llen;
}
else root -> llen = root -> lchild -> llen;
if(root -> rchild -> llen == root -> rchild -> siz){
if(root -> lchild ->rval == root -> rchild -> lval) root -> rlen = root -> rchild -> rlen + root -> lchild -> rlen;
else root -> rlen = root -> rchild -> rlen;
}
else root -> rlen = root -> rchild -> rlen;
root -> maxlen = max(root -> maxlen,root -> llen);
root -> maxlen = max(root -> maxlen,root -> rlen);
root -> maxlen = max(root -> maxlen,root -> mlen);
}

void pushdown(Node *root){
root -> lchild -> add += root -> add;
root -> rchild -> add += root -> add;
root -> lchild -> lval += root -> add;
root -> lchild -> rval += root -> add;
root -> rchild -> lval += root -> add;
root -> rchild -> rval += root -> add;
root -> add = 0;
}

void build(Node *root,int l,int r){
root -> l = l;
root -> r = r;
root -> add = 0;
if(l == r){
root -> siz = 1;
root -> lval = root -> rval = root -> add= 0;
root -> llen = root -> rlen = root -> mlen = root ->maxlen = 1;
root -> lchild = root -> rchild = NULL;
return ;
}
int mid = (l + r) / 2;
root -> lchild = new Node;
root -> rchild = new Node;
build(root -> lchild,l,mid);
build(root -> rchild,mid + 1,r);
pushup(root);
}

Node get(Node *root){
Node res;
res.l = root -> l;
res.r = root -> r;
res.siz = root -> siz;
res.lval = root -> lval;
res.rval = root -> rval;
res.llen = root -> llen;
res.rlen = root -> rlen;
res.mlen = root -> mlen;
res.maxlen = root -> maxlen;
res.lchild = res.rchild = NULL;
return res;
}

Node cal(Node a,Node b){
Node res;
res.l = a.l;
res.r = b.r;
res.lval = a.lval;
res.rval = b.rval;
res.siz = a.siz + b.siz;
res.maxlen = max(a.maxlen,b.maxlen);
if(a.rval == b.lval){
res.mlen = a.rlen + b.llen;
if(a.llen == a.siz) res.llen = a.llen + b.llen;
else res.llen = a.llen;
if(b.rlen == b.siz) res.rlen = a.rlen + b.rlen;
else res.rlen = b.rlen;
}
else{
res.mlen = max(a.rlen,b.llen);
res.llen = a.llen;
res.rlen = b.rlen;
}
res.maxlen = max(res.maxlen,res.llen);
res.maxlen = max(res.maxlen,res.rlen);
res.maxlen = max(res.maxlen,res.mlen);
res.lchild = res.rchild = NULL;
return res;
}

Node query(Node *root,int l,int r){
if(l <= root -> l && root -> r <= r){
return get(root);
}
pushdown(root);
int mid = (root -> l + root -> r) / 2;
if(r <= mid) return query(root -> lchild,l,r);
else if(l > mid) return query(root -> rchild,l,r);
else{
Node left = query(root -> lchild,l,mid);
Node right = query(root -> rchild,mid + 1,r);
Node res = cal(left,right);
return res;
}

}

void modify(Node *root,int l,int r,int tag){
if(l <= root -> l && root -> r <= r){
root -> lval += tag;
root -> rval += tag;
root -> add += tag;
return ;
}
pushdown(root);
int mid = (root -> l + root -> r) / 2;
if(r <= mid) modify(root -> lchild,l,r,tag);
else if(l > mid) modify(root -> rchild,l,r,tag);
else{
modify(root -> lchild,l,mid,tag);
modify(root -> rchild,mid + 1,r,tag);
}
pushup(root);
}

int main(){
cin>>n>>m;
Node ans;
build(rt,1,n);
for(int i = 1;i<=m;i++){
cin>>op;
if(op == 0){
cin>>L>>R>>a>>k>>p;
modify(rt,L,L,a);
int lat = a + k *(2 *p - L - R);
if(R < n) modify(rt,R + 1,R + 1,-lat);
if(L < n) modify(rt,L + 1,p,k);
if(p < n)modify(rt,p + 1,R,-k);
}
else{
int L,R;
cin>>L>>R;
if(L == R){
cout<<1<<endl;
continue ;
}
L++;
ans = query(rt,L,R);
cout<<ans.maxlen + 1<<endl;
}
}
return 0;
}

M、给出一棵树,对树进行两个操作,一个是将某个点涂红,然后另外一个是查询一个点到最近的红点的距离

点分治
学会了点分治的骚操作(
在树上查找整棵树的中心,将重心作为树根将树转成有根树
但是这个题需要对点进行修改那么就把重心连起来变成点分树来搞
std的分块学不来
一开始想复杂了把对最近的红点的维护用优先队列来搞,后面想了想其实可以直接存储距离重心最近的距离
那么每次修改的时候就可以直接从这个点开始跳到父亲节点上进行更新,查询的时候依次查询更新即可(
分治树的深度不超过$ logn $,那么每次修改时间复杂度最多是$ O(logn) $,查询操作也是$ O(logn) $

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
vector<Edge> G;
vector<int> edges[maxn];

int n,m,u,v,op,x;
int root,sum;
int vis[maxn],sz[maxn],f[maxn],dep[maxn],color[maxn],nxt[maxn];
int mn[20][200007],pos[maxn],dfn = 0,bin[20],lo[200007],q[100007];

void Addedge(int u,int v){
G.push_back(Edge(u,v));
G.push_back(Edge(v,u));
edges[u].push_back(G.size() - 2);
edges[v].push_back(G.size() - 1);
}

void dfs(int now,int fa){
mn[0][++dfn] = dep[now];
pos[now] = dfn;
int len = edges[now].size();
for(int i = 0;i<len;i++){
int v = G[edges[now][i]].to;
if(v != fa){
dep[v] = dep[now] + 1;
dfs(v,now);
mn[0][++dfn] = dep[now];
}
}
}

int RMQ(int u,int v){
u = pos[u];
v = pos[v];
if(v < u) swap(u,v);
int t = lo[v - u + 1];
return min(mn[t][u],mn[t][v - bin[t] + 1]);
}

int dist(int u,int v){
return dep[u] + dep[v] - 2 * RMQ(u,v);
}


void getroot(int u,int fa){
sz[u] = 1;f[u] = 0;
int len = edges[u].size();
for(int i = 0;i < len;i++){
int v =G[edges[u][i]].to;
if(v == fa || vis[v]) continue;
getroot(v,u);
sz[u] += sz[v];
f[u] = max(f[u],sz[v]);
}
f[u] = max(f[u],sum - sz[u]);
if(!root || f[u] < f[root]) root = u;
}

void divide(int now,int fa){
nxt[now] = fa;vis[now] = 1;
int len = edges[now].size();
for(int i = 0;i < len;i++){
int v = G[edges[now][i]].to;
if(!vis[v]){
sum = sz[v];
root = 0;
getroot(v,now);
divide(root,now);
}
}
}

void init(){
mst(sz,0);
mst(f,0);
mst(vis,0);
mst(color,0);
mst(q,-1);
G.clear();
bin[0] = 1;
lo[0] = -1;
for(int i = 1;i<20;i++) bin[i] = bin[i - 1] << 1;
for(int i = 1;i<200000;i++) lo[i] = lo[i >> 1] + 1;
dfs(1,0);
for(int i = 1;i <= lo[dfn];i++){
for(int j = 1;j <= dfn;j++){
if(j + bin[i] - 1 <= dfn){
mn[i][j] = min(mn[i - 1][j],mn[i - 1][j + bin[i - 1]]);
}
}
}
root = 0;f[0] = INF;sum = n;
getroot(1,0);
divide(root,0);
color[1] = 1;
int now = 1;
while(now != 0){
q[now].push(dist(now,1));
now = nxt[now];
}
}

int min_dis(int now){
if(q[now] != -1) return q[now].top();
return INF;
}

int main(){
cin>>n>>m;
for(int i = 1;i<n;i++) {
cin>>u>>v;
Addedge(u,v);
}
init();
for(int i = 1;i<=m;i++){
cin>>op>>x;
if(op == 1){
if(color[x]) continue;
color[x] = 1;
int now = x;
while(now != 0){
int dis = dist(now,x);
if(q[now] == -1 || q[now] > dis){
q[now] = dis;
}
now = nxt[now];
}
}
else{
if(color[x]) cout<<0<<endl;
else{
int ans = INF;
int now = x;
while(now != 0){
ans = min(ans,dist(now,x) + min_dis(now));
now = nxt[now];
}
cout<<ans<<endl;
}
}
}
return 0;
}

N、对于区间进行操作,给出三种操作

op = 1,对给定区间内的数加上k
op = 2,输出给定区间的区间和
op = 3,输出给定区间的极差

线段树 lazy标记
lazy标记以前没学,所以第一发爆了一个裸的上去,果然3s都不够我跑
每次加的操作的时候,如果当前操作区间以及被要修改的区间覆盖的话那就直接对当前线段树节点维护信息操作就可以了,而要询问的时候再把标记下次传。。
查询修改复杂度$ O(logn) $
xyy良心题!

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
struct Node{
long long l,r;
long long add;
long long sum;
long long minn,maxx;
Node *lchild,*rchild;
};

long long n,q,o,l,r;
long long k;
long long ssum,maxx,minn;
Node *rt = new Node;

void build(Node *root,long long l,long long r){
root -> l = l;
root -> r = r;
root -> sum = root -> add = root -> minn = root -> maxx = 0;
if(l == r){
root -> lchild = root -> rchild = NULL;
return ;
}
long long mid = (l+r)/2;
root -> lchild = new Node;
root -> rchild = new Node;
build(root->lchild,l,mid);
build(root->rchild,mid+1,r);
}

void pushup(Node *root){
root -> sum = root -> lchild -> sum + root -> rchild -> sum;
root -> minn = min(root -> lchild -> minn,root -> rchild -> minn);
root -> maxx = max(root -> lchild -> maxx,root -> rchild -> maxx);
}

void pushdown(Node *root){
long long a = root -> add;
root -> lchild -> add += a;
root -> rchild -> add += a;
root -> lchild -> sum += a * (root -> lchild -> r - root -> lchild ->l + 1);
root -> rchild -> sum += a * (root -> rchild -> r - root -> rchild ->l + 1);
root -> lchild -> minn += a;
root -> rchild -> minn += a;
root -> lchild -> maxx += a;
root -> rchild -> maxx += a;
root -> add = 0;
}

void add(Node *root,long long l,long long r,long long a){
long long nl = root->l,nr = root->r;
if(l <= nl && nr <= r){
root->add += a;
root->sum += a*(nr - nl + 1);
root->minn += a;
root->maxx += a;
return ;
}
pushdown(root);
long long mid = (nl+nr)/2;
if(r <= mid) add(root->lchild,l,r,a);
else if (l > mid) add(root->rchild,l,r,a);
else{
add(root->lchild,l,mid,a);
add(root->rchild,mid+1,r,a);
}
pushup(root);
}

void query(Node* root,long long l,long long r){
long long nl = root->l,nr = root->r;
if(l <= nl && nr <= r){
ssum += root->sum;
minn = min(minn,root->minn);
maxx = max(maxx,root->maxx);
return ;
}
pushdown(root);
long long mid = (nl + nr)/2;
if(r<=mid) query(root->lchild,l,r);
else if(l>mid) query(root->rchild,l,r);
else{
query(root->lchild,l,mid);
query(root->rchild,mid+1,r);
}
}

int main(){
//freopen("std.in","r",stdin);
//freopen("std2.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q;
build(rt,1,n);
for(int i = 1;i<=q;i++){
cin>>o;
if(o == 1){
cin>>l>>r>>k;
add(rt,l,r,k);
}
else{
cin>>l>>r;
ssum = 0;
minn = INF;
maxx = -INF;
query(rt,l,r);
if(o == 2) cout<<ssum<<endl;
else cout<<maxx - minn<<endl;
}
}
return 0;
}

O、给定三种操作,主要对一个集合进行操作

o = 1、把整数x加入到集合中
o = 2、把整数x从集合移出
o = 3、输出集合中与x异或后最大的结果及最小的结果

Trie树 位运算
用Trie树维护每个插入的数,查询的时候按照位运算进行,查最小值就顺着与当前位相同的边走,查最大值就顺着不同的走,建树要从高位开始。。一开始我从低位开始导致会到一个局部最优解(甚至错解)
每次操作时间复杂度最大$ O(32) $,总时间复杂度$ O(32n) $

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
struct Node{
int cnt;
bool value;
Node *next[2]; // lchild 0 rchild 1
};

Node *rt = new Node;

void insert(Node *root,int u){
Node *Now = root;
int tmp = u;
for(int i = 31;i>=0;i--){
int x = (u >> i) & 1;
if(Now -> next[x] == NULL){
Node *newnode = new Node;
newnode -> cnt = 0;
newnode -> value = x;
newnode -> next[0] = NULL;
newnode -> next[1] = NULL;
Now -> next[x] = newnode;
}
Now = Now -> next[x];
Now -> cnt ++;
}
}

void Delete(Node *root,int u,int pos){
if(pos == -1){
root -> cnt --;
return ;
}
int x = (u >> pos) & 1;
Delete(root -> next[x],u,pos-1);
root -> cnt--;
if(root -> next[x] -> cnt == 0){
delete root -> next[x];
root -> next[x] = NULL;
}
}

int Search1(Node *root,int v) //异或后最小
{
int res = 0;
Node *Now = root;
for(int i = 31;i>=0;i--){
int x = (v >> i) & 1;
if(Now -> next[x] != NULL){
Now = Now -> next[x];
if(Now -> value > 0) res += 1<<i;
}
else{
Now = Now -> next[!x];
if(Now -> value > 0) res += 1<<i;
}
}
return res;
}

int Search2(Node *root,int v) //异或后最大
{
int res = 0;
Node *Now = root;
for(int i = 31;i>=0;i--){
int x = (v >> i) & 1;
x = !x;
if(Now -> next[x] != NULL){
Now = Now -> next[x];
if(Now -> value > 0) res += 1<<i;
}
else{
Now = Now -> next[!x];
if(Now -> value > 0) res += 1<<i;
}
}
return res;
}

void init(){
rt -> next[0] = rt -> next[1] = NULL;
rt -> cnt = 0;
}

int n;
int o,v;

int main(){
cin>>n;
init();
for(int i = 1;i<=n;i++){
cin>>o>>v;
if(o == 1) insert(rt,v);
else if(o == 2) Delete(rt,v,31);
else if(o == 3){
int ans1 = Search1(rt,v) ^ v,ans2 = Search2(rt,v) ^ v;
cout<<ans1<<" "<<ans2<<endl;
}
}
return 0;
}