【题解】牛客IOI周赛22-提高组

: 1~4 20分

可以观察到数据较小，可以使用 通过（其他乱搞也可）
（为了方便讲解，此处先讲解 ）

: 9~12 另20分

可以发现在权值为1的情况下，可以使用贪心（后文将证明），记录下上一次的名次 ，每次都贪心的尽量让名次最大（即 ），若 ，则说明不管怎样都无法满足条件，则将排名设为
由于贪心遗漏的情况是当 时取 通过舍弃这一次的奖品来使下一次获得奖品，而由于权值全部为1，所以本次贪心所选取的补偿了下一个没取到的，所以贪心正确性可证，时间复杂度

: 5~8 20分（可获得40分）

由上文可知，本题需要使用dp来解决，所以考虑直接设计状态 表示第 场考试考第 名时最多的奖品数，则状态转移方程为:

显然当 一定时， 具有单调性，复杂度

: 13~20 40分（可获得100分）

发现 只有，所以连续获奖的次数最多只有次，同时受上文贪心思想的启发，易发现当本次能获得奖品时取 最优，否则取 最优。则可设计状态 表示第 场考试时已经连续获得了 次奖的最多奖品数，则状态转移方程为

其中 为辅助数组，表示连续去 次奖后第 场考试的最大名次，在转移过程中由上述贪心即可求出 数组，而最大值可在上一轮循环的计算中求出，即 可以 求出，由于每取一次奖，能取得名次都会缩小为原来的一半,即 的规模只有,故复杂度为

：可以使用滚动数组优化空间，本题没有卡空间，所以可以不使用

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
int n,m,f[2][65],g[2][65],k;
int minn(int x,int y){return x<y?x:y;}
int maxx(int x,int y){return x<y?y:x;}
signed main()
{
    int i,j,x,y,z;
    scanf("%lld%lld",&n,&m);
    for(i=1;i<=n;++i)
    {
        scanf("%lld%lld%lld",&x,&y,&z);
        f[i&1][0]=f[i&1^1][k];if((g[i&1^1][k]>>1)>=y)f[i&1][0]+=z;g[i&1][0]=y;k=0;
        for(j=1;(g[i&1^1][j-1]>>1)>=x;++j)
        {
            f[i&1][j]=f[i&1^1][j-1]+z;
            if(f[i&1][k]<f[i&1][j])k=j;
            g[i&1][j]=minn(g[i&1^1][j-1]>>1,y);
        }
    }
    printf("%lld\n",f[i&1^1][k]);
    return 0;
}

: 30分

只需依题目要求操作即可

: 对于另20分（可获得50分）

保证没有2,3操作，数据范围200000，我们需要一个单次操作 的算法来实现，路径加操作易想到差分，通过将路径拆分为两段进行维护

: 对于另30分（可获得80分）

此时没有3操作，由于只需要在最后输出权值，可以想到离线维护，先将所有需要加的点读入进来建树，再做如上操作
另：每次加入一个点时，将它的边建好，其他需要的信息维护好也可以实现动态维护这个操作

: 40分（100分）

根据上面的思路，可以考虑离线处理本题，可以发现对于3操作，删去节点后始终保证树的连通，隐藏含义即为删去的都是当前树的叶子节点，所以后面增加的点提前加上并不影响前面的修改操作，故只需要先将所有操作读进来，将所有的加入，再标记出已删除的点，判断哪些点仍在树上即可。
时间复杂度 ，若使用tarjan求LCA可以优化至

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f,T=21;
int read()
{
   int s=0,bj=0;
   char ch=getchar();
   while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
   while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
   return bj?-s:s;
}
void printnum(LL x)
{
    if(x>9)printnum(x/10);
    putchar(x%10^48);
}
void print(LL x,char ch)
{
    if(x<0){putchar('-');x=-x;}
    printnum(x);putchar(ch);
}
int f[2000005][22],n,m,d[2000005];
LL v[2000005],num[2000005],ans[2000005];
struct node{int nx,to;}w[4000005];int h[2000005],cnt;
void AddEdge(int x,int y)
{
    w[++cnt].to=y;w[cnt].nx=h[x];h[x]=cnt;
    w[++cnt].to=x;w[cnt].nx=h[y];h[y]=cnt;
}
struct OPT{int opt,x,y,k;}opt[2000005];
bool vst[2000005];
void DFS(int x,int fa)
{
    f[x][0]=fa;d[x]=d[fa]+1;for(int i=1;i<=T;++i)f[x][i]=f[f[x][i-1]][i-1];
    for(int i=h[x];i;i=w[i].nx)
    {
        int y=w[i].to;
        if(y^fa)DFS(y,x);
    }
}
int LCA(int x,int y)
{
    if(d[x]>d[y])swap(x,y);
    for(int i=T;i>=0;--i)if(d[f[y][i]]>=d[x])y=f[y][i];
    if(x==y)return x;
    for(int i=T;i>=0;--i)if(f[x][i]^f[y][i]){x=f[x][i];y=f[y][i];}
    return f[x][0];
}
void Sol(int x,int fa)
{
    ans[x]=v[x];
    for(int i=h[x];i;i=w[i].nx)
    {
        int y=w[i].to;
        if((y^fa)&&vst[y]){Sol(y,x);ans[x]+=ans[y];}
    }
}
int vss[2000005];
int main()
{
    n=read();m=read();for(int i=1;i<=n;++i){vst[i]=1;num[i]=read();}
    for(int i=1;i<n;++i)AddEdge(read(),read());
    for(int i=1;i<=m;++i)
    {
        opt[i].opt=read();opt[i].x=read();
        if(opt[i].opt==1){opt[i].y=read();opt[i].k=read();}
        else if(opt[i].opt==2){int kkk=read();if(vss[kkk])return 1;AddEdge(++n,kkk);num[n]=opt[i].x;vst[n]=1;}
        else vss[opt[i].x]=1;
    }
    DFS(1,0);
    for(int i=1;i<=m;++i)
    {
        int x=opt[i].x,y=opt[i].y,k=opt[i].k;
        if(opt[i].opt==1){v[x]+=k;v[y]+=k;int lca=LCA(x,y);v[lca]-=k;v[f[lca][0]]-=k;}
        else if(opt[i].opt==2)continue;
        else {v[f[x][0]]+=v[x];vst[x]=0;}
    }
    Sol(1,0);
    for(int i=1;i<=n;++i)if(vst[i]){print(i,' ');print(ans[i]+num[i],'\n');}
    return 0;
}

设 表示每一个 的到根求和
因为 ,所以 等价于
同时题目中的每次操作就相当于直接将 加上
于是原问题就等价于每次可以直接单点修改 ，求使得 任意两个节点 和 ，若 为 的祖先，则有 的最小修改次数

做法一：（30分）
设 表示 的子树中最小权值为 的最大子集
转移

做法二：（60分）
在刚刚的基础上优化一下dp的定义
设 表示 的子树中最小权值大于等于 的最大子集
转移
最后在 自己进行更新

做法三：（100分）
可以将上述方法差分后在用线段树合并解决，不过这里着重讲做法四

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace yspm{
    inline int read()
    {
        int res=0,f=1; char k;
        while(!isdigit(k=getchar())) if(k=='-') f=-1;
        while(isdigit(k)) res=res*10+k-'0',k=getchar(); 
        return res*f;
    }
    const int N=2e5+10;
    struct node{
        int ls,rs,sum;
        #define ls(p) t[p].ls
        #define rs(p) t[p].rs
        #define sum(p) t[p].sum
    }t[N<<6];
    int rt[N],tot,p[N],b[N],vv[N],m,n;
    vector<int> g[N];
    inline void update(int &p,int l,int r,int st,int ed,int val)
    {
        if(!p) p=++tot;
        if(l<=st&&ed<=r) return sum(p)++,void();
        int mid=(st+ed)>>1;
        if(l<=mid) update(ls(p),l,r,st,mid,val);
        if(r>mid) update(rs(p),l,r,mid+1,ed,val);
        return ;
    }
    inline int merge(int x,int y,int l,int r)
    {
        if(!x||!y) return x+y;
        if(l==r) return sum(x)+=sum(y),x;
        int mid=(l+r)>>1,p=++tot; sum(p)=sum(x)+sum(y);
        ls(p)=merge(ls(x),ls(y),l,mid);
        rs(p)=merge(rs(x),rs(y),mid+1,r);
        return p;
    }
    inline int query(int p,int l,int r,int x)
    {
        if(!p||x>m) return 0;
        int mid=(l+r)>>1;
        if(x<=mid) return sum(p)+query(ls(p),l,mid,x);
        else return sum(p)+query(rs(p),mid+1,r,x);
    }
    inline void dfs(int x,int fa)
    {
        int siz=g[x].size();
        for(int i=0;i<siz;++i) 
        {
            int t=g[x][i];
            if(t==fa)continue;dfs(t,x);
            rt[x]=merge(rt[x],rt[t],1,m);
        } 
        int now=query(rt[x],1,m,p[x]+1)+1;
        if(now<=query(rt[x],1,m,p[x])) return ;
        int l=1,r=p[x];
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(query(rt[x],1,m,mid)<now) r=mid; 
            else l=mid+1;
        }
        return update(rt[x],r,p[x],1,m,1);
    }
    inline void dfs1(int x,int fa,int ppp)
    {
        vv[x]+=ppp;
        int siz=g[x].size();
        for(int i=0;i<siz;++i) 
        {
            int t=g[x][i]; 
            if(t==fa)continue;
            dfs1(t,x,vv[x]);
        } 
    }
    signed main()
    {
        n=read(); 
        for(int i=1;i<=n;++i)vv[i]=read();
        for(int i=2,x,y;i<=n;++i) x=read(),y=read(),g[x].push_back(y),g[y].push_back(x);
        dfs1(1,0,0);
        for(int i=1;i<=n+1;++i) p[i]=vv[i],b[++m]=p[i];
        sort(b+1,b+m+1); m=unique(b+1,b+m+1)-b-1;
        g[n+1].push_back(1);g[1].push_back(n+1);
        for(int i=1;i<=n+1;++i) p[i]=lower_bound(b+1,b+m+1,p[i])-b;
        dfs(n+1,0);
        int ans=0;
        for(int i=1;i<=m;++i) ans=max(ans,query(rt[n+1],1,m,i));
        cout<<n+1-ans<<endl; 
        return 0;
    }
}
signed main(){
return yspm::main();}

做法四：（100分）
由于每个点只会被修改1次，求最小修改次数就等价于 n-求最多不被修改的点数
考虑一种贪心方案，我们让子树内最小点权尽量大，为新来的点留位置 二分优化 LIS,现在我们依然二分，然后因为多线程合并采用启发式合并套一个有序的结构，使用multiset即可
由于这样并不能保证1号节点所以加入一个虚根0令 且建0到1的边即可

#include<bits/stdc++.h>
#define _I inline
#define _R register
#define ll long long
#define ull unsigned long long
#define eps 1e-4
#define mod 1000000007
#define INF 0x3f3f3f3f
#define y1 yy1
#define memset(x,y) memset(x,y,sizeof(x))
#define memcpy(x,y) memcpy(x,y,sizeof(x))
#define int ll
using namespace std;
_I int read(){
    int x=0;bool f=0;char ch=getchar();
    while(ch<'0'||ch>'9')f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    f&&(x=-x);
    return x;
}
const int N=200005;
int n,cnt,nx[N<<1],to[N<<1],head[N],val[N];
multiset<int>s[N];
multiset<int>::iterator it;
void addedge(int x,int y){
    nx[++cnt]=head[x];to[cnt]=y;head[x]=cnt;
}
void merge(int x,int y){
    if(s[x].size()<s[y].size())swap(s[x],s[y]);
    for(it=s[y].begin();it!=s[y].end();++it)s[x].insert(*it);
}
void dfs(int x,int fa){
    for(_R int i=head[x];~i;i=nx[i])if(to[i]!=fa)dfs(to[i],x),merge(x,to[i]);
    s[x].insert(val[x]);
    it=s[x].lower_bound(val[x]);
    if(it!=s[x].begin())s[x].erase(--it);
}
void dfs1(int x,int fa,int dep){
    val[x]=dep;
    for(_R int i=head[x];~i;i=nx[i])if(to[i]!=fa)dfs1(to[i],x,dep+val[to[i]]);
}
signed main(){
    n=read();memset(head,-1);
    for(_R int i=1;i<=n;++i)val[i]=read();
    addedge(0,1);val[0]=0;
    for(_R int i=1,x,y;i<n;++i)x=read(),y=read(),addedge(x,y),addedge(y,x);
    dfs1(1,0,val[1]);
    dfs(0,-1);
    printf("%lld",n+1-s[0].size());
    return 0;
}