## 【BZOJ 3237】[AHOI2013] 连通图

### Code

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 100000+9;
const int M = 1000000+9;
const int SGZ = 5;

int u[M],v[M],is_del[M],vout[N],idx;
int fa[N],n,m,k,sz[N],edg[N][SGZ];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

namespace Union_Find_Set{
#define UFS Union_Find_Set
int t1[M*5],t2[M*5],cnt;

inline int find(int w){
int f = fa[w], tmp;
while (fa[f] != f) f = fa[f];
while (w != f) t1[++cnt] = w, t2[cnt] = fa[w], fa[w] = f, w = t2[cnt];
return f;
}

inline void Union(int a, int b) {
int f1 = find(a), f2 = find(b);
if (f1 != f2) ++cnt, fa[t1[cnt]=t2[cnt]=f1] = f2;
}

inline void reset(int Tag) {
for (;cnt>Tag;cnt--)
fa[t1[cnt]] = t2[cnt];
}
};

void solve(int l, int r){
int cur_time = UFS::cnt;
if (l == r) {
vout[l] = 1;
for (int i=1,w;i<=sz[l] && vout[l];i++) {
w = edg[l][i];
if (UFS::find(u[w]) != UFS::find(v[w])) vout[l] = 0;
}
UFS::reset(cur_time);
} else {
int mid = l + r + 1 >> 1; ++idx;
for (int i=mid;i<=r;i++) for (int j=1;j<=sz[i];j++) is_del[edg[i][j]] = idx;
for (int i=l;i<mid;i++) for (int j=1,w;j<=sz[i];j++) {
w = edg[i][j];
if (is_del[w] != idx) UFS::Union(u[w],v[w]);
}
solve(mid,r);
UFS::reset(cur_time); ++idx;
for (int i=l;i<mid;i++) for (int j=1;j<=sz[i];j++) is_del[edg[i][j]] = idx;
for (int i=mid;i<=r;i++) for (int j=1,w;j<=sz[i];j++) {
w = edg[i][j];
if (is_del[w] != idx) UFS::Union(u[w],v[w]);
}
solve(l,mid-1);
UFS::reset(cur_time);
}
}

int main(){
for (int i=1;i<=n;i++) fa[i] = i;
for (int i=1;i<=k;i++) {
for (int j=sz[i];j;--j)
}
for (int i=1;i<=m;i++) if (~is_del[i]) UFS::Union(u[i],v[i]);
solve(1,k);
for (int i=1;i<=k;i++) puts(vout[i]?"Connected":"Disconnected");
return 0;
}


—————————— UPD 2017.2.1 ——————————

## 【BZOJ 2738】矩阵乘法

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 500+9;
const int M = 250000+9;
const int Q = 60000+9;

struct Point{int val,x,y;inline bool operator < (const Point &B) const {return val < B.val;}}p[M];
struct Query{int k,x1,x2,y1,y2,id;}q[Q],buf[Q];

int n,m,vout[Q];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

namespace Fenwick_Tree{
#define BIT Fenwick_Tree
#define lowbit(x) ((x)&-(x))
int sum[N][N];

inline void modify(int x, int y, int delta) {
if (x <= 0 || y <= 0) return;
for (int j=y;j<=n;j+=lowbit(j)) for (int i=x;i<=n;i+=lowbit(i))
sum[i][j] += delta;
}

inline int query(int x, int y){
if (x <= 0 || y <= 0) return 0;
int ret = 0;
for (int j=y;j;j-=lowbit(j)) for (int i=x;i;i-=lowbit(i))
ret += sum[i][j];
return ret;
}
};

void solve(int l, int r, int L, int R) {
if (l == r) for (int i=L;i<=R;i++) vout[q[i].id] = p[l].val;
else {
int mid = l + r + 1 >> 1,ls=L-1,rs=R+1;
for (int i=l;i<=mid-1;i++) BIT::modify(p[i].x,p[i].y,1);
for (int i=L,tmp;i<=R;i++) {
tmp = BIT::query(q[i].x1-1,q[i].y1-1);
tmp += BIT::query(q[i].x2,q[i].y2);
tmp -= BIT::query(q[i].x1-1,q[i].y2);
tmp -= BIT::query(q[i].x2,q[i].y1-1);
if (tmp >= q[i].k) buf[++ls] = q[i];
else q[i].k -= tmp, buf[--rs] = q[i];
}
memcpy(q+L,buf+L,sizeof(buf[0])*(R-L+1));
for (int i=l;i<=mid-1;i++) BIT::modify(p[i].x,p[i].y,-1);
if (L <= ls) solve(l,mid-1,L,ls);
if (rs <= R) solve(mid,r,rs,R);
}
}

int main(){