头像

wxy_




离线:4天前


活动打卡代码 AcWing 255. 第K小数

wxy_
19天前
#include <iostream>
#include <vector>
#include <algorithm>

namespace wxy{

const int N = 1e5 + 5;

int idx,n,m,a[N],root[N];

std::vector<int> nums;

struct node{int l,r,cnt;}t[N * 21];

inline int get(int x){return std::lower_bound(nums.begin(),nums.end(),x) - nums.begin();}

inline int build(int l,int r){
    int p = ++idx; t[p].cnt = 0;
    if (l == r) return p;
    int mid = l + r >> 1;
    t[p].l = build(l,mid);
    t[p].r = build(mid + 1,r);
    return p;
}

inline int insert(int p,int l,int r,int x){
    int q = ++idx;
    t[q] = t[p];
    if (l == r){t[q].cnt++; return q;}
    int mid = l + r >> 1;
    if (x <= mid) t[q].l = insert(t[p].l,l,mid,x);
    else t[q].r = insert(t[p].r,mid + 1,r,x);
    t[q].cnt = t[t[q].l].cnt + t[t[q].r].cnt;
    return q;
}

inline int query(int q,int p,int l,int r,int k){
    if (l == r) return r;
    int mid = l + r >> 1,cnt = t[t[q].l].cnt - t[t[p].l].cnt;
    if (cnt >= k) return query(t[q].l,t[p].l,l,mid,k);
    else return query(t[q].r,t[p].r,mid + 1,r,k - cnt);
}

inline void main(){
    std::cin >> n >> m; idx = 0;
    for (int i = 1; i <= n; i++){
        std::cin >> a[i];
        nums.push_back(a[i]);
    }
    std::sort(nums.begin(),nums.end());
    nums.erase(std::unique(nums.begin(),nums.end()),nums.end());
    root[0] = build(0,nums.size() - 1);
    for (int i = 1; i <= n; i++)
        root[i] = insert(root[i-1],0,nums.size()-1,get(a[i]));
    while(m--){
        int l,r,k; std::cin >> l >> r >> k;
        std::cout << nums[query(root[r],root[l-1],0,nums.size()-1,k)] << std::endl;
    }

}

}signed main(){wxy::main(); return 0;}


活动打卡代码 AcWing 261. 旅馆

wxy_
27天前
#include <iostream>

namespace wxy{
const int N = 5e4 + 5;
struct node{int l,r,lmax,rmax,max,sum,tag;}t[N << 2];
int n,m;
inline void pushup(int u){
    int tt = std::max(t[u << 1].max,t[u << 1 | 1].max);
    t[u].max = std::max(tt,t[u << 1].rmax + t[u << 1 | 1].lmax);
    t[u].lmax = t[u << 1].lmax; t[u].rmax = t[u << 1 | 1].rmax;
    if (t[u << 1].max == t[u << 1].r - t[u << 1].l + 1)
        t[u].lmax = std::max(t[u].max,t[u << 1].sum + t[u << 1 | 1].lmax);
    if (t[u << 1 | 1].max == t[u << 1 | 1].r - t[u << 1 | 1].l + 1)
        t[u].rmax = std::max(t[u].max,t[u << 1 | 1].sum + t[u << 1].rmax);
}
inline void pushdown(int u){
    if (t[u].tag != -1){
        t[u << 1].sum = t[u].tag * (t[u << 1].r - t[u << 1].l + 1);
        t[u << 1 | 1].sum = t[u].tag * (t[u << 1 | 1].r - t[u << 1 | 1].l + 1);
        t[u << 1].max = t[u << 1].lmax = t[u << 1].rmax = t[u << 1].sum;
        t[u << 1 | 1].max = t[u << 1 | 1].lmax = t[u << 1 | 1].rmax = t[u << 1 | 1].sum;
        t[u << 1].tag = t[u << 1 | 1].tag = t[u].tag; t[u].tag = -1;
    }
}
inline void build(int u,int l,int r){
    t[u].l = l; t[u].r = r; t[u].tag = -1;
    if (l == r){t[u].lmax = t[u].rmax = t[u].max = t[u].sum = 1; return;}
    int mid = l + r >> 1;
    build(u << 1,l,mid);
    build(u << 1 | 1,mid + 1,r);
    pushup(u);
}
inline void cge(int u,int l,int r,int v){
    if (t[u].l == l && t[u].r == r){
        t[u].sum = v * (r - l + 1); t[u].tag = v;
        t[u].lmax = t[u].rmax = t[u].max = t[u].sum;
        return;
    }
    pushdown(u);
    int mid = t[u].l + t[u].r >> 1;
    if (r <= mid)cge(u << 1,l,r,v);
    else if (l > mid) cge(u << 1 | 1,l,r,v);
    else {cge(u << 1,l,mid,v); cge(u << 1 | 1,mid + 1,r,v);}
    pushup(u);
}
inline int query(int u,int d){
    if (t[u].lmax >= d){
        cge(1,t[u].l,t[u].l + d - 1,0);
        return t[u].l;
    }
    pushdown(u);
    int mid = t[u].l + t[u].r >> 1;
    if (t[u << 1].max >= d) return query(u << 1,d);
    else if (t[u << 1].rmax + t[u << 1 | 1].lmax >= d && t[u << 1].rmax > 0){
        int len1 = t[u << 1].rmax,len2 = d - t[u << 1].rmax;
        cge(1,mid - len1 + 1,mid,0); cge(1,mid + 1,mid + len2,0);
        return (mid - len1 + 1);
    }else if (t[u << 1 | 1].max >= d)return query(u << 1 | 1,d);
    return 0;
}
inline void main(){
    std::cin >> n >> m;
    build(1,1,n);
    while (m--){
        int op,x,d;
        std::cin >> op >> x;
        if (op == 1) std::cout << query(1,x) << std::endl;
        else {std::cin >> d; cge(1,x,x + d - 1,1);}
    }

}
}signed main(){wxy::main(); return 0;}



wxy_
1个月前
#include <iostream>

namespace wxy{
    const int N = 1e5 + 5;
    int a1[31],a2[31];
    void main(){
        int n,m,res = 0,ans = 0;
        std::cin >> n >> m;
        for (int i = 0; i < 31; i++) a1[i] = 1;
        for (int i = 0; i < n; i++){
            char op[10];int val;
            std::cin >> op >> val;
            if (op[0] == 'A'){
                for (int j = 0;j < 31; j++){
                    if (val >> j & 1){a1[j] &= 1; a2[j] &= 1;}
                    else {a1[j] &= 0; a2[j] &= 0;}
                }
            }
            if (op[0] == 'O'){
                for (int j = 0;j < 31; j++){
                    if (val >> j & 1){a1[j] |= 1; a2[j] |= 1;}
                    else {a1[j] |= 0; a2[j] |= 0;}
                }
            }
            if (op[0] == 'X'){
                for (int j = 0;j < 31; j++){
                    if (val >> j & 1){a1[j] ^= 1; a2[j] ^= 1;}
                    else {a1[j] ^= 0; a2[j] ^= 0;}
                }
            }
        }
        for (int i = 30; i >= 0; i--){
            if ((res + (1 << i)) <= m && a1[i] > a2[i]){
                res += 1 << i;
                ans += 1 << i;
                continue;
            } 
            if (a2[i] == 1)ans += 1 << i;
        }
        std::cout << ans;
    }
}signed main(){wxy::main();return 0;}



wxy_
1个月前

竞赛图$\text{(tournament)}$

若简单图$G$满足任意不同两点间均存在一条有向边,则称$G$为竞赛图$\text{(tournament)}$。

比分序列$\text{(Scores Sequence)}$

定义一个竞赛图的比分序列$\text{(Scores Sequence)}$,是把竞赛图的每一个点的出度从小到大排列得到的序列。

$\text{Landau’s Theorem}$ 与 $\text{Scores Sequence}$的性质、判定

$\text{Landau’s Theorem}:$一个长度为$n$的序列$s(s_1\le s_2\le …\le s_n),n\ge1$是竞赛图的比分序列充要条件为$:$
$$
\forall 1\le k\le n,\sum_{1\le i\le k}s_i \ge \binom{k}{2}
$$
切当$k=n$时上式取等号。

$\text{Scores Sequence}$的性质

对于任意一个$n$个点的竞赛图$G$,其比分序列$s(s_1\le s_2\le …\le s_n),n\ge1$,满足于$\forall 1\le k\le n,\sum_{1\le i\le k}s_i \ge \binom{k}{2}$。

$\text{Scores Sequence}$的判定

一个长度为$n$的序列$s(s_1\le s_2\le …\le s_n),n\ge1$若满足于$\forall 1\le k\le n,\sum_{1\le i\le k}s_i \ge \binom{k}{2}$,那么该序列是竞赛图的比分序列。

$\text{Landau’s Theorem}$的证明与$\text{tournament}$的构造

其定理的必要性(即$\text{Scores Sequence}$的性质)的证明是显然的:

对于$n$个点的竞赛图,其任意由$k(k\le n)$个点构成的子图一定也是竞赛图,且满足出度和为$\binom{k}{2}$,而其子图内部的度数和一定小于等于全局的度数和。

接下来考虑证明$\text{Landau’s Theorem}$的充分性(即$\text{Scores Sequence}$的判定):

我们考虑从从一个已知的$n$个点的竞赛图开始构造,具体地:每次改变一条边的方向,直到将其$\text{Scores Sequence}$“改造”成我们钦定的,满足定理的序列。

首先,我们构造一个“平凡的$n$个点的竞赛图$G$”,具体地:对于任一点$i$,我们向$\forall 1\le j < i$连边,其对应的$\text{Scores Sequence}$为$u(0,1,2,3,…n-1)$,我们的目标为将其“改造”为满足定理的任一序列$s(s_1\le s_2\le…\le s_n)$。

我们如下定义$dist(u.s)$:
$$
dist(u.s)=\sum_{1\le i\le n}|s_i-u_i|
$$
因为
$$
\sum_{1\le i\le n}s_i = \sum_{1\le i\le n}u_i=\binom{n}{2}
$$
$$
S_1=\sum_{1\le i\le n,s_i-u_i<0}s_i-u_i,S_2=\sum_{1\le i\le n,s_i-u_i>0}s_i-u_i
$$
所以
$$
S_1+S_2=\sum_{1\le i\le n}s_i-\sum_{1\le i\le n}u_i=0
$$
即$|S_1|=|S_2|$,且$dist(u.s)=|S_1|+|S_2|$,因此$dist(u.s)|2$。

因为$\forall 1\le i\le n,|s_i-u_i|\ge 0$,所以$dist(u.s)=0$当且仅当$\forall 1\le i\le n,s_i=u_i$。

那么我们的目标就很明显了:通过将若干条边改变方向,令$dist(u.s)=0$。

假定当前步我们构造到的竞赛图所对应的$\text{Scores Sequence}$为$u(u_1\le u_2\le…\le u_n)$,且满足于:
$$
\forall 1\le k\le n, \sum_{1\le i\le k}s_i \ge\sum_{1\le i\le k}u_i
$$
且在$k=n$时,上式取等号。

令$\alpha$为满足第一个$s_\alpha > u_\alpha$的位置,$\beta$为最后一个满足$u_\alpha=u_\beta$的位置,$\gamma$为第一个满足$s_\gamma<u_\gamma$的位置。

在我们未构造出满足$\text{Scores Sequence}$为$s(s_1\le s_2\le…\le s_n)$的竞赛图时,我们可以确定位置$\alpha$一定是存在的,因为若位置$\alpha$不存在,我们当前一定是构造成功的。

而因为位置$\alpha$存在,因此 位置$\beta,\gamma$也一定是存在的。

且位置$\gamma$一定是在位置$\beta$后面的,若$\gamma$在$\alpha$前面,那么一定有$\sum_{1\le i\le \gamma}s_i <\sum_{1\le i\le \gamma}u_i$。

而且其一定是不能在位置$\alpha\sim \beta$之间的。

因此$u_\gamma > s_\gamma \ge s_\beta > u_\beta$,即$u_\gamma\ge u_\beta+2$。

其意味着一定存在一个点$\lambda$,满足$\lambda\not= \beta,\lambda\not=\gamma$,存在边$(\gamma,\lambda),(\lambda,\beta)$。

简单反证即可。

那么我们将边$(\gamma,\lambda),(\lambda,\beta)$翻转为$(\beta,\lambda),(\lambda,\gamma)$。

其影响为$u_\gamma-1$,$u_\beta + 1$。且经过更改后的序列仍然满足:
$$
\forall 1\le k\le n, \sum_{1\le i\le k}s_i \ge\sum_{1\le i\le k}u_i
$$

而且因为$u_\gamma > s_\gamma$,$u_\beta<s_\beta$,因此这样操作下来我们可以使得其$dist(u.s)-2$,而又因为$dist(u.s)|2$,因此操作至多$\frac{1}{2}dist(u.s)$次就可以构造出满足$\text{Scores Sequence}$为$s(s_1\le s_2\le…\le s_n)$的竞赛图。

在证明了$\text{Landau’s Theorem}$的充要性的同时,我们也得到了一个$O(n^3)$的竞赛图构造算法。




wxy_
3个月前
#include <iostream>

namespace wxy{
    const int N = 1e5 + 5;
    int a[N],n,m;
    long long b[N];
    inline int lowbit(int x){return x & -x;}
    inline void add(int x,long long a){
        for (;x <= n; x += lowbit(x)) b[x] += a;
    }
    inline long long ask(int x){
        long long res = 0;
        for (int i = x;i;i -= lowbit(i))
            res += b[i];
        return res;
    }
    void main(){
        std::cin >> n >> m;
        for(int i = 1; i <= n; i++) std::cin >> a[i];
        for (int i = n; i >= 1; i--) a[i] = a[i] - a[i - 1];
        for (int i = 1; i <= n; i++) add(i,a[i]);
        for (int i = 1; i <= m; i++){
            char op[1];
            int a,b;
            long long c;
            std::cin >> op;
            std::cin >> a;
            if (op[0] == 'Q') std::cout << ask(a) << std::endl;
            else{
                std::cin >> b >> c;
                add(a,c);
                add(b + 1,-c);
            }
        }
    }
}signed main(){
    wxy::main();
    return 0;
}



wxy_
3个月前
#include <iostream>

namespace wxy{
    const int N = 1e5 + 5;
    int a[N],n,m;
    long long b[N];
    inline int lowbit(int x){return x & -x;}
    inline void add(int x,long long a){
        for (;x <= n; x += lowbit(x)) b[x] += a;
    }
    inline long long ask(int x){
        long long res = 0;
        for (int i = x;i;i -= lowbit(i))
            res += b[i];
        return res;
    }
    void main(){
        std::cin >> n >> m;
        for(int i = 1; i <= n; i++) std::cin >> a[i];
        for (int i = n; i >= 1; i--) a[i] = a[i] - a[i - 1];
        for (int i = 1; i <= n; i++) add(i,a[i]);
        for (int i = 1; i <= m; i++){
            char op[1];
            int a,b;
            long long c;
            std::cin >> op;
            std::cin >> a;
            if (op[0] == 'Q') std::cout << ask(a) << std::endl;
            else{
                std::cin >> b >> c;
                add(a,c);
                add(b + 1,-c);
            }
        }
    }
}signed main(){
    wxy::main();
    return 0;
}



wxy_
3个月前

众所周知noip暴力分暴多

$Case\ 1$

考虑第一个数据点和第二个数据点,显然当且仅当$S_i=T_i=u$时,才会对点$u$产生贡献,因此在标记后线性扫描每个点即可。

复杂度$O(n+m)$

期望得分:$10\ pts$

$Case\ 2$

显然当且仅当$u=S_i$时,才会对点$u$产生贡献,标记所有起点线性扫描每个点即可。

复杂度$O(n+m)$

期望得分:$20\ pts$

$Case\ 3$

考虑暴力枚举每条链,对其进行树上差分后依次枚举每个点,该链对点$u$产生贡献当且仅当该点在链上且$dis(S_i,u)=w_u$。

复杂度$O(mn+m\ log\ n)$

期望得分:$25\ pts$

$Case\ 4$

该题退化为链的方式比较特殊。

我们发现,当按所叙述方式退化为链时整个问题转化为线性序列上的问题:

给出一个序列$a$与$m$个区间,求对于序列$a$第$i$个位置前面第$a[i]$个位置上有几个$S_j$满足其对应的$T_j\ge i$。

对于每个位置开一个$vector$,保存其$S_i$恰好为这个位置所对应的所有$T_i$,递增排序后每次二分查找即可。

复杂度$O(n\ log\ n)$

期望得分:$40pts$

$Case\ 5$

当所有的$S_i$为根节点时。

显然当且仅当$T_i$在以$x$为根的子树内时,链$[HTML_REMOVED]$才会经过$x$。

因此直接$DFS$一遍,统计每个节点到根节点的距离$dis(u)$,如果$dis(u)=w_u$,那么其节点$u$的答案即子树内$T_i$的数量,否则为$0$。

对于$T_i$的数量,直接打标记后$DFS$一遍即可求得。

复杂度$O(n)$

期望得分:$60pts$

$Case\ 6$

我们发现,当终点在根节点时。

其等价于求在以点$u$为根的子树内有多少$S_i$,满足$dis(u,S_i)=w_u$。

我们设点$u$的深度为$deep[u]$,那么即等价于在点$u$的子树内,深度为$deep[u]+w_u$的这一层内有多少$S_i$。

把原树用$DFS$序重编号,按层拆成若干份使用$vector$存储。

对于每个$S_i$对其进行序列单点加之后求前缀和。

在$deep[u]+w_u$这一层的$DFS$序中二分点$u$ $DFS$序所对的区间查询区间和。

复杂度$O(n\ log\ n)$。

期望得分:$80pts$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>

namespace wxy{
    const int N = 3e5 + 5,inf = 5e5 + 5;
    int ans[N];
    int head[N],fail[N << 1],edge[N << 1],w[N],tot,n,m;
    int fa[N][35],dep[N],tlca[N],dfn[N],cnt,l[N],r[N];
    bool vis[N];
    int t[N],pt[N],ppt[N],maxdeep;
    typedef std::pair<int,int> PII;
    #define x first
    #define y second
    PII ask[N];
    inline void add(int x,int y){
        edge[++tot] = y;
        fail[tot] = head[x];
        head[x] = tot;
    }
    void dfs1(int x){
        l[x] = ++cnt;
        dfn[cnt] = x;
        for (int i = 1; 1 << i <= n; i++)
            fa[x][i] = fa[fa[x][i-1]][i-1];
        for (int i = head[x];i;i = fail[i]){
            int v = edge[i];
            if (dep[v] != -1) continue;
            fa[v][0] = x;
            dep[v] = dep[x] + 1;
            dfs1(v);
        }
        r[x] = cnt;
    }
    inline int lca(int x,int y){
        if (dep[x] < dep[y]) std::swap(x,y);
        int d = dep[x] - dep[y];
        for (int i = 0; i < 20; i++)
            if (d >> i & 1) x = fa[x][i];
        if (x == y) return x;
        for (int i = 19; i >= 0; i--){
            if (fa[x][i] != fa[y][i]){
                x = fa[x][i];
                y = fa[y][i];
            }
        }
        return fa[x][0];
    }
    inline int get(int x,int y){
        return dep[x] + dep[y] - 2 * dep[lca(x,y)];
    }
    inline void case1(){
        for (int i = 1; i <= m; i++) 
            if (w[ask[i].x] == 0)ans[ask[i].x]++;
    }
    inline void case2(){
        for (int i = 1; i <= m; i++) ans[ask[i].x]++;
    }
    inline void case3(){
        for (int i = 1; i <= m; i++){
            memset(t,0,sizeof t);
            int a = ask[i].x,b = ask[i].y;
            t[a]++;t[b]++;t[tlca[i]]--;
            t[fa[tlca[i]][0]] -= 2;
            for (int j = n; j >= 1; j--) 
                t[fa[dfn[j]][0]] += t[dfn[j]];
            for (int j = 1; j <= n; j++){
                if (t[j] >= 1 && get(j,a) == w[j]){
                    ans[j]++;
                } 
            }
        }
    }
    inline void case4(){
        std::vector<int> pos[N];
        for (int i = 1; i <= n; i++){
            pos[i].push_back(0);
            pos[i].push_back(inf);
        }
        for (int i = 1; i <= m; i++)
            pos[ask[i].x].push_back(ask[i].y);
        for (int i = 1; i <= n; i++)
            std::sort(pos[i].begin(),pos[i].end());
        for (int i = 1; i <= n; i++){
            if (i - w[i] > 0){
                int loc = i - w[i];
                int count = lower_bound(pos[loc].begin(),pos[loc].end(),i) - pos[loc].begin();
                if (pos[loc][count] < inf) ans[i] += pos[loc].size() - count - 1;
            }
            if (i + w[i] <= n){
                int loc = i + w[i];
                int count = lower_bound(pos[loc].begin(),pos[loc].end(),i) - pos[loc].begin();
                if (pos[loc][count] > i) count--;
                ans[i] += count;
            }
        }
    }
    inline void case5(){
        for (int i = 1; i <= m; i++)
            pt[ask[i].y]++;
        for (int j = n; j >= 1; j--) 
            pt[fa[dfn[j]][0]] += pt[dfn[j]];
        for (int i = 1; i <= n; i++)
            if (dep[i] == w[i]) ans[i] = pt[i];
    }
    std::vector<int> dfnn[N];
    std::vector<int> ttp[N];
    inline void case6(){
        maxdeep = 0;
        for (int i = 1; i <= n; i++) 
            maxdeep = std::max(maxdeep,dep[i]);
        for (int i = 1; i <= n; i++){
            dfnn[dep[dfn[i]]].push_back(i);
            ttp[dep[dfn[i]]].push_back(0);
        }
        for (int i = 1; i <= m; i++){
            int p = ask[i].x;
            int pos = lower_bound(dfnn[dep[p]].begin(),dfnn[dep[p]].end(),l[p]) - dfnn[dep[p]].begin();
            ttp[dep[p]][pos]++;
        }
        for (int i = 0; i <= maxdeep; i++){
            dfnn[i].push_back(inf);
        }
        for (int i = 0; i <= maxdeep; i++){
            for (int j = 0; j < ttp[i].size(); j++){
                if (j > 0)ttp[i][j] = ttp[i][j - 1] + ttp[i][j];
            }
        }
        for (int i = 1; i <= n; i++){
            if (dep[i] + w[i] > maxdeep) continue;
            int deep = dep[i] + w[i];
            int left = lower_bound(dfnn[deep].begin(),dfnn[deep].end(),l[i]) - dfnn[deep].begin();
            int right = lower_bound(dfnn[deep].begin(),dfnn[deep].end(),r[i]) - dfnn[deep].begin();
            if (dfnn[deep][left] == inf) continue;
            if (dfnn[deep][right] == inf || dfnn[deep][right] > r[i]) right--;
            if (dfnn[deep][left] > r[i] || dfnn[deep][right] < l[i]) continue;
            if (left == 0) ans[i] += ttp[deep][right];
            else ans[i] += ttp[deep][right] - ttp[deep][left - 1];
        }
    }
    void main(){
        cnt = tot = 0;
        std::cin >> n >> m;
        for (int i = 1; i < n; i++){
            int a,b;
            std::cin >> a >> b;
            add(a,b);
            add(b,a);
        }
        memset(dep,-1,sizeof dep);
        dep[1] = 0;
        dfs1(1);
        for (int i = 1; i <= n; i++) std::cin >> w[i];
        for (int i = 1; i <= m; i++){
            std::cin >> ask[i].x >> ask[i].y;
            tlca[i] = lca(ask[i].x,ask[i].y);
        } 
       if (n == 991) case1();
       if (n == 992) case2();
       if (n == 993) case3();
       if (n == 99994) case4();
       if (n == 99995) case5();
       if (n == 99996) case6();
       for (int i = 1; i <= n; i++) std::cout << ans[i] << " ";
    }
}signed main(){
    wxy::main();
    return 0;
}



wxy_
3个月前

Case 1

暴力枚举每条边边权为$0$,每次查询询问中的最长路径取$\min$。

复杂度$O(nm\log\ n)$

Case 2

令最长链最小,其显然具有单调性,考虑二分。

转化为判定问题:

是否存在一种方案,满足所有询问中的链长均不超过$x$。

考虑如何判定:

如果在原树中有若条所询问的链长大于$x$,那么显然我们要令边权为$0$的边一定在这些链的公共边上。

那么我们贪心地令这些链的公共边中边权最大的边边权(记作$w$)为$0$后判一下是否满足所有的链长均小于等于$x$。

显然,原来链长小于等于$x$的依然小于等于$x$,而对于原来链长大于$x$的链而言,如果原来的链长为$L$,那么修改后的链长即$L-w$。

那么,如果$x\ge \max(L-w)$即$x$合法。

复杂度$O((n+m)\log L)$

在处理询问时预处理出所有的$lca$以及$dfn$重编号直接从$n$向前递推子树和减少常数(。

#include <iostream>
#include <cstring>
#include <cstdio>

namespace wxy{
    const int N = 3e5 + 5;
    int head[N],fail[N << 1],edge[N << 1],w[N << 1],tot;
    int dep[N],dis[N],fa[N][35],ds[N],dfn[N],wi[N],tlca[N],p;
    typedef std::pair<int,int> PII;
    #define x first
    #define y second
    PII ask[N];
    int t[N],n,m,cnt;
    inline void add(int x,int y,int we){
        edge[++tot] = y;
        w[tot] = we;
        fail[tot] = head[x];
        head[x] = tot;
    }
    void dfs(int x){
        dfn[++cnt] = x;
        for (int i = 1;i < 20; i++)
            fa[x][i] = fa[fa[x][i-1]][i-1];
        for (int i = head[x];i;i = fail[i]){
            int v = edge[i];
            if (v == fa[x][0]) continue;
            dep[v] = dep[x] + 1;
            dis[v] = dis[x] + w[i];
            wi[v] = w[i];
            fa[v][0] = x;
            dfs(v);
        }
    }
    inline int lca(int x,int y){
        if (dep[x] < dep[y]) std::swap(x,y);
        int d = dep[x] - dep[y];
        for (int j = 0; j < 20; j++)
            if (d >> j & 1) x = fa[x][j];
        if (x == y) return x;
        for (int j = 19; j >= 0; j--){
            if (fa[x][j] != fa[y][j]){
                x = fa[x][j];y = fa[y][j];
            }
        }
        return fa[x][0];
    }
    inline bool check(int x){
        memset(t,0,sizeof t);
        int maxd = 0;
        cnt = 0;
        for (int i = 1; i <= m; i++){
            int a = ask[i].x;
            int b = ask[i].y;
            int lc = tlca[i];
            int dist = dis[a] + dis[b] - (dis[lc] << 1);
            if (dist > x){
                cnt++;t[a]++;t[b]++;
                t[lc] -= 2;
                maxd = std::max(maxd,dist);
            }
        }
        if (cnt == 0) return true;
        for (int i = n; i >= 1; i--)
            t[fa[dfn[i]][0]] += t[dfn[i]];
        for (int i = 1; i <= n; i++)
            if (t[i] == cnt && maxd - wi[i] <= x) return true;
        return false;
    }
    void main(){
        cnt = tot = 0;
        scanf("%d%d",&n,&m);
        for (int i = 1; i < n; i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
        memset(dep,-1,sizeof dep);
        dep[1] = 0;
        dfs(1);
        for (int i = 1; i <= m; i++){
            scanf("%d%d",&ask[i].x,&ask[i].y);
            tlca[i] = lca(ask[i].x,ask[i].y);
        } 
        int l = 0,r = 1e9;
        while (l < r){
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        printf("%d",l);
    }
}signed main(){
    wxy::main();
    return 0;
}



wxy_
3个月前
#include <iostream>

namespace wxy{
    const int N = 5e5 + 5;
    struct node{
        int l,r;
        long long s,add;
    }t[N << 2];
    int a[N],n,m;
    inline void pushup(int u){t[u].s = t[u << 1].s + t[u << 1 | 1].s;}
    inline void pushdown(int u){
        if (t[u].add){
            long long ad = t[u].add;
            t[u << 1].s += ad * (t[u << 1].r - t[u << 1].l + 1);
            t[u << 1 | 1].s += ad * (t[u << 1 | 1].r - t[u << 1 | 1].l + 1);
            t[u << 1].add += ad;
            t[u << 1 | 1].add += ad;
            t[u].add = 0;
        }
    }
    inline void build(int u,int l,int r){
        t[u].l = l;t[u].r = r;t[u].add = 0;
        if (l == r){
            t[u].s = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(u << 1,l,mid);
        build(u << 1 | 1,mid + 1,r);
        pushup(u);
    }
    inline void cge(int u,int l,int r,long long x){
        if (t[u].l >= l && t[u].r <= r){
            t[u].s += x * (t[u].r - t[u].l + 1);
            t[u].add += x;
        }else{
            pushdown(u);
            int mid = t[u].l + t[u].r >> 1;
            if (l <= mid) cge(u << 1,l,r,x);
            if (r > mid) cge(u << 1 | 1,l,r,x);
            pushup(u);
        }
    }
    inline long long ask(int u,int l,int r){
        if (t[u].l >= l && t[u].r <= r)return t[u].s;
        pushdown(u);
        int mid = t[u].l + t[u].r >> 1;
        long long res = 0;
        if (l <= mid) res += ask(u << 1,l,r);
        if (r > mid) res += ask(u << 1 | 1,l,r);
        return res;
    }
    void main(){
        std::cin >> n >> m;
        for (int i = 1; i <= n; i++) std::cin >> a[i];
        build(1,1,n);
        while(m--){
            char op[1];
            std::cin >> op[0];
            int a,b;
            long long c;
            std::cin >> a >> b;
            if (op[0] == 'Q') std::cout << ask(1,a,b) << std::endl;
            else{
                std::cin >> c;
                cge(1,a,b,c);
            }
        }
    }
}signed main(){wxy::main();return 0;}



wxy_
3个月前
#include <iostream>

namespace wxy{
    const int N = 5e5;
    int n,m,a[N];
    struct node{
        int l,r,v,lv,rv,s;
    }t[N << 2];
    inline void push_up(int u){
        int p = std::max(t[u << 1].v,t[u << 1 | 1].v);
        t[u].v = std::max(p,t[u << 1].rv + t[u << 1 | 1].lv);
        t[u].s = t[u << 1].s + t[u << 1 | 1].s;
        t[u].rv = std::max(t[u << 1 | 1].rv,t[u << 1 | 1].s + t[u << 1].rv);
        t[u].lv = std::max(t[u << 1].lv,t[u << 1].s + t[u << 1 | 1].lv);
    }
    inline void build(int u,int l,int r){
        t[u].l = l;t[u].r = r;
        if (l == r){
            t[u].s = t[u].v = t[u].lv = t[u].rv = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(u << 1,l,mid);
        build(u << 1 | 1,mid + 1,r);
        push_up(u);
    }
    inline void cge(int u,int x,int v){
        if (t[u].l == t[u].r && t[u].l == x){
            t[u].s = t[u].v = t[u].lv = t[u].rv = v;
            return;
        }
        int mid = t[u].l + t[u].r >> 1;
        if (x <= mid) cge(u << 1,x,v);
        if (x > mid) cge(u << 1 | 1,x,v);
        push_up(u);
    }
    inline node ask(int u,int l,int r){
        if (t[u].l >= l && t[u].r <= r) return t[u];
        int mid = t[u].l + t[u].r >> 1;
        node r1,r2,res;
        r1 = {0,0,-11451419,-11451419,-11451419,-11451419};
        r2 = {0,0,-11451419,-11451419,-11451419,-11451419};
        if (l <= mid) r1 = ask(u << 1,l,r);
        if (r > mid) r2 = ask(u << 1 | 1,l,r);
        int p = std::max(r1.v,r2.v);
        res.v = std::max(p,r1.rv + r2.lv);
        res.s = r1.s + r2.s;
        res.rv = std::max(r2.rv,r2.s + r1.rv);
        res.lv = std::max(r1.lv,r1.s + r2.lv);
        return res;
    }
    void main(){
        std::cin >> n >> m;
        for (int i = 1; i <= n; i++) std::cin >> a[i];
        build(1,1,n);
        while (m--){
            int a,b,c;
            std::cin >> a >> b >> c;
            if (a == 1 && b > c) std::swap(b,c);
            if (a == 1) std::cout << ask(1,b,c).v << std::endl;
            else cge(1,b,c);
        }
    }
}signed main(){wxy::main();return 0;}