[考试反思]1002csp-s模拟测试56：凌乱

放假回来状态回升？？（玩够了～但是稍困）

T1打的不完全对，但是过掉了。很快的想到了二分吧喇叭啦。。

然后T2也挺快想出来了但是挂细节没发现，考试快结束的时候才发现出锅了。

改了过来是正解，但是出题人无良卡了线段树强制树状数组，T了一个子任务，卡常到飞起。

T3暴力没什么问题。

卡常是一种习惯。要注意题目数据范围观察是否卡常。

T1：Merchant

所有的决策都是一条一次函数。

分两类，斜率正或斜率非负。

如果第二类的直线里有在T=0时符合要求的，那么答案就是0，所以check(0)一下。

如果非负的直线都在T=0时不符合要求，那么以后这些直线都不符合要求了。

所以排除，只剩下斜率为正的直线了，它们到底什么时候符合要求？

因为斜率都是正的，那么现在符合要求以后也一定符合，满足单调性。

二分。贪心。nth_element（sort被卡复杂度）。

注意判断价值为负的物品不选，而不是一定选满m个。

#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
int n,m,S,k[1000005],b[1000005],res[1000005];
bool chk(int tim){int tot=0;//printf("%lld ",tim);
    for(int i=1;i<=n;++i)res[i]=k[i]*tim+b[i];
    nth_element(res+1,res+n-m+1,res+n+1);
    for(int i=n-m+1;i<=n;++i)if(res[i]>=0){tot+=res[i];if(tot>=S)return true;}//printf("%lld %lld
",tot,S);
    return tot>=S;
}
main(){//freopen("merchant3.in","r",stdin);
    scanf("%lld%lld%lld",&n,&m,&S);//printf("%lld %lld
",n,m);
    for(int i=1;i<=n;++i)scanf("%lld%lld",&k[i],&b[i]);
    int l=0,r=1000000000;
    while(l<r-1)if(chk(l+r>>1))r=l+r>>1;else l=(l+r>>1)+1;
    printf("%lld
",chk(l)?l:r);
}

同理可证总决策线是个单谷函数。

思路积累：

• 分类讨论：直线斜率的正负。

T2：Equation

因为是一棵树，设根的权值为x，那么每个点的权值都可以根据路径上的方程来表示为含x的式子：x+a或a-x。a是常数

然后对于询问，分类讨论解方程即可。

对于修改，子树内的点的表达式都有变化。

可以发现，深度为奇数的点都是加，偶数的点都是减。

第一想法是线段树，直接子树加，在叶节点特殊处理加减即可。

#include<cstdio>
int n,q,dep[1000005],f[1000005],w[1000005],W[1000005],tim,re[1000005];
int fir[1000005],l[1000005],to[1000005],cnt,dfn[1000005],rdfn[1000005];
void link(int a,int b){l[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;}
void dfs(int p){
    dep[p]=dep[f[p]]+1;w[p]=W[p]-w[f[p]];dfn[p]=++tim;re[tim]=p;
    for(int i=fir[p];i;i=l[i])dfs(to[i]);rdfn[p]=tim;
}
struct Segment_Tree{
    int cl[4000005],cr[4000005],tw[4000005],lz[4000005];
    void build(int l,int r,int p=1){
        cl[p]=l;cr[p]=r;
        if(l==r){tw[p]=w[re[l]];return;}
        build(l,l+r>>1,p<<1);build((l+r>>1)+1,r,p<<1|1);
    }
    void down(int p){
        tw[p<<1]+=lz[p]*((dep[re[cl[p<<1]]]&1)?1:-1);
        tw[p<<1|1]+=lz[p]*((dep[re[cl[p<<1|1]]]&1)?1:-1);//printf("down:%d %d
",re[cl[p<<1]],re[cr[p<<1|1]]);
        lz[p<<1]+=lz[p];lz[p<<1|1]+=lz[p];
        lz[p]=0;
    }
    void add(int l,int r,int _w,int p=1){//printf("add:%d %d %d
",p,cl[p],cr[p]);
        if(l<=cl[p]&&cr[p]<=r){lz[p]+=_w;tw[p]+=_w*((dep[re[cl[p]]]&1)?1:-1);return;}
        if(lz[p])down(p);
        if(l<=cr[p<<1])add(l,r,_w,p<<1);
        if(r>=cl[p<<1|1])add(l,r,_w,p<<1|1);
    }
    int ask(int pos,int p=1){
        if(cl[p]==cr[p])return tw[p];
        if(lz[p])down(p);
        return pos<=cr[p<<1]?ask(pos,p<<1):ask(pos,p<<1|1);
    }
}T;
int main(){
    scanf("%d%d",&n,&q);
    for(int i=2;i<=n;++i)scanf("%d%d",&f[i],&W[i]),link(f[i],i);
    dfs(1);T.build(1,n);//for(int i=1;i<=n;++i)printf("%d ",w[i]);
    for(int i=1,opt,u,v,ww;i<=q;++i){
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d%d",&u,&v,&ww);int Q=T.ask(dfn[u])+T.ask(dfn[v]);//printf("%d %d
",T.ask(dfn[u]),T.ask(dfn[v]));
            if(dep[u]&1^dep[v]&1)puts(Q==ww?"inf":"none");
            else if(Q-ww&1)puts("none");
            else if(dep[u]&1)printf("%d
",ww-Q>>1);
            else printf("%d
",Q-ww>>1);
        }else scanf("%d%d",&u,&ww),T.add(dfn[u],rdfn[u],(ww-W[u])*((dep[u]&1)?1:-1)),W[u]=ww;
    }
}

那么考虑如何用树状数组来维护。

区间加，单点查询。树状数组不能直接做，所以要差分。

根据度数奇偶加减不同，那么如果我们把度数为奇数的点都取相反数。

取出来的时候再相反数一下就好了。

#include<cstdio>
#define int long long
int dep[1000005],f[1000005],w[1000005],W[1000005],tim,re[1000005],n;
int fir[1000005],l[1000005],to[1000005],cnt,dfn[1000005],rdfn[1000005];
inline void link( int a, int b){l[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;}
const int L=1<<20|1;
char buffer[L],*S,*TT;
#define getchar() ((S==TT&&(TT=(S=buffer)+fread(buffer,1,L,stdin),S==TT))?EOF:*S++)
const int maxn=100000+5;
inline int read(register int &p,register int nt=1,register char ch=getchar()){p=0;
    while(ch>'9'||ch<'0'){if(ch=='-')nt=-1;ch=getchar();}
    while(ch<='9'&&ch>='0')p=(p<<3)+(p<<1)+ch-48,ch=getchar();p*=nt;
}
void dfs(int p){
    dep[p]=dep[f[p]]^1;w[p]=W[p]-w[f[p]];dfn[p]=++tim;re[tim]=p;
    for(int i=fir[p];i;i=l[i])dfs(to[i]);rdfn[p]=tim;
}
struct Tree_Array{
    int t[1000005];
    inline void ADD(int p,int w){for(;p<=1000000;p+=p&-p)t[p]+=w;}
    inline int SUM(int p,int a=0){for(;p;p^=p&-p)a+=t[p];return a;}
    inline void add(int L,int R,int w){ADD(L,w);ADD(R+1,-w);}
    inline int ask(int p){return SUM(p)*(dep[re[p]]?1:-1);}
    inline void build(){for(int i=1;i<=n;++i)ADD(i,(w[re[i]]*(dep[re[i]]?1:-1))-(w[re[i-1]]*(dep[re[i-1]]?1:-1)));}
}T;
main(){
    int q;scanf("%d%d",&n,&q);
    for(int i=2;i<=n;++i)read(f[i]),read(W[i]),link(f[i],i);
    dfs(1);T.build();
    for(int i=1,opt,u,v,ww;i<=q;++i){
        read(opt);
        if(opt==1){
            read(u);read(v);read(ww); int Q=T.ask(dfn[u])+T.ask(dfn[v]);
            if(dep[u]^dep[v])puts(Q==ww?"inf":"none");
            else if(Q-ww&1)puts("none");
            else if(dep[u])printf("%d
",ww-Q>>1);
            else printf("%d
",Q-ww>>1);
        }else read(u),read(ww),T.add(dfn[u],rdfn[u],(ww-W[u])*(dep[u]?1:-1)),W[u]=ww;
    }
}

思路积累：

• 树状数组维护特殊操作：存相反数

T3：

还在改。咕。。。

---

其实不是不会写而咕。

但是第二机房实在是太颓了。。。效率超低。。。

一下午基本什么都没干。。

再不回去我可能就要毁了。。。

但是看现在这个总分好像还是很悬啊。。。

我想回去。。。

---