关键词:
先码着,强制在线的树分块或者树套树?关键是我树分块还在入门阶段树套树完全不会啊摔
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<cstdlib> 8 using namespace std; 9 const int maxn=60010; 10 int n,m; 11 int lastans=0; 12 int f[2*maxn]={}; 13 int ad=0; 14 struct nod{ 15 int y; 16 int next; 17 }e[maxn*2]; 18 struct node{ 19 int num; 20 int a[1010]; 21 inline int ask(int k){ 22 int fff=upper_bound(a+1,a+num+1,k)-a-1; 23 return num-fff; 24 } 25 }blo[10010]; 26 struct no{ 27 int next[maxn]; 28 int ai[maxn]; 29 int head[maxn]; 30 int shu; 31 inline void add(int x,int y){ 32 next[++shu]=head[x]; 33 ai[shu]=y; 34 head[x]=shu; 35 } 36 }gre; 37 int bel[maxn]={}; 38 int tail=0; 39 int sz; 40 int a[maxn]={},head[maxn]={}; 41 int tot=0; 42 inline void init(int x,int y){ 43 e[++tail].next=head[x]; 44 e[tail].y=y; 45 head[x]=tail; 46 } 47 void dfs(int x,int fa){ 48 int now=bel[x]; 49 blo[now].a[++blo[now].num]=a[x]; 50 f[x]=fa; 51 for(int i=head[x];i;i=e[i].next){ 52 if(e[i].y==fa){ 53 continue; 54 } 55 if(blo[now].num<sz){ 56 bel[e[i].y]=now; 57 } 58 else{ 59 bel[e[i].y]=++tot; 60 } 61 if(bel[e[i].y]!=now){ 62 gre.add(now,bel[e[i].y]); 63 } 64 dfs(e[i].y,x); 65 } 66 } 67 int coun(int x,int k){ 68 int ans=blo[x].ask(k); 69 for(int i=gre.head[x];i;i=gre.next[i]){ 70 ans+=coun(gre.ai[i],k); 71 } 72 return ans; 73 } 74 int cnt(int x,int fa,int k){ 75 int ans=a[x]>k; 76 for(int i=head[x];i;i=e[i].next){ 77 if(e[i].y==fa) continue; 78 if(bel[e[i].y]==bel[x]){ 79 ans+=cnt(e[i].y,x,k); 80 } 81 else{ 82 ans+=coun(bel[e[i].y],k); 83 } 84 } 85 return ans; 86 } 87 int main(){ 88 //freopen("wtf.in","r",stdin); 89 //freopen("wtf.out","w",stdout); 90 memset(e,0,sizeof(e)); 91 memset(blo,0,sizeof(blo)); 92 scanf("%d",&n); 93 ad=n; 94 int u,v; 95 sz=(int)sqrt((double)n); 96 for(int i=1;i<n;i++){ 97 scanf("%d%d",&u,&v); 98 init(u,v); 99 init(v,u); 100 } 101 for(int i=1;i<=n;i++){ 102 scanf("%d",&a[i]); 103 } 104 scanf("%d",&m); 105 bel[1]=++tot; 106 dfs(1,0); 107 for(int i=1;i<=tot;++i){ 108 sort(blo[i].a+1,blo[i].a+blo[i].num+1); 109 } 110 for(int op,u,x,i=1;i<=m;++i){ 111 112 scanf("%d%d%d",&op,&u,&x); 113 u^=lastans,x^=lastans; 114 if(op==0){ 115 printf("%d ",lastans=cnt(u,f[u],x)); 116 } 117 else if(op==1){ 118 int fr=bel[u]; 119 for(int i=1;i<=blo[fr].num;i++){ 120 if(blo[fr].a[i]==a[u]){ 121 blo[fr].a[i]=a[u]=x; 122 } 123 } 124 sort(blo[fr].a+1,blo[fr].a+1+blo[fr].num); 125 } 126 else{ 127 int fr=bel[u]; 128 a[++ad]=x; 129 init(u,ad); 130 f[ad]=u; 131 if(blo[fr].num<sz){ 132 bel[ad]=fr; 133 blo[fr].a[++blo[fr].num]=x; 134 sort(blo[fr].a+1,blo[fr].a+1+blo[fr].num); 135 } 136 else{ 137 bel[ad]=++tot; 138 blo[bel[ad]].a[++blo[bel[ad]].num]=x; 139 gre.add(fr,bel[ad]); 140 } 141 } 142 } 143 return 0; 144 }
bzoj4566jzyzoj1547[haoi2016t5]找相同子串后缀数组(代码片段)
http://172.20.6.3/Problem_Show.asp?id=1547http://www.lydsy.com/JudgeOnline/problem.php?id=4566似乎后缀自动机是正解,但是后缀数组+并查集也可以乱搞a掉,定义字符串大小的整型变量时候charsiz导致re什么的;我大概是个zz。顺便存个板子,抄紫萱学姐... 查看详情
[bzoj3729]gty的游戏
[BZOJ3729]Gty的游戏试题描述某一天gty在与他的妹子玩游戏。妹子提出一个游戏,给定一棵有根树,每个节点有一些石子,每次可以将不多于L的石子移动到父节点,询问将某个节点的子树中的石子移动到这个节点先手是否有必胜策... 查看详情
bzoj3744:gty的妹子序列
3744:Gty的妹子序列TimeLimit:20Sec MemoryLimit:128MBSubmit:1335 Solved:379[Submit][Status][Discuss]Description我早已习惯你不在身边,人间四月天寂寞断了弦。回望身后蓝天,跟再见说再见……某天,蒟蒻Autumn发现了从Gty的妹子... 查看详情
bzoj3720gty的妹子树块状树
【BZOJ3720】Gty的妹子树我曾在弦歌之中听过你,檀板声碎,半出折子戏。舞榭歌台被风吹去,岁月深处尚有余音一缕……Gty神(xian)犇(chong)从来不缺妹子……他来到了一棵妹子树下,发现每个妹子有一个美丽度&hellip... 查看详情
bzoj3720:gty的妹子树
3720:Gty的妹子树TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 1493 Solved: 502[Submit][Status][Discuss]Description我曾在弦歌之中听过你,檀板声碎,半出折子戏。舞榭歌台被风吹去,岁月深处尚有余音一缕…&h 查看详情
bzoj3744:gty的妹子序列
...见说再见……某天,蒟蒻Autumn发现了从Gty的妹子树(bzoj3720)上掉落下来了许多妹子,他发现她们排成了一个序列,每个妹子有一个美丽度。Bakser神犇与他打算研究一下这个妹子序列,于是Bakser神犇问道:"你知道区间[l,r]中妹子们... 查看详情
bzoj3720gty的妹子树
Description我曾在弦歌之中听过你,檀板声碎,半出折子戏。舞榭歌台被风吹去,岁月深处尚有余音一缕……Gty神(xian)犇(chong)从来不缺妹子……他来到了一棵妹子树下,发现每个妹子有一个美丽度……由于Gty... 查看详情
bzoj3720:gty的妹子树
Description我曾在弦歌之中听过你,檀板声碎,半出折子戏。舞榭歌台被风吹去,岁月深处尚有余音一缕……Gty神(xian)犇(chong)从来不缺妹子……他来到了一棵妹子树下,发现每个妹子有一个美丽度……由于Gty很哲♂学,他只对美丽... 查看详情
luogu2137/bzoj3720gty的妹子树
题面:https://www.luogu.org/problemnew/show/P2137https://www.lydsy.com/JudgeOnline/problem.php?id=3720 查看详情
bzoj3744gty的妹子序列
大力分块+树状数组+主席树……#include<bits/stdc++.h>#defineN50005#definepapair<int,int>#definefifirst#definescsecondusingnamespacestd;intn,m,cnt,tot,size,t;inta[N],c[N],num[N],rt[N];intsum[250][N];inlin 查看详情
bzoj3720:gty的妹子树
用“重量平衡树”实现的ETT套平衡树就可以做到$O(nlog^2n)$了。然而我很无聊地写了个$O(nsqrt{nlogn})$的根号重构,就是每$O(sqrt{nlogn})$次修改就用$O(nlogn)$的代价重构函数式trie。#include<cstdio>#include<vector>#definepbpush_backconstintN=6... 查看详情
bzoj3809gty的二逼妹子序列
3809:Gty的二逼妹子序列TimeLimit: 80Sec MemoryLimit: 28MBSubmit: 2195 Solved: 674[Submit][Status][Discuss]DescriptionAutumn和Bakser又在研究Gty的妹子序列了!但他们遇到了一个难题。 对于一段妹 查看详情
bzoj3809gty的二逼妹子序列|莫队+分块
BZOJ3809Gty的二逼妹子序列|莫队+分块Autumn和Bakser又在研究Gty的妹子序列了!但他们遇到了一个难题。对于一段妹子们,他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。为了方便,我们规定妹子们的美丽度全都在... 查看详情
bzoj3680吊打xxx随机化
题目描述gty又虐了一场比赛,被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身,但还是被人多势众的蒟蒻抓住了。蒟蒻们将n个gty吊在n根绳子上,每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。吊好gty... 查看详情
bzoj38093809:gty的二逼妹子序列(莫队+分块)
3809:Gty的二逼妹子序列TimeLimit: 80Sec MemoryLimit: 28MBSubmit: 1728 Solved: 513DescriptionAutumn和Bakser又在研究Gty的妹子序列了!但他们遇到了一个难题。对于一段妹子们,他们想让你帮忙求出这之内美丽度∈[a,b... 查看详情
bzoj3720gty的妹子树树分块
题目我曾在弦歌之中听过你,檀板声碎,半出折子戏。舞榭歌台被风吹去,岁月深处尚有余音一缕……Gty神(xian)犇(chong)从来不缺妹子……他来到了一棵妹子树下,发现每个妹子有一个美丽度……由于Gty很哲♂学,他只对美丽度... 查看详情
bzoj3809gty的二逼妹子序列
3809:Gty的二逼妹子序列TimeLimit:80Sec MemoryLimit:28MBSubmit:1504 Solved:436[Submit][Status][Discuss]DescriptionAutumn和Bakser又在研究Gty的妹子序列了!但他们遇到了一个难题。 对于一段妹子们,他们想让你帮忙求出这之内美丽度... 查看详情
bzoj3744gty的妹子序列分块+树状数组+主席树
...见说再见……某天,蒟蒻Autumn发现了从Gty的妹子树(bzoj3720)上掉落下来了许多妹子,他发现她们排成了一个序列,每个妹子有一个美丽度。Bakser神犇与他打算研究一下这个妹子序列,于是Bakser神犇问道:"你知道区间[l,r]中妹子们... 查看详情