//zory 花园 | Zory的个人博客

花园

来源和评测点

某场比赛,没拿到数据
意会吧

题目

【题目大意】

【输入格式】


【输入样例】
5 8
10 20 30 40 50
1 2
1 3
3 4
3 5
Q 2 5 10
C 2 21
Q 3 4 21
C 6 22
Q 1 7 28
C 5 20
Q 2 5 20
Q 2 0 9
【输出样例】
1
2
0
3
1

分析1

这是加密前的操作
Q 2 5 10
C 3 20
Q 2 5 20
C 4 20
Q 3 5 30
C 5 20
Q 2 5 20
Q 1 3 10
咳咳先来个清新脱俗的暴力(50分)
主要是因为T太大,想不到好方法

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//Zory-2018
//*******************头文件*******************
#pragma once
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
//*******************全局常量*******************
const int MAXN=110000,MAXM=210000;
//*******************全局定义*******************
struct pt
{
int cl;
int hou;
int dep;
int fa;
pt()
{
hou=0;
}
}p[MAXN];
struct rod
{
int y,g;
}e[MAXM];
int ln=0;
void ins(int x,int y)
{
ln++;
e[ln].y=y;
e[ln].g=p[x].hou;
p[x].hou=ln;
}
//*******************接口*******************
void dfs(int x)
{
p[x].dep=p[ p[x].fa ].dep+1;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(y!=p[x].fa) p[y].fa=x,dfs(y);
}
}
//*******************主函数*******************
char s[10];
int main()
{
int n,q;scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",&p[i].cl);
for(int i=1;i<=n-1;i++)
{
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
dfs(1);
int lans=0;
while(q--)
{
int x,y,t;scanf("%s%d",s,&x);x=x^lans;
if(s[0]=='C')
{
scanf("%d",&t);
t=t^lans;
p[x].cl=t;
}
else
{
scanf("%d%d",&y,&t);
y=y^lans;t=t^lans;
int ans=0;
if(p[x].dep<p[y].dep) swap(x,y);
while(p[x].dep!=p[y].dep)
{
if(p[x].cl==t) ans++;
x=p[x].fa;
}
while(x!=y)
{
if(p[x].cl==t) ans++;
if(p[y].cl==t) ans++;
x=p[x].fa;y=p[y].fa;
}
if(p[x].cl==t) ans++;
lans=ans;
printf("%d\n",ans);
}
}
}

分析2

那么有请Rose大佬登场……
对于离散化,我也想到了map,但之后就不会了
他一语点醒了我,先%%%

先对颜色进行离散化,最坏情况下100000
树链剖分维护结构,然后线段树动态开点,最坏情况下就一条链,
然后不存在的节点点值就是0,修改操作的时候维护线段树,
询问操作的时候就调用对应线段树查询,
空间理论上最坏情况下10000020,最好情况下也是10000020
但因为删除等,还是会有损耗

以上就是大致思路了
嗯因为这道题算比较难的数据结构了,我加上了大量注释

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
//*******************全局常量*******************
const int MAXN=110000,MAXM=210000;
//*******************全局定义*******************
struct pt
{
int cl;//离散化后的值
int hou;
int dep,tot;
int fa,son,tp;
} p[MAXN];
//逻辑上 很多棵线段树
//实际上 为了动态开点 只有一个下标 用rt分配
struct rod
{
int y,g;
} e[MAXM];
int ln=0;
void ins(int x,int y)
{
ln++;
e[ln].y=y;
e[ln].g=p[x].hou;
p[x].hou=ln;
}
//*******************线段树*******************
int rt[MAXN];//rt[经过离散化的值]=根节点
struct mg
{
int lc,rc;
int c;
} sf[MAXN*30];
int len=0;
//类似于主席树,每次都是增加删除一条链
void change(int &x,int l,int r,int p,int z)
{
if(x==0) x=++len;//新节点
sf[x].c+=z;
if(l==r) return;
int mid=(l+r)/2;
if(p<=mid) change(sf[x].lc,l,mid,p,z);
else change(sf[x].rc,mid+1,r,p,z);
}
int ask(int x,int l,int r,int fl,int fr)
{
if(x==0) return 0;//减少空间支出
if(l==fl and r==fr) return sf[x].c;
int mid=(l+r)/2;
if(fr<=mid) return ask(sf[x].lc,l,mid,fl,fr);
if(fl>mid) return ask(sf[x].rc,mid+1,r,fl,fr);
return ask(sf[x].lc,l,mid,fl,mid)+ask(sf[x].rc,mid+1,r,mid+1,fr);
}
//*******************树链剖分*******************
void dfs(int x)
{
p[x].tot=1;p[x].son=0;
p[x].dep=p[ p[x].fa ].dep+1;
for(int k=p[x].hou; k>0; k=e[k].g)
{
int y=e[k].y;
if(y!=p[x].fa)
{
p[y].fa=x;
dfs(y);
p[x].tot+=p[y].tot;
if(p[y].tot>p[p[x].son].tot) p[x].son=y;
}
}
}
int nln=0;
int nb[MAXN];
void dfs2(int x,int tp)
{
nb[x]=++nln;p[x].tp=tp;
if(p[x].son>0) dfs2(p[x].son,tp);//debug
for(int k=p[x].hou; k>0; k=e[k].g)
{
int y=e[k].y;
if(y!=p[x].fa and y!=p[x].son) dfs2(y,y);//debug
}
}
//*******************接口*******************
int n;
map<int,int> mp;//key=大数字 元素=离散化后的值
int cnt=0;
int newcol(int col)
{
if(mp[col]==0) return mp[col]=++cnt;
return mp[col];
}
//*******************主函数*******************
char s[10];
int main()
{
int q;scanf("%d%d",&n,&q);
for(int i=1; i<=n; i++)
{
int tc;scanf("%d",&tc);
p[i].cl=newcol(tc);
}
for(int i=1; i<=n-1; i++)
{
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
p[1].fa=0;dfs(1);
dfs2(1,1);
for(int i=1;i<=n;i++) change(rt[ p[i].cl ],1,n,nb[i],1);
int lans=0;
while(q--)
{
int x,y,col;
scanf("%s%d",s,&x);x=x^lans;
if(s[0]=='C')
{
scanf("%d",&col);col=col^lans;
change(rt[ p[x].cl ],1,n,nb[x],-1);
p[x].cl=newcol(col);
change(rt[ p[x].cl ],1,n,nb[x],1);
}
else
{
scanf("%d%d",&y,&col);
y=y^lans;col=mp[col^lans];
int ans=0;
while(p[x].tp!=p[y].tp)
{
if(p[p[x].tp].dep<p[p[y].tp].dep) swap(x,y);
ans+=ask(rt[col],1,n,nb[ p[x].tp ],nb[ x ]);
x=p[p[x].tp].fa;
}
if(p[x].dep<p[y].dep) swap(x,y);
lans=ans+ask(rt[col],1,n,nb[y],nb[x]);
printf("%d\n",lans);
}
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-02/花园.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!