題目鏈接

https://codeforces.com/contest/1375/problem/H

題解

首先注意到 \(2.2\times 10^6\approx 2n\sqrt q\)，因此想到分塊。
考慮對值域進行分塊，每塊內值域連續，位置保持相對不變，大小為 \(B\)，分成 \(\frac{n}{B}\) 塊。
那么我們可以對每個塊內的 \(\frac{B(B+1)}{2}\) 個區間中的每個合并出一個集合，然后對于每組詢問在每個塊內求出對應的區間，并將每個塊內的集合合并到一起。
后一部分顯然需要 \(\frac{nq}{B}\) 次操作，考慮前一部分怎么做。

考慮對值域進行分治，每次處理一個值域區間對應的位置，那么對于當前值域區間的一個位置區間，可以直接由兩個子值域區間的對應位置區間合并得到。
總合并次數的遞歸式約為 \(T(n)=2T(\frac{n}{2})+\frac{n^2}{2}\)，得 \(T(n)\approx n^2\). 即每個塊內的預處理需要 \(B^2\) 次操作，總共就是 \(nB\) 次。

綜合兩部分，總共操作次數是 \(nB+\frac{nq}{B}\)，取 \(B=\sqrt q\) 則可以做到總次數為 \(2n\sqrt q\).

代碼

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define x first #define y second #define iter iterator #define riter reversed_iterator #define y1 Lorem_ipsum_ #define tm dolor_sit_amet_ #define pii pair<int,int> using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int mxN = 1<<12; const int mxM = 1<<16; const int mxSIZ = 2.2e6; const int mxB = 1<<8; int a[mxN+3],ai[mxN+3]; int n,m,siz,B; int ans[mxM+3]; vector<pii> way;int merge(int u,int v) {if(!u||!v) {return u+v;} way.push_back(mkpr(u,v)); return ++siz;}int f[mxB*2+3][mxB+3][mxB+3]; struct Block {int len,al,ar; int p[mxN+3];void solve(int u,int l,int r,vector<int> vec){if(l==r) {f[u][1][1] = ai[vec[1]]; return;}int mid = (l+r)>>1; vector<int> vecl(1),vecr(1);for(int i=1; i<vec.size(); i++) {if(vec[i]<=mid) {vecl.push_back(vec[i]);} else {vecr.push_back(vec[i]);}}solve(u<<1,l,mid,vecl); solve(u<<1|1,mid+1,r,vecr);for(int i=1,xl=1,xr=1; i<vec.size(); xl+=(vec[i]<=mid),xr+=(vec[i]>mid),i++){for(int j=i-1,yl=xl-1,yr=xr-1; j<vec.size(); j++,yl+=(vec[j]<=mid),yr+=(vec[j]>mid)){if(j==i-1) continue;f[u][i][j] = merge(f[u<<1][xl][yl],f[u<<1|1][xr][yr]);}}}int id[mxN+3],qwq[mxB+3][mxB+3];void build(){vector<int> vec(1);for(int i=1; i<=n; i++) {if(a[i]>=al&&a[i]<=ar) {vec.push_back(a[i]); id[i] = id[i-1]+1;} else {id[i] = id[i-1];}}solve(1,al,ar,vec);for(int i=1; i<vec.size(); i++) for(int j=1; j<vec.size(); j++) qwq[i][j] = f[1][i][j];}int query(int l,int r) {return qwq[id[l-1]+1][id[r]];} } blo[18];int main() {n = read(),m = read(),siz = n,B = min(n,mxB);for(int i=1; i<=n; i++) a[i] = read(),ai[a[i]] = i; siz = n;for(int i=1; (i-1)*B+1<=n; i++){blo[i].al = (i-1)*B+1,blo[i].ar = i*B;blo[i].build();}for(int q=1; q<=m; q++){int l = read(),r = read(); ans[q] = 0;for(int i=1; i<=(n-1)/B+1; i++){ans[q] = merge(ans[q],blo[i].query(l,r));}}printf("%d\n",siz);for(int i=0; i<way.size(); i++) printf("%d %d\n",way[i].x,way[i].y);for(int i=1; i<=m; i++) printf("%d ",ans[i]); puts("");return 0; }

總結

以上是生活随笔為你收集整理的Codeforces 1375H Set Merging (分块)的全部內容，希望文章能夠幫你解決所遇到的問題。

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