D

给定两个数组,a,b,每次可以交换两数组的各一个元素
求k(k<=2)交换内使得$|sum_a - sum_b|$最小

二分

k<2次的情况直接暴力枚举,k=2时,预处理所有的$2(a_i + a_j)$,枚举$b_i + b_j$,在预处理出的数组中二分$sum_a - sum_b + 2(b_i + b_j)$
复杂度 $O(m^2log(n^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
73
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 2010;
int n,m,k;
int pa[2],pb[2];
LL sa,sb,cur,ta,a[maxn],b[maxn];

vector<LL> V;

int main()
{
//freopen("test.txt","r",stdin);
sa = sb = 0;
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%lld",a+i),sa += a[i];
scanf("%d",&m);
for(int i=0;i<m;++i) scanf("%lld",b+i),sb += b[i];
k = 0; cur = abs(sa - sb);
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
if(cur > abs(sa + 2*b[j] - sb - 2*a[i]))
{
k = 1;
cur = abs(sa + 2*b[j] - sb - 2*a[i]);
pa[0] = i+1,pb[0] = j+1;
}

// for(int i=0;i<pn;++i) printf("%d ",V[i]);
if(n > 1)
{
for(int i=0;i<n;++i)
for(int j=i+1;j<n;++j)
V.push_back(2*(a[i]+a[j]));
sort(V.begin(),V.end());
int pn = unique(V.begin(),V.end()) - V.begin();

for(int i=0;i<m;++i)
for(int j=i+1;j<m;++j)
{
LL bb = 2*(b[i] + b[j]),aa;
//printf("%lld\n",sa - sb + bb);
vector<LL>::iterator p = lower_bound(V.begin(),V.begin()+pn,sa - sb + bb);
if(p == V.end()) --p;
if(p == V.begin()) aa = *p;
else aa = abs(sa + bb - sb - *p) > abs(sa + bb - sb - *(p-1)) ?*(p-1):*p;
if(cur > abs(sa + bb - sb - aa))
{
k = 2;
cur = abs(sa + bb - sb - aa);
pb[0] = i+1;
pb[1] = j+1;
ta = aa;
}
}
}
if(k == 2)
{
for(int i=0;i<n;++i)
for(int j=i+1;j<n;++j)
if(a[i] + a[j] == ta/2)
{
pa[0] = i+1;
pa[1] = j+1;
}
}
printf("%lld\n",cur);
printf("%d\n",k);
for(int i=0;i<k;++i)
printf("%d %d\n",pa[i],pb[i]);
return 0;
}

E

一棵树,每个节点上有不同颜色
每次询问: 以当前节点为根的子树的颜色种类
每次更新: 以当前节点为根的子树节点为同一个指定颜色。

线段树

维护树的先序遍历序列的线段树,可以发现每次更新和查询的区间都是连续的。
用bitmask表示不同颜色。
复杂度$nlog(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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 4e5 + 10;
int n,m;
struct Node{
LL mark,bit;
} node[maxn<<2];

int col[maxn],q[maxn],l[maxn],r[maxn],tot = 0;
vector<int> G[maxn];

void dfs(int u,int fa)
{
l[u] = ++tot;
q[tot] = u;
for(int i=0;i<G[u].size();++i)
{
int v = G[u][i];
if(v == fa) continue;
dfs(v,u);
}
r[u] = tot;
}

void pushdown(int u)
{
if(node[u].mark)
{
node[u<<1].bit = node[u<<1|1].bit = node[u<<1].mark = node[u<<1|1].mark = node[u].mark;
node[u].mark = 0;
}
}

void pushup(int u)
{
node[u].bit = node[u<<1].bit | node[u<<1|1].bit;
}

void build(int L,int R,int u)
{
node[u].mark = 0;
if(L == R)
{
node[u].bit = 1LL << col[q[L]-1];
return ;
}
int m = (L+R)>>1;
build(L,m,u<<1);
build(m+1,R,u<<1|1);
pushup(u);
}

void update(int cL,int cR,int col,int L,int R,int u)
{
if(cL <= L && R <= cR)
{
node[u].bit = node[u].mark = 1LL<<col;
return ;
}
pushdown(u);
int m = (L+R)>>1;
if(m >= cL) update(cL,cR,col,L,m,u<<1);
if(m < cR) update(cL,cR,col,m+1,R,u<<1|1);
pushup(u);
}

LL query(int cL,int cR,int L,int R,int u)
{
if(cL <= L && R <= cR)
return node[u].bit;
pushdown(u);
LL res = 0;
int m = (L+R)>>1;
if(m >= cL) res |= query(cL,cR,L,m,u<<1);
if(m < cR) res |= query(cL,cR,m+1,R,u<<1|1);
return res;
}

int main()
{
//freopen("test.txt","r",stdin);
scanf("%d %d",&n,&m);
for(int i=0;i<n;++i) scanf("%d",col+i);
for(int i=0;i<n-1;++i)
{
int u,v;
scanf("%d %d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,1);
build(1,n,1);
for(int i=0;i<m;++i)
{
int op,u,col;
scanf("%d",&op);
if(op == 1)
{
scanf("%d %d",&u,&col);
update(l[u],r[u],col,1,n,1);
}
else
{
scanf("%d",&u);
printf("%d\n",__builtin_popcountll(query(l[u],r[u],1,n,1)));
}
}
return 0;
}