[AGC002D] Stamp Rally [并查集+整体二分]

题面：

传送门

思路：

看到最大值最小，想到二分答案

原始的想法就是对于每一个询问二分，并查集每次更新，插入1~i的所有边统计答案，时间效率O(nmQlogm),gg

可是，这种方法里面，每一对询问二分的过程中，有很多次并查集的清空、插入做的是重复的工作

那么就考虑用整体二分将这些工作一次做完

我们用一个队列que来实现这个过程

一开始，向队列里插入元素(0,m,{1,2,...,Q})，代表集合1~Q的答案在范围(0,m]中

每一次从队头取出元素u(l,r,S)，如果r-l==1，那么S中所有询问的答案就是R了

否则，令mid=(l+r)/2，查看并查集里面当前插入了多少条边

如果当前的边数比mid大，就清空重新加到mid

否则就加到mid就好了

在这个并查集中，O(1)统计每对节点所能到达的所有节点数有没有大于z

大于等于z的放到t1(l,mid,S1)里面，小于z的放到t2(mid,r,S2)里面

把t1t2放到队尾就可以了

最后把答案输出

Code：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<vector>
  6 #include<queue>
  7 #define ll long long
  8 #define MOD 1000000007
  9 using namespace std;
 10 inline int read(){
 11     int re=0,flag=1;char ch=getchar();
 12     while(ch>'9'||ch<'0'){
 13         if(ch=='-') flag=-1;
 14         ch=getchar();
 15     }
 16     while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
 17     return re*flag;
 18 }
 19 int n,m,Q,first[100010],cnt,ans[100010];
 20 struct edge{
 21     int to,next;
 22 }a[200010];
 23 void add(int u,int v){
 24     a[++cnt]=(edge){v,first[u]};first[u]=cnt;
 25     a[++cnt]=(edge){u,first[v]};first[v]=cnt;
 26 }
 27 int f[100010];
 28 void init(){
 29 //    cout<<"init"<<endl;
 30     for(int i=1;i<=n;i++) f[i]=-1;
 31 }
 32 int find(int x){
 33     return ((f[x]<0)?x:(f[x]=find(f[x])));
 34 }
 35 void join(int x,int y){
 36 //    cout<<"join "<<x<<ends<<y<<endl;
 37     int fx=find(x),fy=find(y);
 38 //    cout<<"find "<<fx<<ends<<fy<<endl;
 39     if(fx==fy) return;
 40     if(f[fx]>f[fy]) swap(x,y),swap(fx,fy);
 41     f[fx]+=f[fy];f[fy]=fx;
 42 }
 43 struct query{
 44     int x,y,z;
 45 }q[100010];
 46 struct node{
 47     int l,r;vector<int>q;
 48     void clear(){l=r=0;q.clear();}
 49 };
 50 bool check(int x){
 51 //    cout<<"check query "<<x<<endl;
 52     int tmp=(-f[find(q[x].x)]-f[find(q[x].y)]);
 53     if(find(q[x].x)==find(q[x].y)) tmp/=2;
 54     return (q[x].z<=tmp);
 55 }
 56 queue<node>que;
 57 void bfs(){
 58     int i,j,cur=0,mid;node u,t1,t2;init();
 59     while(!que.empty()){
 60         u=que.front();que.pop();t1.clear();t2.clear();
 61 //        cout<<"query "<<u.l<<ends<<u.r<<ends<<cur<<endl;
 62 //        for(i=0;i<u.q.size();i++) cout<<u.q[i]<<ends;cout<<endl;
 63 //        system("pause");
 64         if(u.r-u.l==1){
 65             for(i=0;i<u.q.size();i++) ans[u.q[i]]=u.r;
 66             continue;
 67         }
 68         mid=(u.r+u.l)>>1;
 69         if(cur>mid) init(),cur=0;
 70         while(cur<mid) cur++,join(a[cur<<1].to,a[(cur<<1)-1].to);
 71         j=u.q.size();
 72         t1.l=u.l;t1.r=mid;t2.l=mid;t2.r=u.r;
 73         for(i=0;i<j;i++){
 74             if(check(u.q[i])) t1.q.push_back(u.q[i]);
 75             else t2.q.push_back(u.q[i]);
 76         }
 77         que.push(t1);que.push(t2);
 78     }
 79 }
 80 int main(){
 81     memset(first,-1,sizeof(first));
 82     int i,t1,t2;node tmp;
 83     n=read();m=read();
 84     for(i=1;i<=m;i++){
 85         t1=read();t2=read();add(t1,t2);
 86     }
 87     Q=read();
 88     for(i=1;i<=Q;i++){
 89         q[i].x=read();q[i].y=read();q[i].z=read();
 90         tmp.q.push_back(i);
 91     }
 92     tmp.l=0;tmp.r=m;
 93     que.push(tmp);
 94     bfs();
 95     for(i=1;i<=Q;i++){
 96         printf("%d
",ans[i]);
 97     }
 98 }
 99 /*
100 5 6
101 2 3
102 4 5
103 1 2
104 1 3
105 1 4
106 1 5
107 6
108 2 4 3
109 2 4 4
110 2 4 5
111 1 3 3
112 1 3 4
113 1 3 5
114 
115 */

[AGC002D] Stamp Rally [并查集+整体二分]

相关推荐