题意

ξ 得到了一棵圣诞树，他需要在上面挂满礼物。

ξ 会事先进行m个操作，每次在一条链（u[i],v[i]）上的每个点上挂上a[i]个种类为b[i]的礼物。

一个点的k-美观度这样计算：把这个点上的所有种类的礼物按照个数从小到大排序，如果个数一样就按照种类从小到大排。

它的k-美观度就是排好序后前k种礼物种类的xor值（如果礼物种类不足k种，就把这个点上所有礼物的种类xor起来）。

接下来给Q个询问，给定w[i],k[i]，求点w[i]的k[i]-美观度。

前言

这题真是做的我**了。。

想了一个早上，然后写了两个错误的想法。。

然后一个上午就成功过去了。。

什么都没做

下午又调了一个下午。。

一天就没了QAQ

题解

容易想到，这种东西可以树上差分

两个端点处挂上a[i]个b[i]，在端点lca及lca的父亲处挂上-a[i]个b[i]，询问子树的k-美观度

子树可以想到dfs序

因为dfs序的特殊性，所以所有区间都是包含或相离的

然后就可以分治了啊。。

考虑扩过中界线的

那么肯定是可以单调的啊

加入新的点，维护信息就用一个splay就可以了

要注意的是，在分治结构中，要注意所有全局变量的初始化，我就因为有一个没搞好调了很久QAQ

CODE:

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef pair
          
            PI;const int N=100005;int n,m;struct qq{ int x,y,last;}e[N*2];int num,last[N];void init (int x,int y){ num++; e[num].x=x;e[num].y=y; e[num].last=last[x]; last[x]=num;}int fa[N][21];int dep[N];int L[N],R[N],cnt;void dfs (int x){ L[x]=++cnt; for (int u=1;u<=20;u++) fa[x][u]=fa[fa[x][u-1]][u-1]; for (int u=last[x];u!=-1;u=e[u].last) { int y=e[u].y; if (y==fa[x][0]) continue; dep[y]=dep[x]+1;fa[y][0]=x;dfs(y); } R[x]=cnt;}int get (int x,int y){ if (dep[x]>dep[y]) swap(x,y); for (int u=20;u>=0;u--) if (dep[fa[y][u]]>=dep[x]) y=fa[y][u]; if (x==y) return x;// printf("lalal:%d %d\n",x,y); for (int u=20;u>=0;u--) if (fa[x][u]!=fa[y][u]) { x=fa[x][u];y=fa[y][u];} return fa[x][0];}vector
           
             s[N];//各种修改操作 int Q;int ans[N];struct qt{ int l,r,k,id;}q[N];struct qr{ int f,son[2],c;//父亲 儿子 有多少个点 int a,b;//次数和值 int ans;//子树的答案 }tr[N*3];bool operator < (const qr &x,const qr &y){ return x.a==y.a?x.b

o;//我们用了哪些种类void update (int x){ int s1=tr[x].son[0],s2=tr[x].son[1]; tr[x].c=tr[s1].c+tr[s2].c+1; tr[x].ans=(tr[s1].ans^tr[s2].ans^tr[x].b); return ;}void add (int a,int b,int fa)//新建一个节点 { num++;vis[b]=num; tr[num].f=fa; tr[num].son[0]=tr[num].son[1]=0; tr[num].a=a;tr[num].b=b; tr[num].c=1;tr[num].ans=b; if (tr[num]

tr[s1].c+1) x=s2,k=k-tr[s1].c-1; else break; } return x;}int find (int k)//寻找前k个 { if (tr[root].c<=k) return tr[root].ans; int x=get(k+1);splay(x,0); return tr[tr[x].son[0]].ans;}queue

A,B,C;bool cmpq(qt x,qt y){ return x.l==y.l?x.r

y.l;}void solve (int l,int r,int L,int R)//处理到的区间要处理的询问 { if (L>R) return ;// printf("TYB:%d %d %d %d\n",l,r,L,R); if (l==r) { Ins(l); // printf("YES\n"); for (int u=L;u<=R;u++) ans[q[u].id]=find(q[u].k); while (!o.empty()) { int xx=o.front();vis[xx]=0;o.pop();} root=num=0; return ; } int mid=(l+r)>>1;// printf("l:%d r:%d mid:%d %d %d\n",l,r,mid,L,R); for (int u=L;u<=R;u++) { if (q[u].r

mid) { // printf("B:%d %d\n",q[u].l,q[u].r); B.push(q[u]); } else C.push(q[u]); } //C这次要处理的，A递归到左边的，B递归到右边的 int g=L,h=L; int now=L; while (!A.empty()) { q[now]=A.front();A.pop();now++;}h=now; while (!B.empty()) { q[now]=B.front();B.pop();now++;}g=now; while (!C.empty()) { q[now]=C.front();C.pop();now++;} solve(l,mid-1,L,h-1);solve(mid+1,r,h,g-1); //那么now到现在的就是我们要处理的了 if (g>R) return ; sort(q+g,q+1+R,cmpq); int ll=mid,rr=mid;/*printf("OZY:l:%d r:%d g:%d R:%d\n",l,r,g,R); for (int u=g;u<=R;u++) printf("%d %d\n",q[u].l,q[u].r); system("pause");*/ for (int u=g;u<=R;u++) { while(ll>=q[u].l) {Ins(ll);ll--;} while (rr

'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar();} return x*f;}inline void write(int x){ if (!x) return (void)puts("0"); if (x < 0) putchar('-'), x = -x; static short s[12], t; while (x) s[++t] = x % 10, x /= 10; while (t) putchar('0' + s[t--]); putchar('\n');}int main(){ memset(vis,0,sizeof(vis)); num=0;memset(last,-1,sizeof(last)); n=read(); for (int u=1;u

上一篇：bzoj 3011: [Usaco2012 Dec]Running Away From the Barn

下一篇：bzoj 4771: 七彩树

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题意

前言

题解

发表评论

最新留言

关于作者

推荐文章