牛客网字节跳动冬令营网络赛J Sortable Path on Tree —

题目：https://ac.nowcoder.com/acm/contest/296/J

用点分治；

记录了值起伏的形态，二元组 (x,y) 表示有 x 个小于号，y 个大于号；

因为小于号和大于号都 >=2 就不合法了，所以状态是 3×3 的；

然后根据各种形态拼接...写了一晚上，最后连最简单的样例都过不了了...

感觉似乎走入歧途了，这样讨论太麻烦...

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define pb push_back

using namespace std;

typedef long long ll;

int const xn=1e5+,inf=1e9;

int n,hd[xn],ct,to[xn<<],nxt[xn<<],w[xn],siz[xn],rt,mx,sum,wmx;

ll ans,b[][][xn];

bool vis[xn];

struct N{

  int x,y,v;

  N(int x=,int y=,int v=):x(x),y(y),v(v) {}

};

vector<N>tmp;

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}

void ins(int x,int y,int p){for(;p<=wmx;p+=(p&-p))b[x][y][p]++;}

int query(int x,int y,int p){int ret=; for(;p;p-=(p&-p))ret+=b[x][y][p]; return ret;}

int upquery(int x,int y,int p){return query(x,y,wmx)-query(x,y,p-);}

void getrt(int x,int fa)

{

  siz[x]=; int nmx=;

  for(int i=hd[x],u;i;i=nxt[i])

    {

      if((u=to[i])==fa)continue;

      getrt(u,x); siz[x]+=siz[u];

      if(siz[u]>nmx)nmx=siz[u];

    }

  nmx=max(nmx,sum-siz[x]);

  if(nmx<mx)mx=nmx,rt=x;

}

void update(int t1,int t2,int a1)

{

  if(t1==&&t2==)ans+=query(,,wmx)+query(,,wmx)+query(,,wmx)+query(,,wmx)+query(,,wmx)+upquery(,,a1)+query(,,a1),ans++;

  //--\ , --/ , --__ , --`` , --``__ , --.\ , --/.

  if(t1==&&t2==)ans+=query(,,a1)+query(,,wmx)+query(,,wmx)+query(,,wmx)+upquery(,,a1)+upquery(,,a1),ans++;

  //--__/ , ``--\ , --__-- , ``--__ , ``--__`` , ``--\`

  if(t1==&&t2==)ans+=query(,,wmx)+query(,,wmx)+upquery(,,a1)+upquery(,,a1)+upquery(,,a1),ans++;//``\--\ , ``\--__ , --\__`` , ``\--__`` , ``\.`

  if(t1==&&t2==)ans+=query(,,a1)+query(,,wmx)+upquery(,,a1)+query(,,wmx)+query(,,a1)+query(,,a1),ans++;

  //__``-- , __--/ , __-- \ , __--`` , __--``__ , __--``.

  if(t1==&&t2==)ans+=query(,,a1)+query(,,a1)+upquery(,,a1)+upquery(,,a1),ans++;//--``__-- , --``__/ , --__``-- , --__``\ 

  if(t1==&&t2==)ans+=upquery(,,a1)+upquery(,,a1),ans++;//.\--__ , .\--\

  if(t1==&&t2==)ans+=query(,,wmx)+query(,,a1)+query(,,wmx)+query(,,a1)+query(,,a1),ans++;// // , /``__ , /--`` , /--``__ , /`.

  if(t1==&&t2==)ans+=query(,,a1)+query(,,a1),ans++;// /.--`` , /./

}

void dfs(int x,int fa,int s1,int s2)//to rt

{

  if(w[x]<w[fa])s1++; if(w[x]>w[fa])s2++;

  if((s1>=&&s2==&&w[rt]>w[x])||(s1==&&s2>=&&w[rt]<w[x]))return;//&&

  int t1=min(s1,),t2=min(s2,);

  ans+=query(,,wmx); update(t1,t2,w[x]);

  //printf("x=%d ans=%lld t1=%d t2=%d\n",x,ans,t1,t2);

  tmp.pb(N(t2,t1,w[x]));

  for(int i=hd[x],u;i;i=nxt[i])

    if((u=to[i])!=fa&&!vis[u])dfs(u,x,s1,s2);

}

/*

void update2(int t1,int t2,int a1)

{

  if(t1==0&&t2==0)ans+=query(0,1,wmx)+query(0,2,wmx)+query(1,0,wmx)+query(1,1,wmx)+query(2,0,mx),ans++;//--__ , --\__ , --`` , --``__ , --/

  if(t1==0&&t2==1)ans+=query(0,2,wmx)+query(1,0,wmx)+query(2,0,a1)+query(0,1,wmx),ans++;//``\--__ , __--__ , /``__ , ``--__

  if(t1==0&&t2==2)ans+=query(0,1,wmx)+query(0,2,wmx)+query(1,0,a1),ans++;//``--\ , ``\--\ , __``\

  if(t1==1&&t2==0)ans+=query(0,1,wmx)+query(0,2,a1)+query(1,0,wmx)+upquery(1,1,a1)+query(2,0,wmx),ans++;//--__-- , --\__`` , __--`` , --``__-- , /--``

  if(t1==1&&t2==1)ans+=upquery(1,0,a1)+upquery(2,0,a1),ans++;//__--``__ , /--``__

  if(t1==2&&t2==0)ans+=query(0,1,a1)+query(1,0,wmx)+upquery(1,1,a1)+query(2,0,wmx),ans++;//--__/ , __--/ , --``__/ , //

}

void dfs2(int x,int fa,int s1,int s2)//from rt

{

  if(w[x]<w[fa])s2++; if(w[x]>w[fa])s1++;

  if((s1>=2&&s2==1)||(s1==1&&s2>=2))return;

  int t1=min(s1,2),t2=min(s2,2);

  ans+=query(0,0,wmx); update2(t1,t2,w[x]);

  tmp.pb(N(t1,t2,w[x]));

  for(int i=hd[x],u;i;i=nxt[i])

    if((u=to[i])!=fa&&!vis[u])dfs2(u,x,s1,s2);

}

*/

void work(int x,int ss)

{

  printf("x=%d\n",x);

  vis[x]=;//

  memset(b,,sizeof b);

  for(int i=hd[x],u;i;i=nxt[i])

    {

      if(vis[u=to[i]])continue;

      dfs(u,x,,);

      printf("u=%d\n",u);

      for(int j=;j<tmp.size();j++){ins(tmp[j].x,tmp[j].y,tmp[j].v);

    printf("t(%d,%d,%d)\n",tmp[j].x,tmp[j].y,tmp[j].v);}

      printf("ans=%lld\n",ans);

      tmp.clear();

    }

  /*  //无序

  memset(b,0,sizeof b);

  for(int i=hd[x],u;i;i=nxt[i])

    {

      if(vis[u=to[i]])continue;

      dfs2(u,x,0,0);

      for(int j=0;j<tmp.size();j++)ins(tmp[j].x,tmp[j].y,tmp[j].v);

      tmp.clear();

    }

  */

  for(int i=hd[x],u;i;i=nxt[i])

    {

      if(vis[u=to[i]])continue;

      sum=(siz[u]>siz[x]?ss-siz[x]:siz[x]); mx=inf;

      getrt(u,); work(u,sum);//(u,0)

    }

}

int main()

{

  int T=rd();

  while(T--)

    {

      n=rd();

      ct=; memset(hd,,sizeof hd); wmx=;

      memset(vis,,sizeof vis);

      for(int i=;i<=n;i++)w[i]=rd(),wmx=max(wmx,w[i]);

      for(int i=,x,y;i<n;i++)x=rd(),y=rd(),add(x,y),add(y,x);

      sum=n; mx=inf; getrt(,);//

      ans=; work(rt,sum);

      printf("%lld\n",ans+n);//

    }

  return ;

}

艰难尝试

然后看了看AC代码，也有一篇拼形态的，看了半天没看懂...

其实应该是不用拼形态的，直接考虑拼起来以后的大于号、小于号情况来判断是否对两个端点的值有要求；

如果拼起来以后是 (0,~) 或 (~,0) 或 (1,1)，那么对前后端点值的大小是没有限制的；

如果是 (1,~)，小于号只有一个，那么一定是两个下降的段，要求前端的值 <= 后端的值，才可以从小于号的地方断开，成为有序的；

如果是 (~,1)，大于号只有一个，同理，前端的值 >= 后端的值；

所以只要考虑拼完以后的形态就可以了，讨论变得简单许多；

注意判掉不合法的情况，而且每个点自己单独也是一种合法的情况；

清空树状数组时不要暴力使复杂度剧增，可以再 dfs 一遍，把刚才加上的减去；

可以对值域先离散化，加快树状数组的查询；

注意点分治不要写错；

注意本题没有对 1e9+7 取模呵呵。

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define pb push_back

using namespace std;

typedef long long ll;

int const xn=1e5+,inf=1e9;

int n,hd[xn],ct,to[xn<<],nxt[xn<<],w[xn],siz[xn],mx,sum,rt,wmx,b[][][xn];

ll ans;

bool vis[xn];

struct N{

  int u,v,w;

  N(int u=,int v=,int w=):u(u),v(v),w(w) {}

};

vector<N>tmp;

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}

void ins(int x,int y,int p,int v){for(;p<=wmx;p+=(p&-p))b[x][y][p]+=v;}

int query(int x,int y,int p){if(!p)return ; int ret=; for(;p;p-=(p&-p))ret+=b[x][y][p]; return ret;}

int upquery(int x,int y,int p){return query(x,y,wmx)-query(x,y,p-);}

void getrt(int x,int fa)

{

  siz[x]=; int nmx=;

  for(int i=hd[x],u;i;i=nxt[i])

    {

      if((u=to[i])==fa||vis[u])continue;

      getrt(u,x); siz[x]+=siz[u];

      if(nmx<siz[u])nmx=siz[u];

    }

  nmx=max(nmx,sum-siz[x]);

  if(nmx<mx)mx=nmx,rt=x;

}

void update(int s1,int s2,int w)

{

  ans++;

  for(int i=;i<=;i++)

    for(int j=;j<=;j++)

      {

    int t1=s1+i,t2=s2+j;

    if(t1>=&&t2>=)continue;

    if(!t1||!t2||(t1==&&t2==))ans+=query(i,j,wmx);

    else if(t1==)ans+=upquery(i,j,w);

    else if(t2==)ans+=query(i,j,w);

      }

}

void dfs(int x,int fa,int s1,int s2)

{

  if(w[x]<w[fa])s1++; if(w[x]>w[fa])s2++;

  if(s1>)s1=; if(s2>)s2=;

  if((s1==&&s2==)||(s1==&&s2==&&w[x]>w[rt])||(s1==&&s2==&&w[x]<w[rt]))return;

  update(s1,s2,w[x]); tmp.pb(N(s1,s2,w[x]));

  //printf("x=%d s1=%d s2=%d ans=%d\n",x,s1,s2,ans);

  for(int i=hd[x],u;i;i=nxt[i])

    if((u=to[i])!=fa&&!vis[u])dfs(u,x,s1,s2);

}

void clear(int x,int fa,int s1,int s2)

{

  if(w[x]<w[fa])s1++; if(w[x]>w[fa])s2++;

  if(s1>)s1=; if(s2>)s2=;

  if((s1==&&s2==)||(s1==&&s2==&&w[x]>w[rt])||(s1==&&s2==&&w[x]<w[rt]))return;

  ins(s2,s1,w[x],-);

  for(int i=hd[x],u;i;i=nxt[i])

    if((u=to[i])!=fa&&!vis[u])clear(u,x,s1,s2);

}

void work(int x,int ss)

{

  //printf("x=%d\n",x);

  vis[x]=;

  for(int i=hd[x],u;i;i=nxt[i])

    {

      if(vis[u=to[i]])continue;

      dfs(u,x,,); int siz=tmp.size();

      for(int j=;j<siz;j++)ins(tmp[j].v,tmp[j].u,tmp[j].w,);

      tmp.clear();

    }

  for(int i=hd[x],u;i;i=nxt[i])

    {

      if(vis[u=to[i]])continue;

      clear(u,x,,);

    }

  for(int i=hd[x],u;i;i=nxt[i])

    {

      if(vis[u=to[i]])continue;

      sum=(siz[u]>siz[x]?ss-siz[x]:siz[u]);//siz[u]!

      mx=inf; getrt(u,); work(rt,sum);

    }

}

int tt[xn];

int main()

{

  int T=rd();

  while(T--)

    {

      n=rd();

      ct=; for(int i=;i<=n;i++)hd[i]=;

      for(int i=;i<=n;i++)w[i]=rd(),tt[i]=w[i];

      sort(tt+,tt+n+); wmx=unique(tt+,tt+n+)-tt-;

      for(int i=;i<=n;i++)w[i]=lower_bound(tt+,tt+wmx+,w[i])-tt;

      for(int i=,x,y;i<n;i++)x=rd(),y=rd(),add(x,y),add(y,x);

      ans=; for(int i=;i<=n;i++)vis[i]=;

      mx=inf; sum=n; getrt(,); work(rt,n);

      printf("%lld\n",ans+n);

    }

  return ;

}

巴特西

牛客网字节跳动冬令营网络赛J Sortable Path on Tree —— 点分治

最新文章

热门文章