2022”杭电杯“中国大学生算法设计超级联赛（2）1 3 11题解

1001-Static Query on Tree

题目大意：
有一棵树，根为1，以及三个点集合A、B、C，问树上有多少个点同时满足以下条件：

1. 在A中至少一点到1的路径上
2. 在B中至少一点到1的路径上
3. 在C中至少一点的子树中

思路：
对这棵树进行树链刨分，然后将A和B中点到1的路径打上A和B标记，在C的子树上打上C标记，然后统计同时拥有三种标记的点数量。
维护标记可以用线段树，将A标记记为1，B标记记为2，C标记记为4，当一个区间的与值为7时，说明这个区间的所有点都含有三种标记。当一个区间的或值不等于7时，说明这个区间里没有一个点拥有三种标记，就不用继续访问了（优化，否则TLE）。
另一种做法是当区间最小值为7时说明这个区间的所有点都符合，当区间最大值不等于7时说明没有点符合，两种做法理应是相同的，但是用最值的代码WA了，目前还没找到WA的原因。

AC代码：

#include 
const int N = 2e5 + 5;
using namespace std;

vector<int> son[N];
int fa[N], sz[N], mson[N], top[N], id[N], tot;
int minval[N * 4], maxval[N * 4], lazy[N * 4], clr[N * 4]; // clr为清除标记，将子树全部清0
void dfs1(int u)
{
    sz[u] = 1;
    mson[u] = 0;
    for (auto v : son[u])
    {
        fa[v] = u;
        dfs1(v);
        sz[u] += sz[v];
        if (sz[v] > sz[mson[u]]) mson[u] = v;
    }
}
void dfs2(int u, int t)
{
    top[u] = t;
    id[u] = ++tot;
    if (!mson[u]) return;
    dfs2(mson[u], t);
    for (auto v : son[u])
        if (v != mson[u])
            dfs2(v, v);
}
void pushdown(int u)
{
    if (clr[u])
    {
        clr[u] = 0;
        clr[u << 1] = 1;
        clr[(u << 1) | 1] = 1;
        lazy[u << 1] = 0;
        lazy[(u << 1) | 1] = 0;
        minval[u << 1] = 0;
        minval[(u << 1) | 1] = 0;
        maxval[u << 1] = 0;
        maxval[(u << 1) | 1] = 0;
    }
    if (lazy[u])
    {
        lazy[u << 1] |= lazy[u];
        minval[u << 1] |= lazy[u];
        maxval[u << 1] |= lazy[u];
        lazy[(u << 1) | 1] |= lazy[u];
        minval[(u << 1) | 1] |= lazy[u];
        maxval[(u << 1) | 1] |= lazy[u];
        lazy[u] = 0;
    }
}
void update(int u, int l, int r, int L, int R, int val)
{
    if (l <= L && r >= R)
    {
        minval[u] |= val;
        maxval[u] |= val;
        lazy[u] |= val;
        return;
    }
    pushdown(u);
    int mid = (L + R) / 2;
    if (l <= mid) update(u << 1, l, r, L, mid, val);
    if (r > mid) update((u << 1) | 1, l, r, mid + 1, R, val);
    minval[u] = minval[u << 1] & minval[(u << 1) | 1];
    maxval[u] = maxval[u << 1] | maxval[(u << 1) | 1];
}
int query(int u, int L, int R)
{
    if (minval[u] == 7)
        return R - L + 1;
    if (L == R) return (minval[u] == 7);
    pushdown(u);
    int res = 0, mid = (L + R) / 2;
    if (maxval[u << 1] == 7) res += query(u << 1, L, mid);
    if (R > mid && maxval[(u << 1) | 1] == 7) res += query((u << 1) | 1, mid + 1, R);
    return res;
}

void solve()
{
    int n, q, x, cnta, cntb, cntc;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        son[i].clear();
    for (int i = 2; i <= n; i++)
    {
        cin >> x;
        son[x].push_back(i);
    }
    dfs1(1);
    dfs2(1, 1);
    while (q--)
    {
        clr[1] = 1; //每次询问前清除线段树的值
        lazy[1] = maxval[1] = minval[1] = 0;
        cin >> cnta >> cntb >> cntc;
        while (cnta--)
        {
            cin >> x;
            while (top[x] != 1) //将路径区间打上A标记
            {
                update(1, id[top[x]], id[x], 1, n, 1);
                x = fa[top[x]];
            }
            update(1, 1, id[x], 1, n, 1);
        }
        while (cntb--)
        {
            cin >> x;
            while (top[x] != 1) //将路径区间打上B标记
            {
                update(1, id[top[x]], id[x], 1, n, 2);
                x = fa[top[x]];
            }
            update(1, 1, id[x], 1, n, 2);
        }
        while (cntc--)
        {
            cin >> x; //将子树打上C标记
            update(1, id[x], id[x] + sz[x] - 1, 1, n, 4);
        }
        cout << query(1, 1, n) << "\n";
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
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

1003-Copy

题目大意：
给定一个序列，提供两种操作：

1. 选择一个区间[l,r]，将这个区间复制后插入到区间[l,r]后面。
2. 选择当前序列的第x个数。

输出选择的数字的异或和。

思路：
因为是作异或操作，一个数字如果被选了偶数次，对答案是没有贡献的。
所以只要记录最后每个数字对答案是否有贡献即可。可以用bitset来记录。
从后往前看，如果操作1的区间是[l,r]，那么将[r+1,n]的位右移r-l+1位就是对应原序列的位置。
因为题目中1操作不会超过20000次，因此复杂度是O(20000*n/64)
由于bitset不能对某段区间进行移位操作，因此要先取得高位移位后再与低位进行异或操作。

AC代码：

#include 
const int N = 1e5 + 5;
using namespace std;

int a[N], op[N], l[N], r[N];

void solve()
{
    int n, q, ans = 0;
    bitset<N> f;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= q; i++)
    {
        cin >> op[i];
        if (op[i] == 1)
            cin >> l[i] >> r[i];
        else
            cin >> l[i];
    }
    for (int i = q; i >= 1; i--)
    {
        if (op[i] == 1)
        {
            bitset<N> high, low;
            high.set();
            low.set();

            high <<= (r[i] + 1); //保留高位的1
            high &= f; //取得[r+1,N]的位
            high >>= (r[i] - l[i] + 1);//[r+1,N]进行右移

            low >>= (N - r[i] - 1); //保留低位的1时要减1,因为N比最大的下标大1
            low &= f; //取[1,r]的位

            f = high ^ low; //得到高位右移后的结果
        }
        else
            f[l[i]] = !f[l[i]];
    }
    for (int i = 1; i <= n; i++)
        if (f[i]) ans ^= a[i];
    cout << ans << "\n";
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
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

1011-DOS Card

题目大意：
有一个序列x，给定一个区间[l,r]，从这个区间中选出四个位置a,b,c,d，要求a

• (x_a + x_b)(x_a - x_b) + (x_c + x_d)(x_c - x_d)
• (x_a + x_c)(x_a - x_c) + (x_b + x_d)(x_b - x_d)

求出最大值。
换一种描述，也就是选出两个组合，算两个组合的平方差之和。组合可以是(a,b)、(c,d)或(a,c)、(b,d)。

思路：
如果不限定计算方式的话，只要用线段树维护区间的最大值、次大值、最小值、次小值即可。
但是限定了计算方式后，选出了最大值和最小值，次大值和次小值不一定可选。
因为对顺序有影响，所以考虑区间合并，用i代表平方和中加的数字，j代表平方和中减的数字，那么就只有i i j j或i j i j的组合。
i i j j的组合可以是：

• 左子树：i i j j
• 左子树：i i j 右子树：j
• 左子树：i i 右子树：j j
• 左子树：i 右子树：i j j
• 右子树：i i j j

i j i j的组合可以是：

• 左子树：i j i j
• 左子树：i j i 右子树：j
• 左子树：i j 右子树：i j
• 左子树：i 右子树：j i j
• 右子树：i j i j

同样的，对于i i j之类的组合还可以继续细分

最后得到在线段树中，每个结点要维护的值有：

• i、j
• i i、j j、i j、j i
• i i j、i j j、i j i、j i j
• i i j j、i j i j

官方题解的做法是维护8个值，上面这种方法虽然维护的值更多，但是便于理解。

AC代码：

#include 
#define ls (u << 1)
#define rs ((u << 1) | 1)
const long long inf = 1e18 + 7;
const int N = 2e5 + 5;
using namespace std;

long long x[N];
namespace segtree
{
    struct node
    {
        long long i, j, ii, jj, ij, ji, iij, ijj, iji, jij, iijj, ijij;
        node() { i = j = ii = jj = ij = ji = iij = ijj = iji = jij = iijj = ijij = -inf; }
        long long ans() { return max(iijj, ijij); }
    } t[N * 4];
    node merge(node a, node b) //区间合并
    {
        node res;
        res.i = max(a.i, b.i);
        res.j = max(a.j, b.j);
        res.ii = max({a.ii, b.ii, a.i + b.i}); // C++11可以用花括号给max函数传入多个值
        res.jj = max({a.jj, b.jj, a.j + b.j});
        res.ij = max({a.ij, b.ij, a.i + b.j});
        res.ji = max({a.ji, b.ji, a.j + b.i});
        res.iij = max({a.iij, b.iij, a.i + b.ij, a.ii + b.j});
        res.ijj = max({a.ijj, b.ijj, a.i + b.jj, a.ij + b.j});
        res.iji = max({a.iji, b.iji, a.i + b.ji, a.ij + b.i});
        res.jij = max({a.jij, b.jij, a.j + b.ij, a.ji + b.j});
        res.iijj = max({a.iijj, b.iijj, a.i + b.ijj, a.ii + b.jj, a.iij + b.j});
        res.ijij = max({a.ijij, b.ijij, a.i + b.jij, a.ij + b.ij, a.iji + b.j});
        return res;
    }

    void build(int u, int L, int R)
    {
        if (L == R)
        {
            t[u].i = x[L];
            t[u].j = -x[L];
            t[u].ii = t[u].jj = t[u].ij = t[u].ji = t[u].iij = t[u].ijj = t[u].iji = t[u].jij = t[u].iijj = t[u].ijij = -inf;
            return;
        }
        int mid = (L + R) / 2;
        if (L <= mid) build(ls, L, mid);
        if (R > mid) build(rs, mid + 1, R);
        t[u] = merge(t[ls], t[rs]);
    }
    node query(int u, int l, int r, int L, int R)
    {
        if (L >= l && R <= r)
            return t[u];
        int mid = (L + R) / 2;
        if (r <= mid)
            return query(ls, l, r, L, mid);
        else if (l > mid)
            return query(rs, l, r, mid + 1, R);
        else
            return merge(query(ls, l, r, L, mid), query(rs, l, r, mid + 1, R));
    }
}

void solve()
{
    int n, q, l, r;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i];
        x[i] *= x[i]; //直接取平方值
    }
    segtree::build(1, 1, n);
    while (q--)
    {
        cin >> l >> r;
        cout << segtree::query(1, l, r, 1, n).ans() << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
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