【BZOJ 4569】[SCOI2016] 萌萌哒

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4569

这题,出题人是怎么想到的QAQ
真心服 Orz

考虑网络流的区间建边的方法:先搞出一个像线段树的玩意
然而这个题目没办法了,因为线段树的区间拆分是不规则的,对不上 QAQ
于是考虑ST表,用ST表来搞一搞,其实是用来去掉区间合并中的重复部分

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;
const int MOD = 1000000007;

int n,m,fa[18][N],vout=1;

inline int find(int p, int w) {
	int f = fa[p][w], tmp;
	while (f != fa[p][f]) f = fa[p][f];
	while (w != f) tmp = fa[p][w], fa[p][w] = f, w = tmp;
	return f;
} 

inline int read(){
	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;
}

void merge(int t, int a, int b){
	int t1 = find(t,a), t2 = find(t, b);
	if (t1 == t2) return; fa[t][t1] = t2;
	if (!t) return; t--, merge(t,a,b), merge(t,a+(1<<t),b+(1<<t));
}

int main(){
	n = read(); m = read(); if (n == 1) return puts("10"), 0;
	for (int j=0;j<=17;j++) for (int i=1;i<=n;i++) fa[j][i] = i;
	for (int i=1,a,b,c,d,stp;i<=m;i++) 
		a = read(), b = read(), c = read(), d = read(), stp = 31 - __builtin_clz(b-a+1),
		merge(stp,a,c), merge(stp,b-(1<<stp)+1,d-(1<<stp)+1);
	for (int i=1,tag=1;i<=n;i++) if (find(0,i) == i) vout = vout*(tag?9LL:10LL) % MOD, tag = 0;
	return printf("%d\n",vout), 0; 
}

另外说到压代码这个事,Claris我是真心服 (:зゝ∠)
545646454
第一眼看上去,还以为只有主要的函数QAQ
再次 Orz

14 thoughts to “【BZOJ 4569】[SCOI2016] 萌萌哒”

  1. 922333 73361Hello! Someone in my Facebook group shared this internet site with us so I came to appear it more than. Im definitely enjoying the information. Im book-marking and is going to be tweeting this to my followers! Outstanding blog and superb style and style. 486489

  2. 255049 388143Pretty section of content. I just stumbled upon your internet site and in accession capital to assert that I get in fact enjoyed account your blog posts. Any way Ill be subscribing to your feeds and even I achievement you access consistently quick. 714922

  3. 201108 762189This sort of in search of get the enhancements made on this particular lifestyle and diet, begin your L . a . Shifting the pounds diet solution is really a huge procedure into accesing which normally hope. weight loss 142429

  4. 269744 46168There is noticeably a great deal of cash to understand about this. I assume youve made certain good points in attributes also. 815328

  5. 1412 429651Spot on with this write-up, I actually suppose this web site needs considerably much more consideration. probably be once more to learn way more, thanks for that information. 790250

  6. You completed various fine points there. I did a search on the subject matter and found a good number of people will have the same opinion with your blog.

Leave a Reply

Your email address will not be published. Required fields are marked *