bzoj 3720 Gty的妹子树 树分块?瞎搞
Gty的妹子树
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2149 Solved: 781
[Submit][Status][Discuss]
Description
我曾在弦歌之中听过你,
檀板声碎,半出折子戏。
舞榭歌台被风吹去,
岁月深处尚有余音一缕……
Gty神(xian)犇(chong)从来不缺妹子……
他来到了一棵妹子树下,发现每个妹子有一个美丽度……
由于Gty很哲♂学,他只对美丽度大于某个值的妹子感兴趣。
他想知道某个子树中美丽度大于k的妹子个数。
某个妹子的美丽度可能发生变化……
树上可能会出现一只新的妹子……
维护一棵初始有n个节点的有根树(根节点为1),树上节点编号为1-n,每个点有一个权值wi。
支持以下操作:
0 u x 询问以u为根的子树中,严格大于x的值的个数。(u^=lastans,x^=lastans)
1 u x 把u节点的权值改成x。(u^=lastans,x^=lastans)
2 u x 添加一个编号为"当前树中节点数+1"的节点,其父节点为u,其权值为x。(u^=lastans,x^=lastans)
最开始时lastans=0。
Input
输入第一行包括一个正整数n(1<=n<=30000),代表树上的初始节点数。
接下来n-1行,每行2个整数u,v,为树上的一条无向边。
任何时刻,树上的任何权值大于等于0,且两两不同。
接下来1行,包括n个整数wi,表示初始时每个节点的权值。
接下来1行,包括1个整数m(1<=m<=30000),表示操作总数。
接下来m行,每行包括三个整数 op,u,v:
op,u,v的含义见题目描述。
保证题目涉及的所有数在int内。
Output
对每个op=0,输出一行,包括一个整数,意义见题目描述。
Sample Input
1 2
10 20
1
0 1 5
Sample Output
HINT
2017.9.28新加数据一组by GXZlegend,未重测
Source
传说中的树分块,但是会被暴力卡,我貌似没找出什么方法,
和根一起一起到达根号n就就分块,这个没什么用,会被菊花图卡掉的。
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath> #define N 60007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,m,block,ans,tot;
int a[N],fa[N],bl[N];
int cnt,hed[N],nxt[N<<],rea[N<<];
int Cnt,Hed[N],Nxt[N<<],Rea[N<<]; struct Node
{
int a[],siz;
void insert(int x){a[++siz]=x;}
void change(int x,int y)
{
int t=upper_bound(a+,a+siz+,x)-a;t--;
a[t]=y;
sort(a+,a+siz+);
}
int query(int x)
{
int t=upper_bound(a+,a+siz+,x)-a;
return siz-t+;
}
}blo[N];
inline void add(int u,int v)
{
nxt[++cnt]=hed[u];
hed[u]=cnt;
rea[cnt]=v;
}
inline void add_two_way(int u,int v)
{
add(u,v);
add(v,u);
}
inline void ins(int u,int v)
{
Nxt[++Cnt]=Hed[u];
Hed[u]=Cnt;
Rea[Cnt]=v;
}
void dfs(int u)
{
if (blo[bl[fa[u]]].siz==block)
blo[bl[u]=++tot].insert(a[u]),ins(bl[fa[u]],tot);
else blo[bl[u]=bl[fa[u]]].insert(a[u]);
for (int i=hed[u];i!=-;i=nxt[i])
{
int v=rea[i];
if (v==fa[u]) continue;
fa[v]=u,dfs(v);
}
}
void block_dfs(int u,int z)
{
ans+=blo[u].query(z);
for (int i=Hed[u];i!=-;i=Nxt[i])
{
int v=Rea[i];
block_dfs(v,z);
}
}
void solve(int u,int z)
{
if (a[u]>z) ans++;
for (int i=hed[u];i!=-;i=nxt[i])
{
int v=rea[i];
if (v==fa[u]) continue;
if (bl[v]==bl[u]) solve(v,z);
else block_dfs(bl[v],z);
}
}
int main()
{
memset(hed,-,sizeof(hed));
memset(Hed,-,sizeof(Hed));
n=read(),block=sqrt(n);
for (int i=;i<n;i++)
add_two_way(read(),read());
for (int i=;i<=n;i++) a[i]=read();
dfs();
for (int i=;i<=tot;i++)
sort(blo[i].a+,blo[i].a+blo[i].siz+); m=read();
for (int i=;i<=m;i++)
{
int opt=read(),x=read(),y=read();
x^=ans,y^=ans;
if (opt==)
{
ans=;
solve(x,y);
printf("%d\n",ans);
}
else if (opt==)
{
blo[bl[x]].change(a[x],y);
a[x]=y;
}
else
{
a[++n]=y,add_two_way(x,n),fa[n]=x;
if (blo[bl[x]].siz==block)
blo[bl[n]=++tot].insert(y),ins(bl[x],tot);
else
{
blo[bl[n]=bl[x]].insert(y);
sort(blo[bl[n]].a+,blo[bl[n]].a+blo[bl[n]].siz+);
}
}
}
}
最新文章
- js数字时钟
- MATLAB调用C程序、调试和LDPC译码
- LINUX下搭建VPN
- Hbase原理、基本概念、基本架构
- MySQL导入sql脚本 导出数据库
- mysql 自连接
- 在Android中让Preference的宽度占满整个屏幕的宽度
- HttpClient_HttpClient 4.3.6 HTTP状态管理
- ECshop中TemplateBeginEditable 和后台编辑讲解
- Sqli-labs less 44
- Git之 基本常用命令
- Toad for Oracle 使用文档
- android 74 下载文本
- Dictionary的遍历和修改
- Web缓存相关知识整理
- 注册WinEdt 7
- 简陋的swift carthage copy-frameworks 辅助脚本
- http请求 405错误 方法不被允许 (Method not allowed)
- angular4脚手架搭建
- Nginx 之六: Nginx服务器的正向及反向代理功能
热门文章
- Python3爬虫(十一) 爬虫与反爬虫
- HyperLedger Fabric 1.4 超级账本项目(5.4)
- Java 中编码与摘要算法
- 详解jQuery中 .bind() vs .live() vs .delegate() vs .on() 的区别
- 【Luogu P1935】[国家集训队]圈地计划
- ACE_Select_Reactor_T 介绍 (2)
- Spring.Net在ASP.NET Mvc里使用的一个小例子
- Qt 编译时遇到 error: [debug/qrc_music.cpp] Error 1
- fildder抓包工具详解
- 《python核心编程第二版》第7章习题