题目传送门: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我是真心服 (:зゝ∠)
第一眼看上去,还以为只有主要的函数QAQ
再次 Orz
460815 138118Ich kenne einige Leute, die aus Kanadakommen. Eines Tages werde ich auch dorthin reisen Lg Daniela 118858
Hello! I just would like to give a huge thumbs up for the great info you have here on this post. I will be coming back to your blog for more soon.
394839 386647I believe that a simple and unassuming manner of life is finest for everyone, very best both for the body and the mind. 463164
4237 221692Fantastic post, thanks so significantly for sharing. Do you happen to have an RSS feed I can subscribe to? 462587
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
261556 307808You must participate in a contest for among the top blogs on the web. I will suggest this internet site! 567016
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
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
269744 46168There is noticeably a great deal of cash to understand about this. I assume youve made certain good points in attributes also. 815328
420107 105211You made some decent points there. I looked on the web for the difficulty and discovered most individuals will go coupled with along together with your website. 567674
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
429462 924224This website can be a walk-through its the details you wanted concerning this and didnt know who to ask. Glimpse here, and youll undoubtedly discover it. 722323
402478 707804When I came over to this post I can only appear at part of it, is this my net browser or the internet site? Ought to I reboot? 726698
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.