TLE求助

回复帖子

@starusc 2019-10-22 08:38 回复

改了好久还是TLE,帮忙看看嘛 (๑╹っ╹๑) (๑╹っ╹๑) (๑╹っ╹๑)

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f==1?x:-x;
}
#define re register
const int N=2e5+4;
struct ques{
    int l,ll,r,id,lca;
}q[N];
int n,m,a[N],b[N],c[N],st[N],ed[N],fa[N],siz[N],dep[N],son[N],top[N],idx[N<<1],blo,tot=0;
vector<int>e[N];
inline bool comp(const ques &x,const ques &y){
    return x.ll==y.ll?(x.ll%2==1?x.r<y.r:x.r>y.r):x.l<y.l;
}
inline void dfs1(int x){
    st[x]=++tot;idx[tot]=a[x];
    for(re int i=0,v;i<e[x].size();i++){
        v=e[x][i];
        if(st[v])continue;
        fa[v]=x;
        dep[v]=dep[x]+1;
        dfs1(v);
        siz[x]+=siz[v];
        if(siz[v]>siz[son[x]])son[x]=v;
    }
    ed[x]=++tot;idx[tot]=a[x];
}
inline void dfs2(int x,int tp){
    top[x]=tp;
    if(son[x])dfs2(son[x],tp);
    for(re int i=0,v;i<e[x].size();i++){
        v=e[x][i];
        if(v==fa[x]||v==son[x])continue;
        dfs2(v,v);
    }
}
inline int LCA(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v; 
}
int main(){
    n=read();m=read();
    for(re int i=1;i<=n;i++)
        b[i]=a[i]=read();
    sort(b+1,b+n+1);
    int ct=unique(b+1,b+n+1)-b-1;
    for(re int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+ct+1,a[i])-b;
    for(re int i=1,u,v;i<n;i++){
        u=read();v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dep[1]=1;dfs1(1);
    dfs2(1,1);
    blo=n*2/sqrt(m*2/3);//!!
    for(re int i=1,u,v;i<=m;i++){
        u=read();v=read();
        if(st[u]>st[v])swap(u,v);
        q[i].id=i;
        q[i].lca=LCA(u,v);
        if(q[i].lca==u){
            q[i].l=st[u];q[i].r=st[v];q[i].lca=0;//
        }
        else{
            q[i].l=ed[u];q[i].r=st[v];
        }
        q[i].ll=q[i].l/blo;//记录下来 
    }
    sort(q+1,q+m+1,comp);
    for(re int i=1,l=1,r=0,ans=0,x;i<=m;i++){
        while(r<q[i].r){
            c[idx[++r]]++;
            if(c[idx[r]]==1)ans++;
        }
        while(r>q[i].r){
            c[idx[r--]]--;
            if(!c[idx[r+1]])ans--; 
        }
        while(l<q[i].l){
            c[idx[l++]]--;
            if(!c[idx[l-1]])ans--;
        }
        while(l>q[i].l){
            c[idx[--l]]++;
            if(c[idx[l]]==1)ans++;
        }
        x=ans;
        if(q[i].lca&&!c[a[q[i].lca]])x++;
        printf("%d\n",x);
    }
    return (0-0);
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。