「省选模拟赛」小奇的花园
原题：「泉七培训-刘定峰」花园
「题目背景」
小奇在家中的花园漫步时，总是会思考一些奇怪的问题。
「问题描述」
小奇的花园有n个温室，标号为1到n，温室以及以及温室间的双向道路形成一棵树。
每个温室都种植着一种花，随着季节的变换，温室里的花的种类也在不断发生着变化。
小奇想知道从温室x走到温室y的路径中(包括两个端点),第t种花出现的次数。
「输入格式」
第一行为两个整数n，q，表示温室的数目和操作的数目。
第二行有n个整数T1，T2…Tn其中Ti表示温室i中的花的种类。
接下来n-1行,每个两个整数x, y,表示温室x和y之间有一条双向道路。
接下来q行,表示q个操作,分别为以下两种形式之一:
• C x t 表示在温室x中的花的种类变为t。
• Q x y t 表示询问温室x走到温室y的路径中(包括两个端点),第t种花出现
的次数。
为了体现在线操作,输入数据中的每个操作的参数都进行了加密。记最后一次询问的答案为anslast(一开始设anslast为0),下次读入中的x,y,t均需要异或上anslast以得到真实值，在C/C++中异或为ˆ运算符，在pascal中为xor运算符。
「输出格式」
输出q行，每行一个正整数表示该次询问答案。
「样例输入」
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
「样例解释」
加密前的操作:
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
「数据范围」
对于30%的数据,有n <= 1000, q <= 2000。
对于50%的数据,有n <= 10000, q <= 20000。
对于100%的数据,有n <= 100000, q <= 200000，0 <= T < 2^31。
「题解」
对于50%的数据，求出lca然后暴力
当年做这题的时候我很年轻，正好做了CTSC网络管理，就现场写了暴力：树链剖分+线段树套平衡树，这个做法应该很直接。其实对每一种权值建一棵线段树就不需要平衡树了，不过需要用map来存种类，但是这样还是很麻烦。
对于100%的数据
运用部分和思想把单点修改，路径查询转化成子树修改，单点询问。
具体地说我们用Vi 表示点i 的权值，Si 表示点i 到根节点上的权值和，那么询问x 到y 路径的权值和时，我们找到x 和y 的lca 那么答案就是Sx + Sy – 2Slca + Vlca. 而如果修改点x 的权值，就相当于x 子树上所有点的Si 都加上了一个数，我们只要先处理DFS序列之后就转化成区间加，这样可用线段树或者树状数组实现。
70分 树链剖分+线段树套平衡树 4个log几乎相当于暴力，但是常数小
|
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 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 |
#include<iostream> #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<ctime> #define ll long long #define M 15000005 using namespace std; //---------------------------------------------------------------- inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //----------------------------------------------------------------快速读入 bool vis[100005]; int n,q,cnt,sz,place,last; int T[100005]; int ls[M],rs[M],w[M],v[M],rnd[M]; int fa[100005][17],deep[100005],son[100005],pl[100005],belong[100005],root[400005]; //---------------------------------------------------------------- struct hzwer{int to,next;}e[200005];int head[100005]; void ins(int u,int v) { e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt; e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt; } //----------------------------------------------------------------边表 void dfs1(int x) { son[x]=1;vis[x]=1; for(int i=1;i<=16;i++) { if(deep[x]<(1<<i))break; fa[x][i]=fa[fa[x][i-1]][i-1]; } for(int i=head[x];i;i=e[i].next) { if(vis[e[i].to])continue; deep[e[i].to]=deep[x]+1; fa[e[i].to][0]=x; dfs1(e[i].to); son[x]+=son[e[i].to]; } } void dfs2(int x,int chain) { int k=0;place++; pl[x]=place;belong[x]=chain; for(int i=head[x];i;i=e[i].next) if(deep[e[i].to]>deep[x]&&son[e[i].to]>son[k]) k=e[i].to; if(k==0)return; dfs2(k,chain); for(int i=head[x];i;i=e[i].next) if(deep[e[i].to]>deep[x]&&k!=e[i].to) dfs2(e[i].to,e[i].to); } int lca(int x,int y) { if(deep[x]<deep[y])swap(x,y); int t=deep[x]-deep[y]; for(int i=0;i<=16;i++) if(t&(1<<i))x=fa[x][i]; for(int i=16;i>=0;i--) if(fa[x][i]!=fa[y][i]) {x=fa[x][i];y=fa[y][i];} if(x==y)return x; else return fa[x][0]; } //----------------------------------------------------------------预处理 void rturn(int &k) {int t=ls[k];ls[k]=rs[t];rs[t]=k;k=t;} void lturn(int &k) {int t=rs[k];rs[k]=ls[t];ls[t]=k;k=t;} void insert(int &k,int num) { if(!k){k=++sz;w[k]=1;v[k]=num;rnd[k]=rand();return;} if(num==v[k])w[k]++; else if(num<v[k]){insert(ls[k],num);if(rnd[ls[k]]<rnd[k])rturn(k);} else {insert(rs[k],num);if(rnd[rs[k]]<rnd[k])lturn(k);} } void del(int &k,int num) { if(!k)return; if(v[k]==num) { if(w[k]>1){w[k]--;return;} if(ls[k]*rs[k]==0)k=ls[k]+rs[k]; else if(rnd[ls[k]]<rnd[rs[k]]){rturn(k);del(k,num);} else {lturn(k);del(k,num);} } else if(num<v[k])del(ls[k],num); else del(rs[k],num); } int getw(int k,int num) { if(!k)return 0; if(num==v[k])return w[k]; if(num<v[k])return getw(ls[k],num); else return getw(rs[k],num); } //----------------------------------------------------------------平衡树 void change(int k,int l,int r,int x,int num,int y) { if(y!=-1)del(root[k],y); insert(root[k],num); if(l==r)return; int mid=(l+r)>>1; if(x<=mid)change(k<<1,l,mid,x,num,y); else change(k<<1|1,mid+1,r,x,num,y); } int ask(int k,int l,int r,int x,int y,int v) { if(l==x&&y==r)return getw(root[k],v); int mid=(l+r)>>1; if(y<=mid)return ask(k<<1,l,mid,x,y,v); else if(x>mid)return ask(k<<1|1,mid+1,r,x,y,v); else return ask(k<<1,l,mid,x,mid,v)+ask(k<<1|1,mid+1,r,mid+1,y,v); } //----------------------------------------------------------------线段树 void solvechange(int x,int num,int y) { change(1,1,n,x,num,y); } int solvesum(int x,int f,int num) { int sum=0; while(belong[x]!=belong[f]) { sum+=ask(1,1,n,pl[belong[x]],pl[x],num); x=fa[belong[x]][0]; } sum+=ask(1,1,n,pl[f],pl[x],num); return sum; } int solveask(int x,int y,int num) { int t=lca(x,y); int sum=solvesum(x,t,num)+solvesum(y,t,num); if(T[t]==num)sum--; return sum; } //----------------------------------------------------------------树链剖分 int main() { freopen("garden.in","r",stdin); freopen("garden.out","w",stdout); srand(time(0)); n=read();q=read(); for(int i=1;i<=n;i++) T[i]=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); ins(u,v); } dfs1(1);dfs2(1,1); for(int i=1;i<=n;i++) solvechange(pl[i],T[i],-1); for(int i=1;i<=q;i++) { char ch[10]; scanf("%s",ch); int x=read()^last,y=read()^last,v; if(ch[0]=='C'){solvechange(pl[x],y,T[x]);T[x]=y;} else {v=read()^last;last=solveask(x,y,v);printf("%d\n",last);} } return 0; } |
100分
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<vector> #include<algorithm> #include<map> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } map<int,int> mp; int bin[20]; int lastans; int n,Q,sz,tot,cnt,top; int T[100005]; int deep[100005],fa[100005][17],q[200005]; int st[100005],ed[100005]; int root[300005],ls[10000005],rs[10000005],tag[10000005],v[10000005]; struct edge{int to,next;}e[200005];int last[100005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt; } void dfs(int x) { q[++top]=x; for(int i=1;i<=16;i++) if(bin[i]<=deep[x]) fa[x][i]=fa[fa[x][i-1]][i-1]; else break; for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa[x][0]) { fa[e[i].to][0]=x; deep[e[i].to]=deep[x]+1; dfs(e[i].to); } q[++top]=x; } int lca(int x,int y) { if(deep[x]<deep[y])swap(x,y); int t=deep[x]-deep[y]; for(int i=0;i<=16;i++) if(t&bin[i])x=fa[x][i]; for(int i=16;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return x==y?x:fa[x][0]; } void pushdown(int k,int l,int r) { if(!tag[k]||l==r)return; int t=tag[k];tag[k]=0; if(!ls[k])ls[k]=++sz; if(!rs[k])rs[k]=++sz; v[ls[k]]+=t;tag[ls[k]]+=t; v[rs[k]]+=t;tag[rs[k]]+=t; } void update(int &k,int l,int r,int x,int y,int val) { if(!k)k=++sz; pushdown(k,l,r); if(x==l&&y==r) { v[k]+=val; tag[k]+=val; return; } int mid=(l+r)>>1; if(y<=mid)update(ls[k],l,mid,x,y,val); else if(x>mid)update(rs[k],mid+1,r,x,y,val); else { update(ls[k],l,mid,x,mid,val); update(rs[k],mid+1,r,mid+1,y,val); } } int query(int k,int l,int r,int val) { if(!k)return 0; pushdown(k,l,r); if(l==r)return v[k]; int mid=(l+r)>>1; if(val<=mid)return query(ls[k],l,mid,val); else return query(rs[k],mid+1,r,val); } int main() { freopen("garden.in","r",stdin); freopen("garden.out","w",stdout); bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; n=read();Q=read(); for(int i=1;i<=n;i++) { T[i]=read(); if(!mp[T[i]])mp[T[i]]=++tot;T[i]=mp[T[i]]; } int x,y,t; for(int i=1;i<n;i++) { x=read();y=read(); insert(x,y); } dfs(1); for(int i=1;i<=top;i++) { t=q[i]; if(!st[t])st[t]=i; else ed[t]=i; } for(int i=1;i<=n;i++) update(root[T[i]],1,top,st[i],ed[i],1); char ch[5]; for(int i=1;i<=Q;i++) { scanf("%s",ch); if(ch[0]=='C') { x=read();t=read(); x^=lastans;t^=lastans; if(!mp[t])mp[t]=++tot;t=mp[t]; update(root[T[x]],1,top,st[x],ed[x],-1); update(root[t],1,top,st[x],ed[x],1); T[x]=t; } else { x=read();y=read();t=read(); x^=lastans;y^=lastans;t^=lastans; if(!mp[t])mp[t]=++tot;t=mp[t]; int f=lca(x,y); lastans=query(root[t],1,top,st[x])+query(root[t],1,top,st[y]); lastans-=2*query(root[t],1,top,st[f]); if(T[f]==t)lastans++; printf("%d\n",lastans); } } return 0; } |
计数器 9322758
OI 课件=>
OI 课件=>
[…] 做本题是参考了黄学长Hzwer的题解和程序，代码可能有相似之处，但线段树的操作绝对是我自己的风格。（求资瓷~） […]
[…] 做本题是参考了黄学长Hzwer的题解和程序，代码可能有相似之处，但线段树的操作绝对是我自己的风格。（求资瓷~） […]
0 <= T < 2^31, 太大了
吾王赛高
同楼上，学长，可以类似[sdoi2014旅行]一样对每一个种类建一棵线段树，动态开点吧
学长请问，直接向100分做法一样，用map存一下，然后每个种类建一颗线段树直接做树剖不就好了？