设计公司网站官网/域名ip查询

Description

给出一个n个点的数，和m次操作。每个点有颜色和权值。
每次操作分4种
1：修改一个点的颜色
2：修改一个点的权值
3：询问从x到y的路径上，和x相同颜色的点的权值和（保证x，y同颜色）
4：询问从x到y的路径上，和x相同颜色的点的权值最大值（保证x，y同颜色）
n,m<=10^5,颜色<=10^5,权值<=10^4

Solution

首先，很容易想到链剖（蒟蒻表示并不会link-cut tree）。
很明显在线不可做，那么就尝试离线。
把一个修改颜色的操作看成两个，一个加入，一个删除。然后把所有关于同一个颜色的操作排在一起（这里可以用快排乱搞，笔者用的是模链）。然后直接处理同一颜色的所有操作。
实现复杂，注意细节，然后就没有了。（好懒）

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a) for(int i=last[a];i;i=next[i])
#define N 100005
using namespace std;
struct node{int ty,x,y,id;}ask[N*5];
int n,m,tot,x,y,l,a[N],c[N],son[N],size[N],ans[N],tree[N*3][2];
int t[N*5],next[N*5],last[N],h[N],d[N],fa[N],top[N],w[N],bz[N];
char ch,hc;
void add(int x,int y) {t[++l]=y;if (!last[x]) last[x]=l;if (h[x]) next[h[x]]=l;h[x]=l;
}
int merge(int x,int y,int z) {if (z) return max(x,y);else return x+y;
}
void dfs(int x,int y) {size[x]=1;fa[x]=y;d[x]=d[y]+1;int k=0;rep(i,x) if (t[i]!=y) {dfs(t[i],x);size[x]+=size[t[i]];if (size[t[i]]>k) k=size[t[i]],son[x]=t[i];}
}
void make(int x,int y) {top[x]=y;w[x]=++tot;if (!son[x]) return;make(son[x],y);rep(i,x) if (t[i]!=fa[x]&&t[i]!=son[x]) make(t[i],t[i]);
}
void change(int v,int l,int r,int x,int y) {if (l==r) {tree[v][0]=tree[v][1]=y;return;}int m=(l+r)/2;if (x<=m) change(v*2,l,m,x,y);else change(v*2+1,m+1,r,x,y);fo(i,0,1) tree[v][i]=merge(tree[v*2][i],tree[v*2+1][i],i);
}
int find(int v,int l,int r,int x,int y,int z) {if (l==x&&r==y) return tree[v][z];int m=(l+r)/2;if (y<=m) return find(v*2,l,m,x,y,z);else if (x>m) return find(v*2+1,m+1,r,x,y,z);else return merge(find(v*2,l,m,x,m,z),find(v*2+1,m+1,r,m+1,y,z),z);
}
int query(int x,int y,int z) {int f1=top[x],f2=top[y],ans=0;while (f1!=f2) {if (d[f1]<d[f2]) swap(f1,f2),swap(x,y);ans=merge(ans,find(1,1,n,w[f1],w[x],z),z);x=fa[f1];f1=top[x];}if (d[x]>d[y]) swap(x,y);ans=merge(ans,find(1,1,n,w[x],w[y],z),z);return ans;
}
void solve(int x) {rep(i,x) {int k=t[i];if (ask[k].ty==1) change(1,1,n,w[ask[k].x],ask[k].y);else ans[ask[k].id]=query(ask[k].x,ask[k].y,ask[k].ty-2);}
}
int main() {freopen("travel.in","r",stdin);freopen("travel.out","w",stdout);scanf("%d%d",&n,&m);fo(i,1,n) scanf("%d%d",&a[i],&c[i]);fo(i,1,n-1) scanf("%d%d",&x,&y),add(x,y),add(y,x);dfs(1,0);make(1,1);scanf("%c",&ch);l=tot=0;memset(last,0,sizeof(last));memset(h,0,sizeof(h));memset(t,0,sizeof(t));memset(next,0,sizeof(next));fo(i,1,n) {ask[++tot].ty=1;ask[tot].x=i;ask[tot].y=a[i];add(c[i],tot);}fo(i,1,m) {scanf("%c%c%d%d",&ch,&hc,&x,&y);if (ch=='C') {if (hc=='C') {ask[++tot].ty=1;ask[tot].x=x;ask[tot].y=a[x];add(y,tot);ask[++tot].ty=1;ask[tot].x=x;ask[tot].y=0;add(c[x],tot);c[x]=y;} else {ask[++tot].ty=1;ask[tot].x=x;ask[tot].y=y;add(c[x],tot);a[x]=y;}} else {if (hc=='S') ask[++tot].ty=2;else ask[++tot].ty=3;ask[tot].x=x;ask[tot].y=y;ask[tot].id=i;add(c[x],tot);bz[i]=c[x];}scanf("%c",&ch);}fo(i,1,n) {ask[++tot].ty=1;ask[tot].x=i;ask[tot].y=0;add(c[i],tot);}fo(i,0,N-5) solve(i);fo(i,1,m) if (bz[i]) printf("%d\n",ans[i]);
}