Query on a tree IV SPOJ

点分就没有一道不卡常的？

卡常记录：

1.把multiset换成手写的带删除堆（套用pq）（作用很大）

2.把带删除堆里面pq换成用vector+push_heap/pop_heap（作用较小）

 #pragma GCC optimize("Ofast")

 #pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")

 #pragma GCC diagnostic error "-fwhole-program"

 #pragma GCC diagnostic error "-fcse-skip-blocks"

 #pragma GCC diagnostic error "-funsafe-loop-optimizations"

 #pragma GCC diagnostic error "-std=c++14"

 #include<cstdio>

 #include<algorithm>

 #include<queue>

 using namespace std;

 struct E

 {

     int to,nxt,d;

 }e[];

 int f1[],ne;

 int ff[],n,sum,fx[],sz[];

 int eu[],pos[],dpx[],dpx2[],st[][],log2x[],lft[];

 int root;

 bool fl[],vis[];

 struct xxx

 {

 priority_queue<int> q1,q2;int sz;

 void insert(int x){q1.push(x);++sz;}

 void erase(int x){q2.push(x);--sz;}

 int size()    {return sz;}

 void cl()

 {

     while(!q1.empty()&&!q2.empty()&&q1.top()==q2.top())    q1.pop(),q2.pop();

 }

 void pop()

 {

     cl();q1.pop();--sz;

 }

 int top()

 {

     cl();return q1.top();

 }

 bool empty()    {return sz==;}

 };

 xxx s[],s2[],s3;

 //s[i]:i点管辖的连通块各个点到i点上层重心的距离

 //s2[i]:i点的各个下层重心的s的最大值,**再加上一个0（i点到自身距离）

 //s3:各个s2的前2大值之和

 int getdis(int x,int y)

 {

     int l=pos[x],r=pos[y];if(l>r)    swap(l,r);

     int k=log2x[r-l+],t=dpx[pos[st[l][k]]]>dpx[pos[st[r-lft[k]+][k]]]?st[r-lft[k]+][k]:st[l][k];

     return dpx2[pos[x]]+dpx2[pos[y]]-*dpx2[pos[t]];

 }

 void getroot(int u,int fa)

 {

     sz[u]=;fx[u]=;

     for(int k=f1[u];k;k=e[k].nxt)

         if(!vis[e[k].to]&&e[k].to!=fa)

         {

             getroot(e[k].to,u);

             sz[u]+=sz[e[k].to];

             fx[u]=max(fx[u],sz[e[k].to]);

         }

     fx[u]=max(fx[u],sum-sz[u]);

     if(fx[u]<fx[root])    root=u;

 }

 void getsz(int u,int fa)

 {

     sz[u]=;

     for(int k=f1[u];k;k=e[k].nxt)

         if(!vis[e[k].to]&&e[k].to!=fa)

         {

             getsz(e[k].to,u);

             sz[u]+=sz[e[k].to];

         }

 }

 void getdeep(int u,int fa)

 {

     s[root].insert(getdis(u,ff[root]));

     for(int k=f1[u];k;k=e[k].nxt)

         if(!vis[e[k].to]&&e[k].to!=fa)

             getdeep(e[k].to,u);

 }

 char tmp[];

 int getmax2(int p)

 {

     if(s2[p].size()<)    return -0x3f3f3f3f;

     int t1=s2[p].top();s2[p].pop();int t2=s2[p].top();s2[p].insert(t1);

     return t1+t2;

 }

 void solve(int u)

 {

     vis[u]=;

     s2[u].insert();

     for(int k=f1[u];k;k=e[k].nxt)

         if(!vis[e[k].to])

         {

             getsz(e[k].to,);sum=sz[e[k].to];

             root=;getroot(e[k].to,);

             ff[root]=u;getdeep(root,);

             if(!s[root].empty())    s2[u].insert(s[root].top());

             solve(root);

         }

     s3.insert(getmax2(u));

 }

 void dfs1(int u,int fa,int d,int d2)

 {

     eu[++eu[]]=u;pos[u]=eu[];dpx[eu[]]=d;dpx2[eu[]]=d2;

     for(int k=f1[u];k;k=e[k].nxt)

         if(e[k].to!=fa)

         {

             dfs1(e[k].to,u,d+,d2+e[k].d);

             eu[++eu[]]=u;

             dpx[eu[]]=d;

             dpx2[eu[]]=d2;

         }

 }

 //void debugxxxx(multiset<int>& s)

 //{

 //    for(auto i : s)    printf("%d ",i);

 //    puts("test");

 //}

 void change(int u)

 {

     int now;

     s3.erase(getmax2(u));

     if(!fl[u])    s2[u].erase();

     for(now=u;ff[now];now=ff[now])

     {

         s3.erase(getmax2(ff[now]));

         if(!s[now].empty())    s2[ff[now]].erase(s[now].top());

         if(!fl[u])    s[now].erase(getdis(u,ff[now]));

     }

     fl[u]^=;

     if(!fl[u])    s2[u].insert();

     s3.insert(getmax2(u));

     for(now=u;ff[now];now=ff[now])

     {

         if(!fl[u])    s[now].insert(getdis(u,ff[now]));

         if(!s[now].empty())    s2[ff[now]].insert(s[now].top());

         s3.insert(getmax2(ff[now]));

     }

 }

 int num;

 int main()

 {

     lft[]=;

     fx[]=0x3f3f3f3f;

     int i,j,a,b,la=,q,t,c;

     for(i=;i<=;i++)    lft[i]=(lft[i-]<<);

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

     {

         if(i>=lft[la+])    ++la;

         log2x[i]=la;

     }

     scanf("%d",&n);

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

     {

         scanf("%d%d%d",&a,&b,&c);

         e[++ne].to=b;e[ne].nxt=f1[a];e[ne].d=c;f1[a]=ne;

         e[++ne].to=a;e[ne].nxt=f1[b];e[ne].d=c;f1[b]=ne;

     }

     dfs1(,,,);

     for(i=;i<=eu[];i++)    st[i][]=eu[i];

     for(j=;(<<j)<=eu[];j++)

         for(i=;i+lft[j]-<=eu[];i++)

             if(dpx[pos[st[i][j-]]]>dpx[pos[st[i+lft[j-]][j-]]])

                 st[i][j]=st[i+lft[j-]][j-];

             else

                 st[i][j]=st[i][j-];

     sum=n;getroot(,);

     solve(root);

     scanf("%d",&q);

     num=n;

     while(q--)

     {

         scanf("%s",tmp);

         if(tmp[]=='A')

         {

             if(num==)    printf("They have disappeared.\n");

             else if(num==)    printf("0\n");

             else    printf("%d\n",max(s3.top(),));

         }

         else if(tmp[]=='C')

         {

             scanf("%d",&t);

             if(fl[t])    num++;else    num--;

             change(t);

         }

     }

     return ;

 }

upd20181231:

用网上的链分治做法重写了，果然常数小很多，可以A了，然而代码量似乎更大

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 #include<queue>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 struct E

 {

     int to,nxt,d;

 }e[];

 int f1[],ne;

 const int inf1=0x3f3f3f3f;

 struct Set

 {

     priority_queue<int> s,t;int sz;

     void push(int x){s.push(x);++sz;}

     void erase(int x){t.push(x);--sz;}

     int top()

     {

         while(s.size()&&t.size()&&s.top()==t.top())

             s.pop(),t.pop();

         return sz?s.top():-inf1;

     }

     int sum2()//最大2个之和

     {

         if(sz<)    return ;

         int a1=top();erase(a1);

         int a2=top();push(a1);

         return a1+a2;

     }

 }q[],&q0=q[];

 int d[];

 struct I

 {

     int da,db,d;

     //a表示向下最长轻链,d表示到1距离;max{a+d},max{a-d},max{ar+al+dr-dl}

 };

 void merge(I &c,const I &a,const I &b)

 {

     c.da=max(a.da,b.da);

     c.db=max(a.db,b.db);

     c.d=max(max(a.d,b.d),b.da+a.db);

 }

 namespace S

 {

     struct D

     {

         int lc,rc;I d;

     }g[];

     int mem;

 #define LC g[u].lc

 #define RC g[u].rc

     void upd(int u){merge(g[u].d,g[LC].d,g[RC].d);}

     I x;int L;

     /*

     void init()

     {

         g[0].d.da=g[0].d.db=g[0].d.d=-inf1;

     }

     inline int gnode()

     {

         int t=++mem;

         g[t].d.da=g[t].d.db=g[t].d.d=g[t].d.a=-inf1;

         return t;

     }

     */

     void _setx(int l,int r,int &u)

     {

         if(!u)    u=++mem;

         if(l==r)

         {

             g[u].d=x;

             return;

         }

         int mid=(l+r)>>;

         if(L<=mid)    _setx(l,mid,LC);

         else    _setx(mid+,r,RC);

         upd(u);

     }

     I getx(int L,int R,int l,int r,int u)

     {

         if(L<=l&&r<=R)    return g[u].d;

         int mid=(l+r)>>;

         if(L<=mid&&mid<R)

         {

             I t;merge(t,getx(L,R,l,mid,LC),getx(L,R,mid+,r,RC));

             return t;

         }

         else if(L<=mid)

             return getx(L,R,l,mid,LC);

         else if(mid<R)

             return getx(L,R,mid+,r,RC);

     }

 }

 int dep[],sz[];

 int d2[],hson[];

 int ff[];

 void dfs1(int u,int fa)

 {

     sz[u]=;

     int v;

     for(int k=f1[u];k;k=e[k].nxt)

         if(e[k].to!=fa)

         {

             v=e[k].to;

             ff[v]=u;

             dep[v]=dep[u]+;

             d[v]=d[u]+e[k].d;

             dfs1(v,u);

             sz[u]+=sz[v];

             if(sz[v]>sz[hson[u]])    hson[u]=v;

         }

 }

 int b[],pl[],tp[],dwn[],len[];

 int rt[],oknum;

 bool ok[];

 int n,m;

 void dfs2(int u,int fa)

 {

     ok[u]=;q[u].push();

     b[++b[]]=u;pl[u]=b[];

     tp[u]=(u==hson[fa])?tp[fa]:u;

     if(hson[u])    dfs2(hson[u],u);

     dwn[u]=hson[u]?dwn[hson[u]]:u;

     len[u]=dep[dwn[u]]-dep[tp[u]]+;

     int v,k;

     for(k=f1[u];k;k=e[k].nxt)

         if(e[k].to!=fa&&e[k].to!=hson[u])

         {

             v=e[k].to;

             dfs2(v,u);

             q[u].push(d2[v]-d[u]);

         }

     {

         int t=q[u].top();

         using namespace S;

         x.da=t+d[u];x.db=t-d[u];x.d=q[u].sum2();

         L=dep[u]-dep[tp[u]]+;_setx(,len[u],rt[tp[u]]);

     }

     if(u==tp[u])

     {

         const I &t=S::g[rt[u]].d;

         d2[u]=t.da;

         q0.push(t.d);

     }

 }

 int main()

 {

     int i,x,y,z,t,u,v;

     char tmp[];

     //S::init();

     scanf("%d",&n);

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

     {

         scanf("%d%d%d",&x,&y,&z);

         e[++ne].to=y;e[ne].nxt=f1[x];f1[x]=ne;e[ne].d=z;

         e[++ne].to=x;e[ne].nxt=f1[y];f1[y]=ne;e[ne].d=z;

     }

     dfs1(,);

     oknum=n;

     dfs2(,);

     //printf("%d\n",q0.top());

     scanf("%d",&m);

     while(m--)

     {

         scanf("%s",tmp);

         if(tmp[]=='C')

         {

             scanf("%d",&u);

             if(ok[u])

             {

                 --oknum;

                 q[u].erase();

             }

             else

             {

                 ++oknum;

                 q[u].push();

             }

             ok[u]^=;

             while(u)

             {

                 q0.erase(S::g[rt[tp[u]]].d.d);

                 {

                     t=q[u].top();

                     using namespace S;I &x=S::x;

                     x.da=t+d[u];x.db=t-d[u];x.d=q[u].sum2();

                     L=dep[u]-dep[tp[u]]+;_setx(,len[u],rt[tp[u]]);

                 }

                 u=tp[u];v=ff[u];

                 const I &t=S::g[rt[u]].d;

                 if(v)    q[v].erase(d2[u]-d[v]);

                 d2[u]=t.da;

                 if(v)    q[v].push(d2[u]-d[v]);

                 q0.push(t.d);

                 u=v;

             }

         }

         else

         {

             if(!oknum)

             {

                 puts("They have disappeared.");

                 continue;

             }

             printf("%d\n",q0.top());

         }

     }

     return ;

 }

巴特西

Query on a tree IV SPOJ - QTREE4

最新文章

热门文章