codeforces 811E Vladik and Entertaining Flags
题面
(n*m(1<=n<=10, 1<=m<=1e5))的棋盘，每个格子有一个值。
定义联通块：联通块中所有格子的值相等，并且格子四联通。
(1e5)次询问，每次询问子矩形((1, l, n, r))中联通块的数量。
题解
线段树区间合并。
(cnt[rt])：区间中联通块个数
(pre[rt][])：在区间中用并查集维护端点的连通性。在给合并之后的集合重新编号时，要注意并查集是用集合中某个点的标号表示整个集合的标号，不能直接用离散化的方法重命名。
upd
建一棵线段树，每个节点存l列到r列的信息（联通块个数，l列和r列上每个格子属于哪个联通块）。
合并的时候其实是将标号合并起来。
http://acm.hs97.cn/article/1873
代码
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define sz(x) (int)x.size()
#define de(x) cout<< #x<<" = "<<x<<endl
#define dd(x) cout<< #x<<" = "<<x<<" "
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//------
const int N=11, M=101010;
int n,m,q,mrt,cntn;
int a[N][M];
int cnt[M*4+77], pre[M*4+77][N<<2];
int find(int rt,int x) {
if(pre[rt][x]==x) return x;
return pre[rt][x]=find(rt,pre[rt][x]);
}
void join(int rt,int x,int y) {
int fx=find(rt,x);
int fy=find(rt,y);
pre[rt][fx]=fy;
}
void up(int rt,int mid,int L,int R) {
rep(i,0,n) {
pre[rt][i]=pre[L][i];
pre[rt][i+n]=pre[L][i+n];
pre[rt][i+2*n]=pre[R][i]+2*n;
pre[rt][i+3*n]=pre[R][i+n]+2*n;
}
cnt[rt]=cnt[L]+cnt[R];
rep(i,0,n) if(a[i][mid]==a[i][mid+1]&&find(rt, i+n)!=find(rt, i+2*n)) join(rt, i+n, i+2*n), --cnt[rt];
int vis[N<<2]={0};
rep(i,0,n) {
int t;
t=find(rt, i);
if(!vis[t]) vis[t]=i+1;
t=find(rt, i+3*n);
if(!vis[t]) vis[t]=i+n+1;
}
rep(i,0,n) {
pre[rt][i]=vis[pre[rt][i]]-1;
pre[rt][i+n]=vis[pre[rt][i+3*n]]-1;
}
}
void build(int l,int r,int rt) {
if(rt>mrt) mrt=rt;
if(l==r) {
cnt[rt]=n;
rep(i,0,n) pre[rt][i]=i;
rep(i,1,n) if(a[i][l]==a[i-1][l]) join(rt, i, i-1), --cnt[rt];
rep(i,0,n) pre[rt][i+n]=pre[rt][i];
return ;
}
int mid=l+r>>1;
build(l, mid, rt<<1);
build(mid+1, r, rt<<1|1);
up(rt, mid, rt<<1, rt<<1|1);
}
int qry(int L,int R,int l,int r,int rt) {
if(L<=l&&r<=R) return rt;
int mid=l+r>>1;
int ll=-1, rr=-1;
if(L<=mid) ll=qry(L,R,l,mid,rt<<1);
if(R>=mid+1) rr=qry(L,R,mid+1,r,rt<<1|1);
if(ll==-1) return rr;
if(rr==-1) return ll;
++cntn;
up(cntn,mid,ll,rr);
return cntn;
}
int main() {
while(~scanf("%d%d%d",&n,&m,&q)) {
///read
rep(i,0,n) rep(j,0,m) scanf("%d",&a[i][j]);
///solve
build(0, m-1, 1);
while(q--) {
int l,r;scanf("%d%d",&l,&r);
--l;--r;
cntn=mrt;
int p=qry(l,r,0,m-1,1);
printf("%d
",cnt[p]);
}
return 0;
}
return 0;
}
upd 代码
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define sz(a) (int)a.size()
#define de(a) cout << #a << " = " << a << endl
#define dd(a) cout << #a << " = " << a << " "
#define all(a) a.begin(), a.end()
#define endl "
"
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//---
const int N = 101010;
int n, m, q, top, ans, sz;
int a[11][N], pre[11*N], sta[11*N];
bool vis[11*N];
pii res[N];
inline void init() {
rep(i, 1, top+1) vis[sta[i]] = 0, pre[sta[i]] = sta[i];
top = ans = 0;
sz = 0;
}
inline void push(int x) {
vis[x] = 1;
sta[++top] = x;
}
int find(int x) {
if(x == pre[x]) return x;
if(!vis[x]) push(x);
return pre[x] = find(pre[x]);
}
struct Seg {
#define ls rt<<1
#define rs ls|1
static const int N = ::N << 2;
int cnt[N], id[N][22];
inline void init(int rt, int l) {
cnt[rt] = 0;
rep(i, 0, n) {
if(i == 0 || a[i][l] != a[i-1][l]) {
++cnt[rt];
id[rt][i] = i * m + l;
} else {
id[rt][i] = id[rt][i-1];
}
id[rt][i+n] = id[rt][i];
}
}
inline void up(int rt, int l, int r, int mid) {
cnt[rt] = cnt[ls] + cnt[rs];
rep(i, 0, n) if(a[i][mid] == a[i][mid+1]) {
int x = find(id[ls][i+n]), y = find(id[rs][i]);
if(x == y) continue;
pre[x] = y;
if(!vis[x]) push(x);
--cnt[rt];
}
rep(i, 0, n) {
id[rt][i] = find(id[ls][i]);
id[rt][i+n] = find(id[rs][i+n]);
}
}
void build(int l, int r, int rt) {
if(l == r) {
init(rt, l);
return ;
}
int mid = l + r >> 1;
build(l, mid, ls);
build(mid+1, r, rs);
up(rt, l, r, mid);
}
void qry(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
ans += cnt[rt];
res[sz++] = mp(l, rt);
res[sz++] = mp(r, rt);
return ;
}
int mid = l + r >> 1;
if(L <= mid) qry(L, R, l, mid, ls);
if(R >= mid+1) qry(L, R, mid+1, r, rs);
}
}seg;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin >> n >> m >> q;
rep(i, 0, n) rep(j, 0, m) cin >> a[i][j];
rep(i, 0, n*m) pre[i] = i;
seg.build(0, m-1, 1);
while(q--) {
int l, r;
cin >> l >> r;
--l, --r;
init();
seg.qry(l, r, 0, m-1, 1);
for(int t = 1; t < sz - 1; t += 2) {
int ll = res[t].se, rr = res[t+1].se, mid = res[t].fi;
rep(i, 0, n) if(a[i][mid] == a[i][mid+1]) {
int x = find(seg.id[ll][i+n]), y = find(seg.id[rr][i]);
if(x == y) continue;
pre[x] = y;
--ans;
if(!vis[x]) push(x);
}
}
cout << ans << endl;
}
return 0;
}