成都网站建设推广,怎么做营销型网站,都市网,怎样做商城网站天下第一 txdydescriptionsolutioncodedescription
djq_cpp 是天下第一的。 djq_cpp 给了你一个 n 个点 m 条边的无向图#xff08;无重边自环#xff09;#xff0c;点标号为 1 ∼n。祂想要考考你#xff0c; 有多少对整数对 (l, r) 满足#xff1a; • 1 ≤l ≤r ≤n •…
天下第一 txdydescriptionsolutioncodedescription
djq_cpp 是天下第一的。 djq_cpp 给了你一个 n 个点 m 条边的无向图无重边自环点标号为 1 ∼n。祂想要考考你 有多少对整数对 (l, r) 满足 • 1 ≤l ≤r ≤n • 如果把区间 [l, r] 内的点以及它们之间的边保留下来其他的点和边都扔掉那么留下来的这张 图恰好是一条链。 注链必须是连通的图。特别地一个点的图也是链。
Input 第一行两个非负整数 n, m。 接下来 m 行每行两个正整数 u, v(1 ≤u, v ≤n, u ̸ v)表示 u, v 之间有一条边。 保证图无重边自环。
Output 输出一个整数表示答案。
Sample Input 3 3 1 2 2 3 3 1 Output 5 Explanation (1, 1), (1, 2), (2, 2), (2, 3), (3, 3) 是符合条件的整数对。
Constraint 对于 10% 的数据n, m ≤100。 对于 20% 的数据n, m ≤1000。 对于 60% 的数据n, m ≤50000。 对于另外 10% 的数据保证每个点度数 ≤2。 对于 100% 的数据1 ≤n ≤250000, 0 ≤m ≤250000。
solution
首先清楚为链的必要条件
点数减边数111无环每个点度数≤2\le 2≤2
正解就是寻找辅助工具来判断点[l,r][l,r][l,r]内的所有边是否满足上面所有条件
实际上三个条件可以分开保证后再合并
双指针法
考虑枚举点区间的右端点rrr
然后找到满足[l,r][l,r][l,r]内每个点度数都≤2\le 2≤2的最小的lll记为f[r]f[r]f[r]
显然随着rrr的右移lll只会变大不会变小
具体而言利用度数did_idi每次右端点111后加入新右端点连接的所有在[l,r1][l,r1][l,r1]的边并判断边连接两点是否度数超过222如果超过就选择右移左端点断掉原来左端点的所有已连边直到度数不超过222才停止左端点右移
同理双指针法
考虑枚举右端点rrr
然后找到满足[l,r][l,r][l,r]内所有边加入后无环的最小的lll记为g[r]g[r]g[r]
显然随着rrr的右移lll只会变大不会变小
具体而言与维护度数本质上是完全一样的但是这里涉及到了边的动态变化那就不得不使用动态树LCT\text{LCT}LCT了判断新右端点的边连接的两个点原本已经连接这条边加入就会形成环右移左端点断掉原来左端点的所有已连边。这些完完全全就是LCT\text{LCT}LCT的模板专场了
为了满足以上两个条件则真正的左端点是lmax(g[r],f[r])l\max(g[r],f[r])lmax(g[r],f[r])
最后就是必须是同一条链的连通性问题
要求点数减边数111就可以用线段树维护点数减边数最小值再记录最小值的个数
具体而言对于每一个右端点rrr线段树叶子结点lll表示的意思是[l,r][l,r][l,r]区间内所有边都加入后点数减边数的最小值。写法上是将线段树与无环的判断放在一起写的
考场上硬刚LCT的人真的是强者
code
#include bits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 250005
int n, m, top, sta[maxn], pos[maxn], deg[maxn];
vector int G[maxn];namespace LCT {struct node { int son[2], fa, tag; }t[maxn];bool root( int x ) { return t[t[x].fa].son[0] ^ x and t[t[x].fa].son[1] ^ x; }void reverse( int x ) { swap( t[x].son[0], t[x].son[1] ); t[x].tag ^ 1; }void pushdown( int x ) {if( ! t[x].tag ) return;if( t[x].son[0] ) reverse( t[x].son[0] );if( t[x].son[1] ) reverse( t[x].son[1] );t[x].tag ^ 1;}void rotate( int x ) {int fa t[x].fa;int Gfa t[fa].fa;int d t[fa].son[1] x;if( ! root( fa ) ) t[Gfa].son[t[Gfa].son[1] fa] x;t[x].fa Gfa;if( t[x].son[d ^ 1] ) t[t[x].son[d ^ 1]].fa fa;t[fa].son[d] t[x].son[d ^ 1];t[x].son[d ^ 1] fa;t[fa].fa x;}void splay( int x ) {sta[ top] x; int y x;while( ! root( y ) ) sta[ top] y t[y].fa;while( top ) pushdown( sta[top --] );while( ! root( x ) ) {int fa t[x].fa, Gfa t[fa].fa;if( ! root( fa ) ) (t[Gfa].son[0] fa) ^ (t[fa].son[0] x) ? rotate( x ) : rotate( fa );rotate( x ); }}void access( int x ) { for( int son 0;x;son x, x t[x].fa ) splay( x ), t[x].son[1] son; }void makeroot( int x ) { access( x ); splay( x ); reverse( x ); }void split( int x, int y ) { makeroot( x ); access( y ); splay( y ); }void link( int x, int y ) { makeroot( x ); t[x].fa y; }void cut( int x, int y ) { split( x, y ); t[x].fa t[y].son[0] 0; }int findroot( int x ) { access( x ); splay( x ); while( t[x].son[0] ) pushdown( x ), x t[x].son[0]; splay( x ); return x; }bool check( int x, int y ) { makeroot( x ); return findroot( y ) x; }
}struct node { int ans, cnt, tag; }t[maxn 2];
namespace SGT {#define lson now 1#define rson now 1 | 1#define mid (l r 1)node operator ( node x, node y ) {if( x.ans y.ans ) return x;else if( x.ans y.ans ) return y;else { x.cnt y.cnt; return x; }}void pushdown( int now ) {if( ! t[now].tag ) return;t[lson].ans t[now].tag;t[lson].tag t[now].tag;t[rson].ans t[now].tag;t[rson].tag t[now].tag;t[now].tag 0;}void build( int now, int l, int r ) {t[now] { 0, 1, 0 };if( l r ) return;build( lson, l, mid );build( rson, mid 1, r );t[now] t[lson] t[rson];}void modify( int now, int l, int r, int L, int R, int v ) {if( R l or r L ) return;if( L l and r R ) { t[now].ans v; t[now].tag v; return; }pushdown( now );modify( lson, l, mid, L, R, v );modify( rson, mid 1, r, L, R, v );t[now] t[lson] t[rson]; t[now].tag 0; //因为重载的写法问题 t[now]t[lson]/t[rson] 会把儿子的懒标记也赋过来 但实际上now这里是不该存在懒标记的}node query( int now, int l, int r, int L, int R ) { if( r L or R l ) return { inf, 0, 0 };if( L l and r R ) return t[now];pushdown( now );return query( lson, l, mid, L, R ) query( rson, mid 1, r, L, R );}
}int main() {scanf( %d %d, n, m );for( int i 1, u, v;i m;i ) {scanf( %d %d, u, v );G[u].push_back( v );G[v].push_back( u );}for( int r 1, l 1;r n;r ) {//枚举位置r作为右端点 //双指针l求出最远的满足度数2的条件sort( G[r].begin(), G[r].end() );for( int i : G[r] ) { //把每条r相连的属于[l,r]的边加进来 if( i r ) break;while( l i and ( deg[i] 2 or deg[r] 2 ) ) {//在加这条边之前 两点度数就已经等于2 加了过后肯定不满足度数2的条件//这个时候说明l左端点应当右移//知道两点度数都2为止 for( int j : G[l] )if( l j and ( j r or ( j r and l i ) ) )deg[l] --, deg[j] --;l ;}if( l i ) deg[i] , deg[r] ;//这条边还在调整后新区间内[l,r]内才真的加入}pos[r] l;}SGT :: build( 1, 1, n );long long ans 0;for( int r 1, l 1;r n;r ) {SGT :: modify( 1, 1, n, 1, r, 1 );for( int i : G[r] ) {if( i r ) break;while( l i and LCT :: check( i, r ) ) {for( int j : G[l] )if( l j and ( j r or ( j r and l i ) ) )LCT :: cut( l, j );/*不能写成if(lj and j r) 上面同理因为新加一条边是i-r有可能i就恰好是l发现i和r已经联通就必须去除掉l连接的边l里面就会访问到l-r这条边 但是这里还没有加错误写法就会删去一条根本没加过的边导致错误 */l ;}if( l i ) LCT :: link( i, r );SGT :: modify( 1, 1, n, 1, i, -1 );}pos[r] max( pos[r], l );node now SGT :: query( 1, 1, n, pos[r], r );if( now.ans 1 ) ans now.cnt;}printf( %lld\n, ans );return 0;
}
