[NOIP10.6模拟赛]2.equation题解--DFS序+线段树

题目链接:

咕

闲扯:

终于在集训中敲出正解(虽然与正解不完全相同),开心QAQ

首先比较巧,这题是\(Ebola\)出的一场模拟赛的一道题的树上强化版,当时还口胡出了那题的题解

然而考场上只得了86最后一个substask被卡了,一开始以为毒瘤出题人卡常(虽然真卡了)卡线段树,题目时限1.5s,评测机上两个点擦线1500ms左右,剩下两个点不知道。然后本地测一下都是1900+ms!机子性能已经这样了吗....结果把快读换成\(fread\),TM过了!最慢的1200+ms!!!这......无话可说,\(getchar()\)快读也卡讲究

分析:

首先最简单的处理不讲了.就是把每个点的未知数表示成\(k_i x_1 + b_i\)的形式,这DFS一遍就好了

然后观察到有一个1e3的子任务,想想暴力怎么做,我们对于操作1,相当于\((k_i+k_j)x_1+(b_i+b_j)=w\)判断一下解得情况就好了,\(O(1)\)完成;

对于操作2,我们可以发现对于\(x\)的操作,只会对\(x\)的子树中的\(k_ix_1+b_i\)形式有影响(实际上只会影响\(b_i\)),于是\(DFS\)一遍子树即可,这样总的暴力时间复杂度是\(O(nq)\)

考虑优化暴力,

我们发现瓶颈是操作2,如果将\(x\)与其父亲的边权从\(w_1\)改为\(w_2\),那么加入\(x\)本来形式是\(k_ix_1+b_i\),这时候变成了\(k_i x_1+b_i+w_2-w_1\),相当于加操作,当时在\(x\)的子树中与\(x\)的\(k_i\)(实际上显然只有-1,1两种取值)不同的点,\(b\)值却应该减去\(w_2-w_1\),所以我们将标记开成一个二元组,一个记录标记的正负,另一个记录值,重载下运算符就很方便了

struct Tag{

        int o;//标记的正负

        ll dt;

        Tag(){o=dt=0;}

        Tag(int o){o=dt=o;}

        Tag(int _o,ll _dt){o=_o,dt=_dt;}

        Tag operator +(const Tag &b)const{

            Tag tmp=*this;

            if(tmp.o==0)tmp=b;

            else if(b.o==0)return tmp;

            else {

            	if(o!=b.o){

               	 tmp.dt=dt-b.dt;

            	}

            	else tmp.dt=dt+b.dt;

            }

            return tmp;

        }

    };

这样对于操作2,只用在子树加个标记就好了,因为dfs序是一段连续区间(我比较傻考场上是用树链剖分)使用线段树就好了

对于操作1,我们两次单点查询就好了,然后按暴力那样处理.

总的时间复杂度\(O(q log N)\),常数稍大

当然标算std是将深度分奇偶考虑,然后树状数组维护差分标记,时间复杂度相同但是常数小的多

代码

这是考场代码换了快读,如果想看线段树部分直接跳到\(niconicoi\)那个\(namespace\)就好了

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

#include <queue>

#include <cmath>

#include <vector>

#define ll long long

#define ri register int

using std::min;

using std::abs;

using std::max;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

template <class T>inline void read(T &x){

    x=0;int ne=0;char c;

    while(!isdigit(c=nc()))ne=c=='-';

    x=c-48;

    while(isdigit(c=nc()))x=(x<<3)+(x<<1)+c-48;

    x=ne?-x:x;return ;

}

const int maxn=100005;

const int inf=0x7fffffff;

const int N=1000005;

struct Edge{

    int ne,to;

    ll dis;

}edge[N<<1];

int h[N],num_edge=1;

inline void add_edge(int f,int to,int c){

    edge[++num_edge].ne=h[f];

    edge[num_edge].to=to;

    edge[num_edge].dis=c;

    h[f]=num_edge;

}

struct Wt{

    int ki;

    ll bi;

    Wt(){ki=bi=0;}

    Wt(int _k,ll _b){ki=_k,bi=_b;}

}pt[N];

int n,q;

int fafa[N],fa_id[N];

namespace wtf{

    void main(){

        /*orz*/

        return ;

    }

}

void pre_dfs(int now,int fa){

    int v;

    int x=pt[now].ki,y=pt[now].bi;

    for(ri i=h[now];i;i=edge[i].ne){

        v=edge[i].to;

        if(v==fa)continue;

        fafa[v]=now;

        fa_id[v]=i;

        pt[v]=Wt(-x,edge[i].dis-y);

        pre_dfs(v,now);

    }

    return;

}

namespace qwq{

    void main(){

        int op,x,y;ll dd;

        ll p=edge[2].dis;

        while(q--){

            read(op),read(x),read(y);

            if(op==1){

                read(dd);

                if(x!=y){

                    if(dd==p){

                        puts("inf");

                    }

                    else{

                        puts("none");

                    }

                }

                else {

                    if(x==1){

                        if(dd%2)puts("none");

                        else printf("%lld\n",dd/2);

                    }

                    if(x==2){

                        ll tt=2*p-dd;

                        if(tt%2)puts("none");

                        else printf("%lld\n",tt/2);

                    }

                }

            }

            else{

                p=y;

            }

        }

        return ;

    }

}

namespace task_1{

    void main(){

        int op,x,y;ll dd;

        int kk,bb;

        while(q--){

            read(op),read(x),read(y);

            if(op==1){

                read(dd);

                kk=pt[x].ki+pt[y].ki;

                bb=pt[x].bi+pt[y].bi;

                dd=dd-bb;

                if(kk==0){

                    if(dd==0)puts("inf");

                    else puts("none");

                }

                else if(dd%abs(kk)!=0)puts("none");

                else printf("%lld\n",dd/kk);

            }

            else {

                edge[fa_id[x]].dis=y;

                edge[fa_id[x]^1].dis=y;

                pre_dfs(fafa[x],fafa[fafa[x]]);

            }

        }

        return ;

    }

}

namespace niconiconi{

    int dep[N],top[N],son[N],size[N],dfn[N],rnk[N],tot=0;

    void print(ll xxx){

        if(!xxx)return ;

		print(xxx/10);

        putchar(xxx%10+'0');

        return ;

    }

    void dfs_1(int now){

        int v;size[now]=1;

        for(ri i=h[now];i;i=edge[i].ne){

            v=edge[i].to;

            if(v==fafa[now])continue;

            dep[v]=dep[now]+1;

            dfs_1(v);

            size[now]+=size[v];

            if(!son[now]||size[son[now]]<size[v])son[now]=v;

        }

        return ;

    }

    void dfs_2(int now,int t){

        int v;top[now]=t;

        dfn[now]=++tot,rnk[tot]=now;

        if(!son[now])return ;

        dfs_2(son[now],t);

        for(ri i=h[now];i;i=edge[i].ne){

            v=edge[i].to;

            if(v==fafa[now]||v==son[now])continue;

            dfs_2(v,v);

        }

        return ;

    }

    struct Tag{

        int o;//标记的正负

        ll dt;

        Tag(){o=dt=0;}

        Tag(int o){o=dt=o;}

        Tag(int _o,ll _dt){o=_o,dt=_dt;}

        Tag operator +(const Tag &b)const{

            Tag tmp=*this;

            if(tmp.o==0)tmp=b;

            else if(b.o==0)return tmp;

            else {

            	if(o!=b.o){

               	 tmp.dt=dt-b.dt;

            	}

            	else tmp.dt=dt+b.dt;

            }

            return tmp;

        }

    };

	Tag tag[N<<2];

    void build(int now,int l,int r){

        tag[now]=Tag(0);

        if(l==r){

            return ;

        }

        int mid=(l+r)>>1;

        build(now<<1,l,mid);

        build(now<<1|1,mid+1,r);

        return ;

    }

    int L,R;

    Tag dta;

    inline void pushdown(int now){

        if(tag[now].o==0)return ;

        tag[now<<1]=tag[now<<1]+tag[now];

        tag[now<<1|1]=tag[now<<1|1]+tag[now];

        tag[now]=Tag(0);

        return ;

    }

    void update(int now,int l,int r){

        if(L<=l&&r<=R){

            tag[now]=tag[now]+dta;

            return ;

        }

        int mid=(l+r)>>1;

        pushdown(now);

        if(L<=mid)update(now<<1,l,mid);

        if(mid<R)update(now<<1|1,mid+1,r);

        return ;

    }

    Wt pa,pb;

	int t;

    void query(int now,int l,int r){

        if(l==r){

            //int kkk=pt[rnk[l]].ki,bbb=pt[rnk[l]].bi;

            if(tag[now].o!=0){

                if(tag[now].o!=pt[rnk[l]].ki){

                    pt[rnk[l]].bi-=tag[now].dt;

                }

                else{

                    pt[rnk[l]].bi+=tag[now].dt;

                }

                tag[now]=Tag(0);

            }

            //pa.ki=pt[rnk[l]].ki;

            //pa.bi=pt[rnk[l]].bi;

            return;

        }

        int mid=(l+r)>>1;

        pushdown(now);

        if(t<=mid)query(now<<1,l,mid);

        else query(now<<1|1,mid+1,r);

        return ;

    }

    void main(){

        int op,x,y;

        ll kk,bb,dd;

        dep[1]=0;

        dfs_1(1);

        dfs_2(1,1);

        build(1,1,n);

        while(q--){

            read(op),read(x),read(y);

            if(op==1){

                read(dd);

                t=dfn[x];//pa=Wt(0,0);

                query(1,1,n);

                t=dfn[y];//pb=Wt(pa.ki,pa.bi),pa=Wt(0,0);

                query(1,1,n);

                //printf("%d %d %d %d\n",pa.ki,pb.ki,pa.bi,pb.bi);

                kk=pt[x].ki+pt[y].ki;

                bb=pt[x].bi+pt[y].bi;

                dd=dd-bb;

                if(kk==0){

                    if(dd==0)puts("inf");

                    else puts("none");

                }

                else if(dd%abs(kk)!=0)puts("none");

                else {

                    if(dd==0)puts("0");

                    else {

                    	dd=dd/kk;

                    	if(dd<0)dd=-dd,putchar('-');

						print(dd);

						puts("");

					}

                    //printf("%lld\n",dd/kk);

                }

            }

            else {

                dd=edge[fa_id[x]].dis;

                edge[fa_id[x]].dis=edge[fa_id[x]^1].dis=y;

                dd=1ll*y-dd;

                //printf("%lld\n",dd);

                L=dfn[x],R=dfn[x]+size[x]-1;

                //t=dfn[x];pa=Wt(0,0);

                //query(1,1,n);

                pa=pt[x];

                //printf("%d\n",pa.ki);

                dta=Tag(pa.ki,dd);

                update(1,1,n);

                //update_subtree()

            }

        }

        return ;

    }

}

int main(){

    int x,y;

    freopen("equation.in","r",stdin);

    freopen("equation.out","w",stdout);

    read(n),read(q);

    for(ri i=2;i<=n;i++){

        read(x),read(y);

        add_edge(i,x,y);

        add_edge(x,i,y);

    }

    pt[1].ki=1,pt[1].bi=0;

    fafa[1]=0;

    pre_dfs(1,0);

    if(q==0)wtf::main();

    else if(n==2)qwq::main();

    else if(n<=2000)task_1::main();

    else niconiconi::main();

    fclose(stdin);

    fclose(stdout);

    return 0;

}

巴特西

[NOIP10.6模拟赛]2.equation题解--DFS序+线段树

题目链接:

闲扯:

分析:

代码

最新文章

热门文章