HDU5589:Tree(莫队+01字典树)

传送门

题意

略

分析

f[u]表示u到根的边的异或

树上两点之间的异或值为f[u]^f[v],

然后将查询用莫队算法分块,每个点插入到字典树中,利用字典树维护两点异或值大于等于M复杂度O(N^(3/2)*logM)

参考 _zidaoziyan

表示又陷入查错的大坑，思路是对的，调不出来，留坑

trick

代码

wa

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define mem(a,b) memset(a,b,sizeof(a))

#define F(i,a,b) for(int i=a;i<=b;++i)

const int maxn = 50050;//集合中的数字个数

int ch[20*maxn][2];//节点的边信息

int num[20*maxn];//记录节点的使用次数，删除时要用

//int val[32*maxn];//节点存储的值

int cnt;//树中节点的个数

bitset<20>choose;

int ask;

int f[maxn],vis[maxn];

ll ans[maxn];

vector<pair<int,int> >mp[maxn];

struct node

{

    int l,r,id,len;

    bool operator<(const node &p)const

    {

        return len==p.len?r<p.r:len<p.len;

    }

}a[maxn];

void bfs(int u)

{

    queue<int>q;

    q.push(1);

    mem(vis,0);

    vis[1]=1;f[1]=0;

    while(!q.empty())

    {

        int tmp=q.front();q.pop();

        for(int i=0;i<mp[tmp].size();++i)

        {

            int v=mp[tmp][i].first;

            if(vis[v]) continue;

            f[v]=f[tmp]^mp[tmp][i].second;

            q.push(v);vis[v]=1;

        }

    }

}

inline void init()

{

    cnt=1;mem(ch[0],0);//清空树

}

/*

void insert(int x)//在字典树中插入x，和一般字典树操作相同，将x化成二进制插入到字典树

{

    int cur=0;

    for(int i=29;i>=0;--i)

    {

        int idx=((x>>i)&1);

        if(!ch[cur][idx])

        {

            mem(ch[cnt],0);

            num[cnt]=0;

            ch[cur][idx]=cnt++;

            //val[cnt++]=0;

        }

        //printf("ch[%d][%d]=%d\n",cur,idx,ch[cur][idx]);

        cur=ch[cur][idx];

        num[cur]++;

    }

    //val[cur]=x;//最后节点插入val

}

*/

void update(int x,int c)

{

    int cur=0;

    for(int i=17;i>=0;--i)

    {

        int idx=((x>>i)&1);

        if(!ch[cur][idx])

        {

            mem(ch[cnt],0);

            num[cnt]=0;

            ch[cur][idx]=cnt++;

        }

        cur=ch[cur][idx];

        num[cur]+=c;

    }

}

/*

ll query(ll x)//在字典树（数集)中查找和x异或是最大值的元素y，返回y

{

    int cur=0;

    for(int i=32;i>=0;--i)

    {

        int idx=(x>>i)&1;

        if(ch[cur][idx^1]) cur=ch[cur][idx^1];else cur=ch[cur][idx];

    }

    return val[cur];

}

*/

int query(int x)//返回移动一位增加/减少的匹配数

//带删除操作的查询

{

    int cur=0,idx,ans=0;

    for(int i=17;i>=0;--i)

    {

        if((i<<i)&x) idx=1;else idx=0;

        if(!choose[i])

        {

            if(ch[cur][idx^1]) ans+=num[ch[cur][idx^1]];

            if((!ch[cur][idx])||(!num[ch[cur][idx]])) return ans;

            cur=ch[cur][idx];

        }

        else

        {

            if((!ch[cur][idx^1])||(num[ch[cur][idx^1]]==0)) return ans;

            cur=ch[cur][idx^1];

        }

        //printf("%d\n",ret);

        //if(ch[cur][idx^1]&&num[ch[cur][idx^1]]) cur=ch[cur][idx^1];else cur=ch[cur][idx];

    }

    //printf("val(%d)=%d\n",cur,val[cur]);

    return ans;

}

/*

int get_ans(int x)

{

    int cur=0,ret=0;

    for(int i=29;i>=0;--i)

    {

        int idx=(((x>>i)&1)^1);

        if(num[ch[cur][idx]]) cur=ch[cur][idx],ret|=(1<<i);

        else cur=ch[cur][idx^1];

    }

    return ret;

}

*/

void solve()

{

    int L=1,R=0;

    init();

    ll tmp=0;

    F(i,1,ask)

    {

        while(R<a[i].r) {R++;tmp+=query(f[R]);update(f[R],1);}

         //printf("tmp1=%lld\n",tmp);

        while(R>a[i].r) {update(f[R],-1);tmp-=query(f[R]);R--;}

              // printf("tmp2=%lld\n",tmp);

        while(L<a[i].l) {update(f[L],-1);tmp-=query(f[L]);L++;}

                 // printf("tmp3=%lld\n",tmp);

         while(L>a[i].l) {L--;tmp+=query(f[L]);update(f[L],1);}

         //printf("tmp4=%lld\n",tmp);

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

        ans[a[i].id]=tmp;

    }

}

int main()

{

    int n,m;

    while(scanf("%d %d %d",&n,&m,&ask)!=EOF)

    {

        int u,v,w,sqr=sqrt(n);choose=m;

        F(i,1,n) mp[i].clear();

        F(i,1,n-1)

        {

            scanf("%d %d %d",&u,&v,&w);

            mp[u].push_back(pair<int,int>{v,w});

            mp[v].push_back(pair<int,int>{u,w});

        }

        bfs(1);

        //F(i,1,n) printf("%d%c",f[i],i==n?'\n':' ');

        F(i,1,ask)

        {

            scanf("%d%d",&a[i].l,&a[i].r);

            a[i].id=i;a[i].len=a[i].l/sqr;

        }

        sort(a+1,a+1+ask);

        //F(i,1,ask) printf("%d %d %d\n",a[i].l,a[i].r,a[i].id );

        solve();

        F(i,1,ask) printf("%lld\n",ans[i]);

    }

    return 0;

}

//ac

#include<bits/stdc++.h>

using namespace std;

const int maxn=50010;

typedef pair<int,int> PI;

vector<PI>G[maxn];

int a[maxn],unit,q;

bitset <20> cnt;

int vis[maxn];

long long ans[maxn];

struct node{

    int l,r,id;

}Q[maxn];

bool cmp(node u,node v){

    if(u.l/unit!=v.l/unit)

        return u.l/unit<v.l/unit;

    return u.r<v.r;

}

void bfs(int u){

    queue<int>Q;

    Q.push(1);

    memset(vis,0,sizeof(vis));

    vis[1]=1;

    while(!Q.empty()){

        int u=Q.front();

        Q.pop();

        for(int i=0;i<G[u].size();i++){

            int v=G[u][i].first;

            if(vis[v])

                continue;

            a[v]=a[u]^G[u][i].second;

            Q.push(v);

            vis[v]=1;

        }

    }

}

struct Trie{

    int val[maxn*20],next[maxn*20][2];

    int sz;

    void init(){

        sz=1;

        memset(next[0],0,sizeof(next[0]));

    }

    void insert(int num,int x){

        int u=0,c;

        for(int i=17;i>=0;i--){

            if((1<<i)&num)

                c=1;

            else

                c=0;

            if(!next[u][c])

                memset(next[sz],0,sizeof(next[sz])),val[sz]=0,next[u][c]=sz++;

            u=next[u][c];

            val[u]+=x;

        }

    }

    int query(int num){

        int ans=0,c,u=0;

        for(int i=17;i>=0;i--){

            if((1<<i)&num)

                c=1;

            else

                c=0;

            if(cnt[i]==0){

                if(next[u][c^1])

                    ans+=val[next[u][c^1]];

                if(!next[u][c]||val[next[u][c]]==0)

                    return ans;

                u=next[u][c];

            }

            else{

                if(!next[u][c^1]||val[next[u][c^1]]==0)

                    return ans;

                u=next[u][c^1];

            }

                   // printf("%d\n",ans);

        }

        return ans;

    }

};

Trie trie;

void solve(){

    int L=1,R=0;

    trie.init();

    long long tmp=0;

    for(int i=1;i<=q;i++){

        while(R<Q[i].r){

            R++;

            tmp+=trie.query(a[R]);

            trie.insert(a[R],1);

        }

                 //printf("tmp1=%lld\n",tmp);

        while(R>Q[i].r){

            trie.insert(a[R],-1);

            tmp-=trie.query(a[R]);

            R--;

        }

                 //printf("tmp2=%lld\n",tmp);

while(L<Q[i].l){

            trie.insert(a[L],-1);

            tmp-=trie.query(a[L]);

            L++;

        }

       // printf("tmp3=%lld\n",tmp );

        while(L>Q[i].l){

            L--;

            tmp+=trie.query(a[L]);

            trie.insert(a[L],1);

        }

       // printf("tmp4=%lld\n", tmp);

        ans[Q[i].id]=tmp;

    }

}

int main(){

    int n,m;

    while(scanf("%d%d%d",&n,&m,&q)!=EOF){

        int u,v,w;

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

            G[i].clear();

        for(int i=1;i<n;i++){

            scanf("%d%d%d",&u,&v,&w);

            G[u].push_back(PI{v,w});

            G[v].push_back(PI{u,w});

        }

        cnt=m;

        a[1]=0,unit=sqrt(n);

        bfs(1);

       // for(int i=1;i<=n;++i) printf("%d%c",a[i],i==n?'\n':' ');

        for(int i=1;i<=q;i++){

            scanf("%d%d",&Q[i].l,&Q[i].r);

            Q[i].id=i;

        }

        sort(Q+1,Q+q+1,cmp);

       // for(int i=1;i<=q;++i) printf("%d %d %d %d\n",Q[i].l,Q[i].r,Q[i].id);

        solve();

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

            printf("%lld\n",ans[i]);

    }

    return 0;

}

巴特西

HDU5589:Tree(莫队+01字典树)

传送门

题意

分析

trick

代码

最新文章

热门文章