数据结构 - cool's Blog
[莫队算法]
最近又看了一下莫队，发现我以前完全理解错了莫队算法。
[分块]bzoj4537
4537: [Hnoi2016]最小公倍数
Time Limit: 40 Sec Memory Limit: 512 MBSubmit: 592 Solved: 251
[Submit][Status][Discuss]
Description
给定一张N个顶点M条边的无向图(顶点编号为1,2,…,n)，每条边上带有权值。所有权值都可以分解成2^a*3^b
的形式。现在有q个询问，每次询问给定四个参数u、v、a和b，请你求出是否存在一条顶点u到v之间的路径，使得
路径依次经过的边上的权值的最小公倍数为2^a*3^b。注意：路径可以不是简单路径。下面是一些可能有用的定义
：最小公倍数：K个数a1,a2,…,ak的最小公倍数是能被每个ai整除的最小正整数。路径：路径P:P1,P2,…,Pk是顶
点序列，满足对于任意1<=i<k，节点Pi和Pi+1之间都有边相连。简单路径：如果路径P:P1,P2,…,Pk中，对于任意1
<=s≠t<=k都有Ps≠Pt，那么称路径为简单路径。
Input
输入文件的第一行包含两个整数N和M，分别代表图的顶点数和边数。接下来M行，每行包含四个整数u、v、a、
b代表一条顶点u和v之间、权值为2^a*3^b的边。接下来一行包含一个整数q，代表询问数。接下来q行，每行包含四
个整数u、v、a和b，代表一次询问。询问内容请参见问题描述。1<=n,q<=50000、1<=m<=100000、0<=a,b<=10^9
Output
对于每次询问，如果存在满足条件的路径，则输出一行Yes，否则输出一行 No（注意：第一个字母大写，其余
字母小写） 。
Sample Input
1 2 1 3
1 3 1 2
1 4 2 1
2 4 3 2
3 4 2 2
5
1 4 3 3
4 2 2 3
1 3 2 2
2 3 2 2
1 3 4 4
Sample Output
Yes
Yes
No
No
HINT
[分块]bzoj2002
一直听主力讲分块大法好，xllend3似乎证明莫队都可以用分块做！（%一发）
一开始看到标签写着Splay 启发式合并感觉很厉害的样子，然后发现分块可以操！
思路：把N个蹦床分成sqrt(n）块，然后在每块里记录这个点飞出这个块要的步数和会飞到哪个点。
修改：把这个块里的点都重新算一遍，O（n^0.5)
询问：显然O（n^0.5）
#include <cstdio>
#include <cmath>
using namespace std;
#define maxn 200010
#define INF 0x7f7f7f7f
int a[maxn],p[maxn],num[maxn],size;
int LG(int x)//询问X属于哪个块
{
return (x-1)/size+1;
}
int head(int x)//询问第x块的头
{
return (x-1)*size+1;
}
int main()
{
int n;
scanf("%d",&n);
for (int i = 1;i <= n;i++)
scanf("%d",&a[i]);
size = sqrt(n);
if (size*size < n) size++;
for (int i = n;i >= 1;i--)
{
if (i+a[i] > n)
p[i] = INF,num[i] = 1;
else if (LG(i+a[i])!=LG(i))
p[i] = i+a[i],num[i] = 1;
else p[i] = p[i+a[i]],num[i] = 1+num[i+a[i]];
}
int q;
scanf("%d",&q);
for (;q--;)
{
int x;
scanf("%d",&x);
if (x == 1)
{
int y,ans = 0;
scanf("%d",&y);
for (y++;y < INF;y = p[y])ans += num[y];
printf("%d\n",ans);
}
else
{
int y,z;
scanf("%d%d",&y,&z);
a[++y] = z;
int t = head(LG(y));
for (;y >= t;y--)
{
if (y+a[y] > n)
p[y] = INF,num[y] = 1;
else if (LG(y+a[y])!=LG(y))
p[y] = y+a[y],num[y] = 1;
else p[y] = p[y+a[y]],num[y] = 1+num[y+a[y]];
}
}
}
return 0;
}
【并查集】bzoj1015
每次删边显然十分复杂，所谓正难则反（= = 数学思路？）
只要把摧毁的建筑倒着加入并查集就行了
每次合并，连通块就会减1，但总的连通块要减去那些还未加入的星球（= = 貌似说不清楚）
直接上代码。
#include <cstdio>
#define maxm 200001
#define maxn 400001
int b[maxn],f[maxn],d[maxn],c[maxn],h[maxn],last[maxn],head[maxn],l;
void add(int x,int y)
{
l++;
h[l] = y;
last[l] = head[x];
head[x] = l;
}
int find(int x)
{
if (f[x] == x) return x;
return f[x] = find(f[x]);
}
void read(int &i)
{
char x;
for (x = getchar();x < '0';x = getchar());
for (i = 0;x >= '0';x = getchar()) i = i * 10 + x - '0';
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for (int i = 1;i <= m;i++)
{
int x,y;
read(x);read(y);
add(++x,++y);
add(y,x);
}
int q;
read(q);
for (int i = 1;i <= n;i++)
b[i] = 1,f[i] = i;
for (int i = 1;i <= q;i++)
{
read(d[i]);
b[++d[i]] = 0;
}
int t = q;\\t就是还没加入的星球个数
int sum = n;
for (int i = 1;i <= n;i++)
if (b[i] == 1)
{
for (int x = head[i];x;x = last[x])
if (b[h[x]] == 1)
{
int r1 = find(i),r2 = find(h[x]);
if (r1 != r2)
{
f[r1] = r2;
sum--;
}
}
}
for (int i = q;i >= 1;i--)
{
c[i] = sum - t;
b[d[i]] = 1;
for (int x = head[d[i]];x;x = last[x])
if (b[h[x]] == 1)
{
int r1 = find(d[i]),r2 = find(h[x]);
if (r1 != r2)
{
f[r1] = r2;
sum--;
}
}
t--;
}
printf("%d\n",sum-t);
for (int i = 1;i <= q;i++)
printf("%d\n",c[i]);
return 0;
}
【倍增LCA】 NOIP2013 T3货车运输
人生第一道A掉的提高组T3= =
倍增+LCA 就能轻松AC了
但lbn大神让我去学树剖LCA 而我连树剖都不会 结果被大D一通