# Bzoj3545: [ontak2010] peaks

2020-12-07 15:04:46

solution ：
Good question .
It's just not mandatory online .
Forcing online means it won't .

offline .
First x The points that can be reached can actually reach each other .
So we can think of it as a connecting block .
In fact, it is the minimum spanning tree to require the edge weight to be as small as possible .

Offline, first press the x Sort .
And then, in turn, build less than or equal to x The minimum spanning tree of .
Then the current v At the end of the link block k Big is actually the answer .
When searching and compressing paths, merge the chairman tree .

Make complaints ：
The time limit is too small .40s Ok or not .
This machine is too slow. It runs at every point 5 second .
Submit TLE.
At this time, of course, it's time to find karchang to optimize .
It's amazing %%%.
Fast reading of metaphysics .
And a bunch of things I couldn't find in the code before ..
Get my five second program to three .
then 7000ms+ After that

Code implementation ：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
inline char nc() {
static char buf[1000000],*p1=buf,*p2=buf;
}
inline int read(void) {
char ch=nc();
int sum=0;
while(!(ch>='0'&&ch<='9'))
ch=nc();
while(ch>='0'&&ch<='9')
sum=(sum<<3)+(sum<<1)+(ch^48),ch=nc();
return sum;
}
struct node {

int lc,rc,c;}t[2000001];int cnt,rt[200001];
inline void build(int &u,int l,int r,int p) {
if(u==0)u=++cnt;t[u].c++;
if(l==r)return ;int mid=(l+r)/2;
if(p<=mid)build(t[u].lc,l,mid,p);
else build(t[u].rc,mid+1,r,p);
}
int fa[100001];inline int findfa(int x) {

if(fa[x]!=x)fa[x]=findfa(fa[x]);return fa[x];}
void Merge(int &u1,int u2) {
if(u1==0) {u1=u2;return ;}if(u2==0)return ;
t[u1].c+=t[u2].c;
Merge(t[u1].lc,t[u2].lc);
Merge(t[u1].rc,t[u2].rc);
}
int S[100001];
inline int find(int u,int l,int r,int k) {
if(t[u].c<k)return -1;
if(l==r)return S[l];
int mid=(l+r)/2;
if(k<=t[t[u].rc].c)return find(t[u].rc,mid+1,r,k);
else return find(t[u].lc,l,mid,k-t[t[u].rc].c);
}
struct trnode {

int x,y,c,id,ans;}a[500001],Q[500001];int len;
bool cmp(trnode n1,trnode n2) {

return n1.c<n2.c;}
bool cmp2(trnode n1,trnode n2) {

return n1.y<n2.y;}
struct edge {

int x,id;}s[500001];
bool cmp1(edge n1,edge n2) {

return n1.x<n2.x;}
bool cmp3(trnode n1,trnode n2) {

return n1.id<n2.id;}
int main() {
//freopen("3545.in","r",stdin);freopen("3545.out","w",stdout);
sort(s+1,s+1+n,cmp1);int tot=0;
for(int i=1;i<=n;i++) {
if(s[i].x!=s[i-1].x)tot++;S[tot]=s[i].x;
build(rt[s[i].id],1,n,tot);
}
for(register int i=1;i<=m;++i) {
}
for(int i=1;i<=n;++i)fa[i]=i;
sort(a+1,a+len+1,cmp);sort(Q+1,Q+1+m,cmp2);int tt=1;
for(register int i=1;i<=m;++i) {
for(register int j=tt;j<=len;++j) {
if(a[j].c>Q[i].y) {tt=j;break;}
int xx=findfa(a[j].x),yy=findfa(a[j].y);
if(xx!=yy) {fa[xx]=yy;Merge(rt[yy],rt[xx]);}
if(j==len)tt=len+1;
}Q[i].ans=find(rt[findfa(Q[i].x)],1,n,Q[i].c);
}sort(Q+1,Q+1+m,cmp3);
for(int i=1;i<=m;i++)printf("%d\n",Q[i].ans);
return 0;
}

https://chowdera.com/2020/12/20201207150436872z.html