我曾在弦歌之中听过你，
檀板声碎，半出折子戏。
舞榭歌台被风吹去，
岁月深处尚有余音一缕……
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。
输入第一行包括一个正整数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内。
对每个op=0，输出一行，包括一个整数，意义见题目描述。
2017.9.28新加数据一组by GXZlegend,未重测
思路： 吐槽一下题目的数据范围有误，n好像要比30000大。
这题可以按照size的大小分块，如果父亲所在的块的点的数量小于sz，那么就把当前节点加到父亲所在的块里面。
这样分块的方法可以保证块的大小和直径，但是不能保证块的数量。（感觉要被卡，逃 。。。)
块里面用普通的一维数组记录每个不同的权值，插入和修改的时候用暴力的插入排序维护。
时间复杂度$O(n*sqrt{n}*log n)$，时间复杂度比较高，但是可以卡过。
本题最好的方法是用替罪羊树套treap来写。
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define rep(i,a,b) for(int i=a;i<=b;i++)
4 #define Rep(i,a,b) for(int i=a;i>=b;i--)
5 #define ms(i,a) memset(a,i,sizeof(a))
6 int const N = 100000 + 3;
7 template<class T>void read(T &x) {
8 x = 0;
9 char c = 0;
10 while(!isdigit((c))) c = getchar();
11 while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
12 }
13 struct edge {
14 int to, nt;
15 } e[N << 2];
16 struct block {
17 int a[300], num;
18 void ins(int x) {
19 num++;
20 int j = num - 1;
21 while(j && a[j] > x) a[j + 1] = a[j], j--;
22 a[j + 1] = x;
23 }
24 void modify(int x, int y) {
25 int t = lower_bound(a + 1, a + num + 1, x) - a;
26 rep(i, t + 1, num) a[i - 1] = a[i];
27 num--;
28 ins(y);
29 }
30 int query(int x) {
31 return num - (upper_bound(a + 1, a + num + 1, x) - a) + 1;
32 }
33 } b[10000];
34 int h[N], cnt, H[N], bl[N], n, m, a[N], sz, sum, ans,f[N];
35 void add(int a, int b) {
36 e[++cnt].to = b;
37 e[cnt].nt = h[a];
38 h[a] = cnt;
39 }
40 void Add(int a, int b) {
41 e[++cnt].to = b;
42 e[cnt].nt = H[a];
43 H[a] = cnt;
44 }
45 void dfs(int x) {
46 if(b[bl[f[x]]].num >= sz) {
47 bl[x] = ++sum;
48 b[sum].ins(a[x]);
49 Add(bl[f[x]], sum);
50 } else {
51 bl[x] = sum;
52 b[sum].ins(a[x]);
53 }
54 for(int i = h[x]; i; i = e[i].nt) {
55 int v = e[i].to;
56 if(v == f[x]) continue;
57 f[v]=x;
58 dfs(v);
59 }
60 }
61 void getblock(int x, int y) {
62 ans += b[x].query(y);
63 for(int i = H[x]; i; i = e[i].nt) {
64 int v = e[i].to;
65 getblock(v, y);
66 }
67 }
68 void getans(int x, int y) {
69 if(a[x] > y) ans++;
70 for(int i = h[x]; i; i = e[i].nt) {
71 int v = e[i].to;
72 if(v == f[x]) continue;
73 if(bl[v] == bl[x]) getans(v, y);
74 else getblock(bl[v], y);
75 }
76 }
77 int main() {
78 read(n);
79 sz = sqrt(n);
80 rep(i, 1, n - 1) {
81 int x, y;
82 read(x);
83 read(y);
84 add(x, y);
85 add(y, x);
86 }
87 rep(i, 1, n) read(a[i]);
88 dfs(1);
89 read(m);
90 while(m--) {
91 int k, x, y;
92 read(k);
93 read(x);
94 read(y);
95 x ^= ans;
96 y ^= ans;
97 if(k == 0) {
98 ans = 0;
99 getans(x,y);
100 printf("%dn", ans);
101 }
102 if(k == 1) {
103 b[bl[x]].modify(a[x], y);
104 a[x] = y;
105 }
106 if(k == 2) {
107 a[++n] = y;
108 f[n]=x;
109 add(x, n);
110 if(b[bl[x]].num >= sz) {
111 bl[n] = ++sum;
112 b[sum].ins(y);
113 Add(bl[x], sum);
114 } else {
115 bl[n] = bl[x];
116 b[bl[n]].ins(y);
117 }
118 }
119 }
120 return 0;
121 } View Code
转载于:.html
本文发布于:2024-02-02 05:21:02，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170682246341623.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
