[20220212联考] 色
前言
这道题调了我一个下午、五分之一个晚上、半个上午。
调试版本 207 行，删掉调试信息 143 行，我手调了两个 \(n=3000\) 的数据，真的爽死了。
我也不知道这么一个猪鼻题为啥调这么久。
总之就是懒得对拍，而且这道题数据特别水，暴力都能过。
题目
给 \(n\) 个点 \(m\) 条边的无向图带权图，边权 \(w_i\)，每个点有个颜色 \(c_i\) 并保证每时每刻 \(1\le c_i\le C\)，有 \(Q\) 次修改，每次修改更改一个点的颜色，每次修改后询问两个不同颜色点之间的最短距离。
\(1\le C \le n\le 2\times 10^5;1\le m\le 3\times 10^5;1\le w_i\le 10^6;1\le Q\le 2\times 10^5.\)
原题面保证每时每刻所有点颜色不同，但是事实上数据不保证，此时输出 \(0\)。
屑题。
讲解
首先有两个观察：
- 最短距离一定是一条边的边权。
- 这条边一定在最小生成树上。
我挖出了第一个性质，第二个性质没想到，但是不难证明，如果没想到第二个性质也可以直接根号分治。
在树上就很好做了，时间复杂度 \(O(n\log_2n).\)
代码
为了纪念调这道题这么久，我把没有去掉注释的版本放上来好了。
//12252024832524
#include
#define TT template
using namespace std;
typedef long long LL;
typedef pair pii;
const int MAXN = 200005;
const int INF = 0x3f3f3f3f;
int n,m,C,Q;
int val[MAXN],c[MAXN];
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int f[MAXN];
int findSet(int x)
{
if(f[x] ^ x) f[x] = findSet(f[x]);
return f[x];
}
struct Edge
{
int u,v,w;
bool operator < (const Edge &px)const{
return w < px.w;
}
}E[MAXN<<1];
int head[MAXN],tot;
struct edge
{
int v,w,nxt;
}e[MAXN<<1];
void Add_Edge(int x,int y,int z)
{
e[++tot] = edge{y,z,head[x]};
head[x] = tot;
}
void Add_Double_Edge(int x,int y,int z)
{
Add_Edge(x,y,z);
Add_Edge(y,x,z);
}
multiset ans;
struct node
{
int clr,vl,x;
bool operator < (const node &px)const{
if(clr ^ px.clr) return clr < px.clr;
return vl < px.vl;
}
};
set s[MAXN];
void dfs(int x,int fa)
{
f[x] = fa;
for(int i = head[x],v; i ;i = e[i].nxt)
if((v = e[i].v) ^ fa)
dfs(v,x),val[v] = e[i].w,s[x].insert(node{c[v],val[v],v});
if(!s[x].size()) return;
// for(auto it = s[x].begin();it != s[x].end();it = s[x].lower_bound(make_pair(it->first+1,0)))
// if(c[x] ^ (it->first)) ans.insert(val[it->second]);
for(auto it = s[x].begin(),it2 = s[x].begin();it != s[x].end();it2 = it,++ it)
if(it == s[x].begin() || it->clr != it2->clr)
if(it->clr != c[x]) ans.insert(val[it->x]);
// printf("dfs ");Put(x,'\n');
// for(auto it = s[x].begin();it != s[x].end();++it) Put(it->first,' '),Put(it->second,'\n');
}
int MIN;
void dfs2(int x,int fa)
{
for(int i = head[x],v; i ;i = e[i].nxt)
if((v = e[i].v) ^ fa)
{
dfs2(v,x);
if(c[v] ^ c[x]) MIN = Min(MIN,e[i].w);
}
}
int main()
{
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
n = Read(); m = Read(); C = Read(); Q = Read();
for(int i = 1;i <= m;++ i) E[i].u = Read(),E[i].v = Read(),E[i].w = Read();
for(int i = 1;i <= n;++ i) c[i] = Read(),f[i] = i;
sort(E+1,E+m+1);
for(int i = 1;i <= m;++ i)
{
if(findSet(E[i].u) == findSet(E[i].v)) continue;
f[findSet(E[i].u)] = findSet(E[i].v);
Add_Double_Edge(E[i].u,E[i].v,E[i].w);
}
dfs(1,0);
//change 726's color,its son is 435,the edge value is 3901
// for(auto it = s[726].begin();it != s[726].end();++ it) Put(it->clr,' '),Put(it->x,' '),Put(val[it->x],'\n');
// return 0;
/*while(Q --> 0)
{
MIN = INF;
int pos = Read(),color = Read();
c[pos] = color;
dfs2(1,0);
Put(MIN,'\n');
if(Q == 2996) {printf("end\n");return 0;}
}*/
// printf("ans\n");
// for(auto it = ans.begin();it != ans.end();++it) Put(*it,'\n');
while(Q --> 0)
{
int pos = Read(),color = Read();
if(c[pos] == color) {Put(*ans.begin(),'\n');continue;}
if(f[pos])
{
auto it = s[f[pos]].lower_bound(node{c[pos],val[pos],pos});
auto it2 = it;
if(it != s[f[pos]].begin())//delete the old one
{
// if(Q == 2424) {printf("end\n");return 0;}
--it; if(it->clr != c[pos] && c[f[pos]] != c[pos]) ans.erase(ans.lower_bound(val[pos]));//you are the first.
it = it2; ++it; if(it != s[f[pos]].end() && it->clr == c[pos] && c[pos] != c[f[pos]]) ans.insert(val[it->x]);//same color
}
else
{
if(c[f[pos]] != c[pos]) ans.erase(ans.lower_bound(val[pos]));//you are the first.
++it; if(it != s[f[pos]].end() && it->clr == c[pos] && c[pos] != c[f[pos]]) ans.insert(val[it->x]);//same color
}
// if(c[pos] != it2->first || pos != it2->second) printf("wdnmd\n");
// printf("size %d %d\n",f[pos],s[f[pos]].size());
s[f[pos]].erase(it2);//bye~
// printf("size %d %d\n",f[pos],s[f[pos]].size());
s[f[pos]].insert(node{color,val[pos],pos});//add the new one
it2 = it = s[f[pos]].lower_bound(node{color,val[pos],pos});
if(it != s[f[pos]].begin())
{
// if(pos == 297) printf("wdnmd wdnmd %d %d %d %d %d\n",it->first,it->second,color,c[f[pos]],it->first);
--it; if(it->clr != color && color != c[f[pos]]) ans.insert(val[pos]);//you are the first
it = it2; ++it;
if(it != s[f[pos]].end() && it->clr == color && color != c[f[pos]]) ans.erase(ans.lower_bound(val[it->x]));//same color
}
else
{
if(color != c[f[pos]]) ans.insert(val[pos]);
it = it2; ++it;
if(it != s[f[pos]].end() && it->clr == color && color != c[f[pos]]) ans.erase(ans.lower_bound(val[it->x]));//same color
}
}
// printf("## 796796796 %d\n",val[297]);
// for(auto it = s[796].begin();it != s[796].end();++ it) Put(it->first,' '),Put(it->second,'\n');
// printf("woc %d\n",ans.size());
// for(auto woc = ans.begin();woc != ans.end();++woc) Put(*woc,' ');
// putchar('\n');
if(s[pos].size())
{
auto it = s[pos].lower_bound(node{c[pos],0,0});
// if(pos == 726)
// {
// printf("## 726726\n");
// Put(it->clr,' '),Put(it->x,' ');Put(c[pos],' ');Put(val[it->x],'\n');
// }
if(it != s[pos].end() && it->clr == c[pos]) ans.insert(val[it->x]);
it = s[pos].lower_bound(node{color,0,0});
if(it != s[pos].end() && it->clr == color) ans.erase(ans.lower_bound(val[it->x]));//printf("wrng %d\n",val[it->second]);
}
c[pos] = color;
if(ans.size()) Put(*ans.begin(),'\n');
else Put(0,'\n');
// if(Q == 2990) {printf("end\n");return 0;}
// printf("print\n");
// printf("ansize %d\n",ans.size());
// for(int i = 1;i <= 2;++ i)
// {
// Put(i,'\n');
// for(auto it = s[i].begin();it != s[i].end();++ it) Put(it->first,' '),Put(it->second,'\n');
// }
// putchar('\n');
}
return 0;
}
/*
3 2 3 4
1 2 3
2 3 1
1 1 2
3 3
2 3
1 2
2 2
*/