HDU5589:Tree(莫队+01字典树)-白红宇

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

阅读量：402 次

发布时间：2019-03-06

本文共 3104 字，大约阅读时间需要 10 分钟。

题意

略

分析

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

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

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

参考

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

trick

代码

wa#include 
   
    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
    
     
       >mp[maxn];struct node{    int l,r,id,len;    bool operator<(const node &p)const    {        return len==p.len?r

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

=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<

=0;--i) { int idx=(((x>>i)&1)^1); if(num[ch[cur][idx]]) cur=ch[cur][idx],ret|=(1<

a[i].r) {update(f[R],-1);tmp-=query(f[R]);R--;} // printf("tmp2=%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

{v,w}); mp[v].push_back(pair

{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
   
    using namespace std;const int maxn=50010;typedef pair
    
      PI;vector
     
      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

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

=0;i--){ if((1<

Q[i].r){ trie.insert(a[R],-1); tmp-=trie.query(a[R]); R--; } //printf("tmp2=%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

转载地址：http://okokz.baihongyu.com/