include long long amp else n) div 每一个 并查集
好题。
ST 表又叫做稀疏表,这里利用了他的性质。
显然每一个条件可以分成 n 个条件,显然过不了。
然后发现有许多状态是重复的,首先考虑线段树,没什么卵用。
然后 ST 表,可以每一层表示对应的区间大小的两个部分是否合并,如果合并就不向下递归。
然后可以剪去许多状态,变成了 $O(nlogn)$ 的。
- #include < cstdio > #include < cstring > #include < iostream > #include < algorithm >
- using namespace std;#define maxn 100005#define ll long long#define md 1000000007#define F(i, j, k) for (int i = j; i <= k; ++i)
- int f[maxn][21],
- n,
- m,
- l1,
- r1,
- l2,
- r2,
- lg[maxn];
- int gf(int a, int t) {
- if (f[a][t] == a) return a;
- else return f[a][t] = gf(f[a][t], t);
- }
- void merge(int a, int b, int t) {
- int fa = gf(a, t),
- fb = gf(b, t);
- if (fa == fb) return;
- f[fa][t] = fb;
- if (!t) return;
- merge(a, b, t - 1);
- merge(a + (1 << (t - 1)), b + (1 << (t - 1)), t - 1);
- }
- int main() {
- scanf("%d%d", &n, &m);
- F(i, 2, n) lg[i] = lg[i >> 1] + 1;
- F(i, 1, n) F(j, 0, lg[n]) f[i][j] = i;
- while (m--) {
- scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
- int tmp = lg[r1 - l1 + 1];
- merge(l1, l2, tmp);
- merge(r1 - (1 << tmp) + 1, r2 - (1 << tmp) + 1, tmp);
- }
- int cnt = 0,
- ans = 9;
- F(i, 1, n) if (f[i][0] == i) cnt++;
- cnt--;
- while (cnt--) {
- ans = (ll) ans * 10 % md;
- }
- printf("%d\n", ans);
- }
BZOJ 4569 [Scoi2016] 萌萌哒 ——ST 表 并查集
来源: http://www.bubuko.com/infodetail-2054537.html