May 2022 Algorithm Solution

Treelabeling

题目链接：https://codeforces.com/contest/1605/problem/D
题目大意：A 和 B 在树上玩博弈，两个人每次行动都要在树上选择一个节点。A 先手，第一步可以选择任意的节点。定义 $u$ 为上一步选择的节点， $v$ 为下一步将要选择的节点。那么要选择 $v$ 必须满足

• $u$ 与 $v$ 相邻
• $v$ 没有被任何人选择过
• $u\oplus v \leq min(u,v)$

两个人都极其聪明，无法操作的玩家输。在开始之前，A 可以将树上节点权值重新标记，使其变成 1 到 n 的一个全排列。A 想在第一回合中最大化可以选择的节点数量，这将保证他获胜。帮助 A 找到任何可以帮助他这样做的重新标记

解题思路：对于 $u\oplus v \leq min(u,v)$ 我们发现 $u,v$ 的最高位相同时满足，反之则不然。因此我们可以联想到二分图染色，划分成白点和黑点，假设白点是数量小的那部分，要让每个白点和它每一个相邻黑点的最高为都不相同。设白点的数量为 $m$ ，转换成二进制，如果某一位为 1 ，就把所有这一位为 1 且该位是最高位的点染成白色，例如 $m=6$ ，那么$\{2,3,4,5,6,7\}$ 都要是白点。剩下的染成黑色即可，这样不管选择哪个点，都是先手获胜

int n,color[N],cnt[60],ans[N];
vector<int>w,b;
set<int>t;
vector<int>G[N];
void dfs(int u,int fa,int c){
    color[u]=c;
    if(c) w.emplace_back(u);
    else b.emplace_back(u);
    for(auto v:G[u]){
        if(v==fa) continue;
        dfs(v,u,c^1);
    }
}
void solve(){    
    cin>>n;
    string s="";
    w.clear();
    b.clear();
    lep(i,0,50) cnt[i]=0;
    lep(i,1,n) color[i]=-1,G[i].clear(),t.insert(i),ans[i]=0;
    lep(i,2,n){
        int u,v;cin>>u>>v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }dfs(1,0,0);
    if(w.size()>b.size()) swap(w,b);
    int len=w.size();
    while(len){
        if(len&1) s+='1';
        else s+='0';
        len/=2;
    }if(!s.empty()) lep(i,0,s.size()-1)cnt[i]=s[i]=='1';
    int k=0;
    lep(i,0,50){
        if(cnt[i]){
            int l=1<<i;
            int r=(1<<(i+1))-1;
            lep(j,l,r){
                ans[w[k++]]=j;
                t.erase(j);
            }
        }
    }
    lep(i,1,n){
        if(!ans[i]){
            ans[i]=(*t.begin());
            t.erase(t.begin());
        }
    }
    lep(i,1,n) cout<<ans[i]<<' ';
    cout<<'\n';
}

Anonymity Is Important

题目链接：https://codeforces.com/contest/1642/problem/E

题目大意：有 n 个人，可以知道 $[l,r]$ 里面有没有病人，判断某个人有没有生病

解题思路：首先定义 set，把所有人放进去，为了防止访问错误，可以把不可能出现的最小值和最大值放进去，如果 $[l,r]$ 里面没有病人，那么就把 l 到 r 从 set 里面删掉

定义 map 储存区间，如果 $[l,r]$ 有病人，那么 map[l]=r ,当遇到 $[l,r]$ 里面有病人的话，如果存在 $[l,r]$ 的子集，则该信息无用，否则加入该区间，再把覆盖此区间的大区间删除

查询的时候，如果他不在 set 里面就是没有病，否则在 set 里面找到离他最近的两个人 $L,R$，通过 map 判断有没有一个区间 $l,r$ ，满足 $L<l\le r<R$，如果存在这样的区间，那么他就是病人，否则就是不确定

int n,q;
set<int>s;
map<int,int>m;
void solve(){
    cin>>n>>q;
    lep(i,0,n+1) s.insert(i);
    while(q--){
        int opt;cin>>opt;
        if(opt){
            int x;cin>>x;
            if(s.find(x)==s.end()) cout<<"NO"<<'\n';
            else{
                auto l=*prev(s.find(x));
                auto r=*next(s.find(x));
                auto it=m.upper_bound(l);
                if(it!=m.end()&&it->first<=x&&it->second<r) cout<<"YES"<<'\n';
                else cout<<"N/A"<<'\n';
            }
        }
        else{
            int l,r,x;cin>>l>>r>>x;
            if(x){
                auto it=m.lower_bound(l);
                if(it!=m.end()&&(it->second)<=r) continue;
                m[l]=r;
                it=m.find(l);
                while(it!=m.begin()&&prev(it)->second>=r)
                m.erase(prev(it));
            }
            else{
                while(1){
                    auto it=s.lower_bound(l);
                    if((*it)>r) break;
                    s.erase(it);
                }
            }
        }
    }
}

Hemose on the Tree

题目链接：https://codeforces.com/contest/1670/problem/E

题目大意：给你 n 个节点的树，把 $[1,2n-1]$ 的权值分配给树上的节点和边。然后你可以选择任意一个点当根，要求根节点到任意点或边的最短路径异或和的最大值最小

解题思路：首先异或和的最小值不小于 n，因为要满足小于 n ，那么根节点的权值就得小于 n ,然后其它的节点和边的最高位都不能为 1，而这显然是不可能的。我们把剩下来的权值处理一下，让 ${x,x+n}$ 凑成一对，这样它们异或就是 n ，总共又有偶数个，现在只要分配得当就可以得到答案的最小值 n 。让根节点的权值就为 n ,它到每个节点的异或和要么为 0，要么为 n 。如果当前走到的子节点的异或值为 0 ,那么接下来的边权就要小于 n ，否则大于 n，这样构造即可。

struct edge {
    int to, next, w;
} edge[N];
int n, l, r;
int head[N];
int wx[N], wy[N];
int cnt;
void init(int n) {
    for (int i = 0; i <= n; i++) {
        edge[i].next = -1;
        head[i] = -1;
    }
    cnt = 0;
}
void add(int u, int v, int w) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
void solve() {
    cin >> n;
    n = 1 << n;
    l = 1, r = n + 1;
    init(n);
    lep(i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        add(u, v, i);
        add(v, u, i);
    }
    wx[1] = n;
    function<void(int, int)> dfs = [&](int u, int fa) {
        for (int i = head[u]; ~i; i = edge[i].next) {
            int y = edge[i].to, z = edge[i].w;
            if (y == fa) continue;
            if (wx[u] >= n) {
                wy[z] = r;
                wx[y] = l;
                r++;
                l++;
            } else {
                wy[z] = l;
                wx[y] = r;
                l++;
                r++;
            }
            dfs(y, u);
        }
    };
    dfs(1, 0);
    cout << 1 << endl;
    lep(i, 1, n) cout << wx[i] << " ";
    cout << endl;
    lep(i, 1, n - 1) cout << wy[i] << " ";
    cout << endl;
}

Increasing Array Queries

题目链接：https://cses.fi/problemset/task/2416

题目大意：给你一个数组，两种操作

• 区间加 $[1,2,..r-l+1]$
• 区间变成非递减数组的最小操作数，每次操作选择一个数加一

解题思路：在这个问题上，我们可以离线回答查询（即读入查询并以不同的顺序处理它们）。更具体地说，我们按照 $l$ 的顺序来处理查询。

首先，让我们思考一下我们如何回答一个单一的查询 $[l，r]$ ，考虑以下算法：

让 $mx_0=0，j=0$ ，对于 $[l, r]$ 中的每个 $i$

如果 $x_i>mx_j$ ，则令 $mx_{j+1}=x_i$ ，并增加 $j$
否则，在答案中加入 $mx_j - x_i$。

注意每个 $mx_j$（除了最后一个）对答案的贡献都是固定的，与 $r$ 无关。
如果 $pref$ 是 $x$ 的前缀和数组，$idx_j$ 是 $mx_j$ 在 $x$ 中的索引，那么这个贡献就是

$(idx_j + 1 - 1 - idx_j)*mx_j - (pref_{idx_j + 1} - 1 - pref_{idx_j})$

相当于在 $m_{j}$ 和 $m_{j+1}$ 之间所有的 $x_i$ 都变成 $m_{j}$ 的花费

这意味着，对于一个固定的 $l$，我们可以计算每个 $mx_j$ 和它们的贡献，然后使用 upper_bound 和一个 BIT 来回答询问 $r$

如果我们想改变 $l$，注意我们如何通过使用单调堆栈有效地更新 $mx$ 。
使用一个单调的堆栈，因为每个 $mx_j$ 的贡献都取决于它后面的 $x_i$ 之后，旧的 $mx_j$ 的贡献不会改变。

同样，我们使用 upper_bound 和一个 BIT 来回答查询

ll n, q;
ll a[N], pre[N], v[N], ans[N], BIT[N];
vector<PII> que[N];
void add(int p, ll d) {
    for (; p <= n; p += low(p)) {
        BIT[p] += d;
    }
}
ll query(int p) {
    ll sum = 0;
    for (; p; p -= low(p)) {
        sum += BIT[p];
    }
    return sum;
}
void solve() {
    cin >> n >> q;
    lep(i, 1, n) cin >> a[i], pre[i] = a[i] + pre[i - 1];
    a[n + 1] = INF, pre[n + 1] = pre[n] + a[n + 1];
    lep(i, 1, q) {
        int l, r;
        cin >> l >> r;
        que[l].emplace_back(r, i);
    }
    deque<int> st;
    st.push_back(n + 1);
    rep(i, n, 1) {
        while (!st.empty() and a[i] >= a[st.front()]) {
            add(st.front(), -v[st.front()]);
            st.pop_front();
        }
        v[i] = (st.front() - 1 - i) * a[i] - (pre[st.front() - 1] - pre[i]);
        add(i, v[i]);
        st.push_front(i);
        for (auto j : que[i]) {
            int pos = upper_bound(st.begin(), st.end(), j.fi) - st.begin() - 1;
            ans[j.se] = (pos ? query(st[pos - 1]) - query(i - 1) : 0) +
                        (j.fi - st[pos]) * a[st[pos]] -
                        (pre[j.fi] - pre[st[pos]]);
        }
    }
    lep(i, 1, q) cout << ans[i] << endl;
}