传送门!
最近考试考到了一道类似的题然后就想起这道回来看下,发现题解写得奇奇怪怪的我我我重构下$QwQ$
首先不难想到暴力?就考虑把区间相等转化成对应点对相等,然后直接对应点连边,最后求有几个连通块就好辣
然后看下复杂度,修改是$O(n^2)$查询是$O(n)$,就比较容易想到能不能通过一些技巧变成都是$O(nlogn)$的,结合数据范围发现$nlogn$的复杂度似乎是对的,于是就往这个方面想呗.就不难想到倍增和线段树.
考虑倍增,设$f_{i,j}$表示$[i,i&＃43;2^j-1]$这一段区间的信息.然后每次赋值操作就可以二进制拆分成$log$个区间,然后直接赋值$f_{l_1,j}&＃61;f_{l_2,j}$.
最后回答询问的时候把所有相等关系下放下去,就$f_{i,j}&＃61;f_{i,j&＃43;1},f_{i,i&＃43;2^{j-1}}&＃61;f_{i,j&＃43;1}$.
最后统计下联通块个数$cnt$,答案就$10^{cnt}$.
其实是有点类似线段树的$lazy\_tag$操作的$QwQ$
#include
using namespace std;
#define il inline
#define ll long long
#define rg register
#define gc getchar()
#define rp(i,x,y) for(rg int i&＃61;x;i<&＃61;y;&＃43;&＃43;i)
#define my(i,x,y) for(rg int i&＃61;x;i>&＃61;y;--i)
const int N&＃61;1e5&＃43;10,mod&＃61;1e9&＃43;7;
int n,m,f[N][20],poww[20],cnt;
ll as&＃61;9;
il int read()
{
rg char ch&＃61;gc;rg int x&＃61;0;rg bool y&＃61;1;
while(ch!&＃61;&＃39;-&＃39; && (ch>&＃39;9&＃39; || ch<&＃39;0&＃39;))ch&＃61;gc;
if(ch&＃61;&＃61;&＃39;-&＃39;)ch&＃61;gc,y&＃61;0;
while(ch>&＃61;&＃39;0&＃39; && ch<&＃61;&＃39;9&＃39;)x&＃61;(x<<1)&＃43;(x<<3)&＃43;(ch^&＃39;0&＃39;),ch&＃61;gc;
return y?x:-x;
}
il void pre(){poww[0]&＃61;1;rp(i,1,19)poww[i]&＃61;poww[i-1]<<1;rp(i,1,n)rp(j,0,20)f[i][j]&＃61;i;}
int fd(int x,int lth){return f[x][lth]&＃61;&＃61;x?x:f[x][lth]&＃61;fd(f[x][lth],lth);}
il void merg(int x,int y,int lth){int fax&＃61;fd(x,lth),fay&＃61;fd(y,lth);if(fax!&＃61;fay)f[fax][lth]&＃61;fay;}
int main()
{
// freopen("mmd.in","r",stdin);freopen("mmd.out","w",stdout);
n&＃61;read();m&＃61;read();pre();
while(m--){int l1&＃61;read(),r1&＃61;read(),l2&＃61;read(),r2&＃61;read();my(i,19,0)if(l1&＃43;poww[i]-1<&＃61;r1)merg(l1,l2,i),l1&＃43;&＃61;poww[i],l2&＃43;&＃61;poww[i];}
my(j,19,1)rp(i,1,n-poww[j]&＃43;1)merg(i,fd(i,j),j-1),merg(i&＃43;poww[j-1],fd(i,j)&＃43;poww[j-1],j-1);
rp(i,1,n)if(fd(i,0)&＃61;&＃61;i)&＃43;&＃43;cnt;rp(i,1,cnt-1)as&＃61;as*10,as%&＃61;mod;
printf("%lld\n",as);
return 0;
}
京公网安备 11010802041100号