ICPC中国南昌国家邀请赛和国际丝绸之路规划大赛预选赛 I J

太过爱你忘了你带给我的痛 2021-09-30 13:28 297阅读 0赞

I. Max answer

链接：https://nanti.jisuanke.com/t/38228

思路:

枚举最小值，单调栈确定最小值的边界，用线段树+前缀和维护最小值的左右区间

实现代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    
    const ll M = 5e5+10;
    const ll inf = 1e9;
    ll a[M],Li[M],Ri[M],sum[M];
    ll lmn[M<<2],lmx[M<<2],rmn[M<<2],rmx[M<<2],pre[M],nex[M];
    void build(ll l,ll r,ll rt){
        if(l == r){
            lmn[rt] = nex[l];
            lmx[rt] = nex[l];
            rmn[rt] = pre[l];
            rmx[rt] = pre[l];
            return ;
        }
        ll m = (l + r) >> 1;
        build(lson); build(rson);
        lmn[rt] = min(lmn[rt<<1],lmn[rt<<1|1]);
        rmn[rt] = min(rmn[rt<<1],rmn[rt<<1|1]);
        lmx[rt] = max(lmx[rt<<1],lmx[rt<<1|1]);
        rmx[rt] = max(rmx[rt<<1],rmx[rt<<1|1]);
    }
    
    ll getlmn(ll L,ll R,ll l,ll r,ll rt){
        if(L <= l&&R >= r){
            return lmn[rt];
        }
        ll m = (l + r) >> 1;
        ll ret = inf;
        if(L <= m) ret = min(ret,getlmn(L,R,lson));
        if(R > m) ret = min(ret,getlmn(L,R,rson));
        return ret;
    }
    
    ll getrmn(ll L,ll R,ll l,ll r,ll rt){
        if(L <= l&&R >= r){
            return rmn[rt];
        }
        ll m = (l + r) >> 1;
        ll ret = inf;
        if(L <= m) ret = min(ret,getrmn(L,R,lson));
        if(R > m) ret = min(ret,getrmn(L,R,rson));
        return ret;
    }
    
    ll getlmx(ll L,ll R,ll l,ll r,ll rt){
        if(L <= l&&R >= r){
            return lmx[rt];
        }
        ll m = (l + r) >> 1;
        ll ret = 0;
        if(L <= m) ret = max(ret,getlmx(L,R,lson));
        if(R > m) ret = max(ret,getlmx(L,R,rson));
        return ret;
    }
    
    ll getrmx(ll L,ll R,ll l,ll r,ll rt){
        if(L <= l&&R >= r){
            return rmx[rt];
        }
        ll m = (l + r) >> 1;
        ll ret = 0;
        if(L <= m) ret = max(ret,getrmx(L,R,lson));
        if(R > m) ret = max(ret,getrmx(L,R,rson));
        return ret;
    }
    
    int  main()
    {
        ll n;
        scanf("%lld",&n);ll ans = 0,flag = 0,mid = n+1;
        for(ll i = 1;i <= n;i ++){
            scanf("%lld",&a[i]);
            if(a[i]>0&&flag==0) mid = i,flag = 1;
            ans += a[i]; pre[i] = ans;
        }
        ans = 0;
        for(ll i = n;i >= 1;i --){
            ans += a[i]; nex[i] = ans;
        }
        build(1,n,1);
        stack<ll>s;
        for(ll i = 1;i <= n;i ++){
            while(s.size()&&a[s.top()]>=a[i]) s.pop();
            if(s.empty()) Li[i] = 1;
            else Li[i] = s.top()+1;
            s.push(i);
        }
        while(!s.empty()) s.pop();
        for(ll i = n;i >= 1;i --){
            while(s.size()&&a[s.top()]>=a[i]) s.pop();
            if(s.empty()) Ri[i] = n;
            else Ri[i] = s.top()-1;
            s.push(i);
        }
        while(!s.empty()) s.pop();
        ll cnt = 0,num,mx=0;
        for(ll i = 1;i <= n;i ++){
            if(a[i] >= 0){
                cnt = a[i];
                cnt += getlmx(Li[i],i,1,n,1)-nex[i];
                cnt += getrmx(i,Ri[i],1,n,1)-pre[i];
                mx = max(mx,cnt*a[i]);
                //cout<<cnt<<" "<<getlmx(Li[i],i,1,n,1)<<" "<<getrmx(i,Ri[i],1,n,1)<<endl;
            }
            else{
                cnt = a[i];
                cnt += getlmn(Li[i],i,1,n,1)-nex[i];
                cnt += getrmn(i,Ri[i],1,n,1)-pre[i];
                mx = max(mx,cnt*a[i]);
                 //cout<<cnt<<" "<<getlmn(Li[i],i,1,n,1)-nex[i]<<" "<<getrmn(i,Ri[i],1,n,1)-pre[i]<<endl;
            }
           //cout<<a[i]<<" "<<Li[i]<<" "<<Ri[i]<<" "<<mx<<endl;
        }
        printf("%lld\n",mx);
    }

J. Distance on the tree

链接：https://nanti.jisuanke.com/t/38229

思路;

序列上求任意区间有多少个数小于k

https://www.cnblogs.com/kls123/p/9568553.html

就是这道题扔到树上，一开始想复杂了，还以为是点对的数量。

从根节点向下遍历每次遍历到一条边看作是一次修改，下标为val的点+1

但是这种方法建的主席树是类似权值线段树的，下标和树是没关系的，有关系的是这是第几次修改的，所以在树上应该用root跳

注意 在树上跳的时候表示当前点前后的点时应该用fa\[\],son\[\]，而不是+1,-1.

实现代码：

#include<bits/stdc++.h>
    using namespace std;
    const int M = 3e5+10;
    int ls[M*40],rs[M*40],sum[M*40],a[M],b[M],root[M];
    int cnt1,cnt,head[M],dep[M],siz[M],fa[M],son[M],wt[M],top[M],tid[M],rk[M];
    int idx,tot;
    struct node{
        int w,to,next;
    }e[M*2];
    
    void add(int u,int v,int c){
        e[++cnt1].to=v;e[cnt1].next=head[u];e[cnt1].w=c;head[u]=cnt1;
        e[++cnt1].to=u;e[cnt1].next=head[v];e[cnt1].w=c;head[v]=cnt1;
    }
    void dfs1(int u,int faz,int deep){
        dep[u] = deep;
        siz[u] = 1;
        fa[u] = faz;
        for(int i = head[u];i ;i=e[i].next){
            int v = e[i].to;
            if(v != fa[u]){
                wt[v] = e[i].w;
                dfs1(v,u,deep+1);
                siz[u] += siz[v];
                if(son[u]==-1||siz[v]>siz[son[u]])
                    son[u] = v;
            }
        }
    }
    
    void dfs2(int u,int t){
        top[u] = t;
        tid[u] = tot;
        rk[tot] = wt[u];
        //cout<<1<<endl;
        tot++;
        if(son[u] == -1) return ;
        dfs2(son[u],t);
        for(int i = head[u];i;i=e[i].next){
            int v = e[i].to;
            if(v != son[u]&&v != fa[u])
                dfs2(v,v);
        }
    }
    
    void update(int old,int &k,int l,int r,int p){
        k = ++idx;
        ls[k] = ls[old]; rs[k] = rs[old];
        sum[k] = sum[old] + 1;
        if(l == r) return ;
        int mid = (l + r) >> 1;
        if(p <= mid) update(ls[old],ls[k],l,mid,p);
        else update(rs[old],rs[k],mid+1,r,p);
    }
    
    int query(int old,int k,int L,int R,int l,int r){
        if(L <= l&&R >= r) return sum[k] - sum[old];
        int mid = (l + r) >> 1;
        int ret = 0;
        if(L <= mid) ret += query(ls[old],ls[k],L,R,l,mid);
        if(R > mid) ret += query(rs[old],rs[k],L,R,mid+1,r);
        return ret;
    }
    
    int ask(int x,int y,int l,int r){
        int ans = 0;
        int fx = top[x],fy = top[y];
        while(fx != fy){
            if(dep[fx] < dep[fy]) swap(fx,fy),swap(x,y);
            if(fx == 1) ans += query(root[tid[fx]],root[tid[x]],l,r,1,cnt);
            else ans += query(root[tid[fa[fx]]],root[tid[x]],l,r,1,cnt);
            x = fa[fx]; fx = top[x];
        }
        if(x==y) return ans; 
        if(dep[x] > dep[y]) swap(x,y);
        ans += query(root[tid[x]],root[tid[y]],l,r,1,cnt);
        return ans;
    }
    
    void dfs(int u,int fa){
        update(root[tid[fa]],root[tid[u]],1,cnt,wt[u]);
        for(int i = head[u];i;i=e[i].next){
            int v = e[i].to;
            if(v == fa) continue;
            dfs(v,u);
        }
    }
    
    int l[M],r[M],x[M],u[M],v[M],w[M];
    int Find(int x){
        int num = lower_bound(b+1,b+1+cnt,x)-b;
        return num;
    }
    
    int main()
    {
        int m,n;
        scanf("%d%d",&n,&m); tot = 1;
        memset(son,-1,sizeof(son));
        for(int i = 1;i < n;i ++){
            scanf("%d%d%d",&u[i],&v[i],&w[i]);
            b[i] = w[i];
        }
        for(int i = 1;i <= m;i ++){
            scanf("%d%d%d",&l[i],&r[i],&x[i]);
            b[i+n-1] = x[i];
        }
        sort(b+1,b+n+m);
        cnt = unique(b+1,b+n+m)-b;
        for(int i = 1;i < n;i ++){
            int num = Find(w[i]);
            add(u[i],v[i],num);
        }
        dfs1(1,0,1); dfs2(1,1);dfs(1,0);
        for(int i = 1;i <= m;i ++){
            int num = Find(x[i]);
            printf("%d\n",ask(l[i],r[i],1,num));
        }
    }

转载于:https://www.cnblogs.com/kls123/p/10742300.html