http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4100

比賽的時候封榜開始開這題，因為我的愚蠢沒有開出來。

?

查詢的最小值不用多說，維護一個當前的聯通快數量num, max(num - K,1LL)就是答案，問題在于最大值。

仔細一看就會發現，首先需要將所有的聯通快填滿，變成一個個完全子圖，這些被填滿的邊被稱為白給的邊，然后再開始計算答案，每次將兩個聯通快聯通的時候，只用一條有效邊就又會產生一堆白給的邊，所以說，為了使聯通快盡可能地多，我們需要每次不得不聯通兩個塊之后盡量產生更多的白給的邊。顯而易見的是，聯通需要從大的聯通快開始合并，可以貪心的產生更多的白給邊。

-----------------------------比賽想到了這一步，開始set暴力，最后十分鐘發現時間復雜度很假，開始掛機-------------------------------------------

被合并的聯通快的數量可以二分，二分的位置往右的所有聯通快將會被變成一個大聯通快，單調性顯然。

問題在于維護這個過程，考慮到權值線段樹，思路就明了了。

一開始先二分然后權值線段樹check的操作寫掛了，后面采用先權值線段樹，最后一個點二分的操作就過了。

意識到先二分的話時間復雜度是nlognlogn,先權值線段樹的話時間復雜度是Nlognlog(最后一個葉子節點的點數量)

#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 1e5 + 10; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; int fa[maxn]; LL size[maxn],edge[maxn],comp[maxn]; LL bg,num; void init(){for(int i = 0 ; i <= N ; i ++){fa[i] = i;size[i] = 1;edge[i] = 0;}num = N;bg = 0; } inline LL cul(LL x){return x * (x - 1) / 2; }struct Tree{int l,r;LL sum,num,edge; }tree[maxn << 2]; void Pushup(int t){tree[t].edge = tree[t << 1].edge + tree[t << 1 | 1].edge;tree[t].num = tree[t << 1].num + tree[t << 1 | 1].num;tree[t].sum = tree[t << 1].sum + tree[t << 1 | 1].sum; } void Build(int t,int l,int r){tree[t].l = l; tree[t].r = r;if(l == r){tree[t].sum = tree[t].num = tree[t].edge = 0;if(l == 1){tree[t].sum = tree[t].num = N;tree[t].edge = N * comp[l];}return; }int m = l + r >> 1;Build(t << 1,l,m); Build(t << 1 | 1,m + 1,r);Pushup(t); } void update(int t,int p,int v){if(tree[t].l == tree[t].r){tree[t].sum += v * tree[t].l;tree[t].num += v;tree[t].edge += comp[tree[t].l] * v;return;}int m = tree[t].l + tree[t].r >> 1;if(p <= m) update(t << 1,p,v);else update(t << 1 | 1,p,v);Pushup(t); } int find(int p){if(fa[p] == p) return p;return fa[p] = find(fa[p]); } void add(int u,int v){u = find(u); v = find(v);if(u == v){edge[u]++;bg--;return;} num--;bg -= comp[size[u]] - edge[u];bg -= comp[size[v]] - edge[v];update(1,size[u],-1);update(1,size[v],-1);fa[u] = v;size[v] += size[u];edge[v] += edge[u] + 1;bg += comp[size[v]] - edge[v];update(1,size[v],1); } LL cnt,E; int query(int t,LL k,LL v){if(tree[t].l == tree[t].r){int l = 0,r = tree[t].num;int ans = 0;while(l <= r){int m = l + r >> 1;if(comp[v + m * tree[t].l] < comp[tree[t].l] * m + k){ans = m + 1;l = m + 1; }else{r = m - 1;}}return ans;}if(comp[v + tree[t << 1 | 1].sum] >= k + tree[t << 1 | 1].edge) return query(t << 1 | 1,k,v);else return query(t << 1,k + tree[t << 1 | 1].edge,v + tree[t << 1 | 1].sum) + tree[t << 1 | 1].num; }int main(){int T; Sca(T);for(int i = 0 ; i < maxn; i ++) comp[i] = cul(i);while(T--){Sca2(N,M); init();Build(1,1,N);for(int i = 1; i <= M ; i ++){int q = read();if(q == 1){int u,v; u = read(); v = read(); add(u,v); }else{LL k; Scl(k);int MIN,MAX;MIN = max(num - k,1LL);if(k <= bg){MAX = num;}else{k -= bg;MAX = num - query(1,k,0LL) + 1;}printf("%d %d\n",MIN,MAX);}}} return 0; }

?

轉載于:https://www.cnblogs.com/Hugh-Locke/p/10844117.html

總結

以上是生活随笔為你收集整理的ZOJ4100 浙江省赛16th Problem A的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。