OID天下第一 （双指针，LCT，线段树）
题面
或曰：“笑长天下第一！”，OID 喜得合不拢嘴：“哈哈哈哈哈哈……”
OneInDark 是天下第一的。
OneInDark 给了你一个
n
n
n 个点
m
m
m 条边的无向图（无重边自环），点标号为
1
∼
n
1 ∼ n
1∼n。祂想要考考你，有多少对整数对
(
l
,
r
)
(l, r)
(l,r) 满足：
1
≤
l
≤
r
≤
n
1 ≤ l ≤ r ≤ n
1≤l≤r≤n
如果把区间
[
l
,
r
]
[l, r]
[l,r] 内的点以及它们之间的边保留下来，其他的点和边都扔掉，那么留下来的这张图恰好是一条链。
注：链必须是连通的图。特别地，一个点的图也是链。
n
,
m
≤
2.5
×
1
0
5
n,m\leq 2.5\times10^5
n,m≤2.5×105
题解
既然它是一条链，就没有度数大于 2 的点，同时又无环。
如果无环，那么就是森林（重点：一棵树也是森林），森林成为连通图只需要满足一个条件：点数-边数=1。同时由于森林满足 点数-边数 ≥ 1，所以该条件等价于(点数-边数)取得最小值 1 。
于是，我们认定链要(先后)满足三个条件：
- 每个点的度数不超过 2（读书超过 2 的点个数为 0）。
- 无环。
- (点数 - 边数) 取得最小值 1 。
如果固定区间右端点
R
R
R，我们会发现只满足前两个条件的区间左端点
L
L
L 是连续的，从某个位置一直到
R
R
R。同时若区间
[
L
,
R
]
[L,R]
[L,R] 满足前两个条件，那么区间
[
L
,
R
−
1
]
[L,R-1]
[L,R−1] （如果非空的话）也一定满足前两个条件。所以我们用双指针（曰Two Pointers，曰尺取(?)……）配合LCT（判断环），求出对于每个右端点的最远合法——仅对前两个条件合法——的左端点。
这时候要满足第三个条件，就很简单了。我们用线段树，维护左端点在每个位置时的(点数-边数)最小值及其个数。
时间复杂度
O
(
(
n
+
m
)
log
n
)
O((n+m)\log n)
O((n+m)logn) 。
CODE
做 LCT 要谨记一点：平衡树上凡是访问过的链，都得Splay旋到根，相当于对Splay进行一次“训练”，不然复杂度不对。
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 250005
#define LL long long
#define ULL unsigned long long
#define UI unsigned int
#define DB double
#define ENDL putchar('\n')
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define eps (1e-4)
#define BI bitset<1002>
#pragma GCC optimize(2)
LL read() {
LL f=1,x=0;char s = getchar();
while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f*x;
}
void putpos(LL x) {
if(!x) return ;
putpos(x/10); putchar('0'+(x%10));
}
void putnum(LL x) {
if(!x) putchar('0');
else if(x < 0) putchar('-'),putpos(-x);
else putpos(x);
}
void AIput(LL x,char c) {putnum(x);putchar(c);}
int n,m,s,o,k;
// -------------------------------------START >>>
struct tr{
int s[2],fa,lz;
tr(){s[0]=s[1]=fa=lz=0;}
}tre[MAXN];
int isroot(int x) {return tre[tre[x].fa].s[0] != x && tre[tre[x].fa].s[1] != x;}
int whichson(int x) {return tre[tre[x].fa].s[1] == x;}
int update(int x) {
if(!x) return x;
tre[tre[x].s[0]].fa = tre[tre[x].s[1]].fa = x;
tre[0].fa = 0;
return x;
}
void pushdown(int x) {
if(tre[x].lz) {
swap(tre[x].s[0],tre[x].s[1]);
tre[tre[x].s[0]].lz ^= 1;
tre[tre[x].s[1]].lz ^= 1;
tre[x].lz = 0;
}return ;
}
void rotat(int x) {
int y = tre[x].fa,z = tre[y].fa;
int d = whichson(x),d2 = whichson(y),d3 = isroot(y);
tre[y].s[d] = tre[x].s[d^1];
tre[x].s[d^1] = y; tre[x].fa = z;
tre[tre[y].s[d]].fa = y; tre[y].fa = x;
if(!d3) tre[z].s[d2] = x; tre[0].fa = 0;
return ;
}
void pushup(int x) {
static int st[MAXN],tp;
st[tp = 1] = x;
while(!isroot(x)) st[++ tp] = tre[x].fa,x = tre[x].fa;
while(tp > 0) pushdown(st[tp --]);
return ;
}
int splay(int x) {
pushup(x);
while(!isroot(x)) {
int y = tre[x].fa;
if(!isroot(y) && whichson(x) == whichson(y)) rotat(y);
rotat(x);
}return x;
}
// ---------------------------SPLAY
int Access(int x) {
int p = 0,xx = x;
while(x) {
splay(x);
tre[x].s[1] = p;
p = update(x);
x = tre[x].fa;
}return splay(xx);
}
void Makeroot(int x) {Access(x);tre[x].lz ^= 1;}
int Findroot(int x) {Access(x);while(tre[x].s[0])x=tre[x].s[0];return splay(x);}
void Cut(int x,int y) {Makeroot(x);Access(y);tre[y].s[0]=tre[x].fa=0;update(y);}
void Link(int x,int y) {Makeroot(x);tre[x].fa = y;return ;}
// ---------------------------LCT
int hd[MAXN],v[MAXN<<1],nx[MAXN<<1],cne;
int ind[MAXN],cnd;
map<int,bool> mp[MAXN];
void ins(int x,int y) {
nx[++ cne] = hd[x]; v[cne] = y; hd[x] = cne;
}
void del(int x) {
for(int i = hd[x];i;i = nx[i]) {
if(mp[min(x,v[i])][max(x,v[i])]) {
Cut(x,v[i]);
mp[min(x,v[i])][max(x,v[i])] = 0;
ind[x] --; ind[v[i]] --;
if(ind[x] == 2) cnd --;
if(ind[v[i]] == 2) cnd --;
}
}return ;
}
int pl[MAXN];
struct it{
int nm,ct;
it(){nm=0x3f3f3f3f;ct=0;}
}tr[MAXN<<2];
int lz[MAXN<<2],M;
it merg(it a,it b) {
if(a.nm > b.nm) swap(a,b);
if(a.nm == b.nm) a.ct += b.ct;
return a;
}
it operator + (it a,int b) {a.nm += b; return a;}
void maketree(int n) {
M=1;while(M<n+2)M<<=1;
for(int i = 1;i <= n;i ++) {
tr[M+i].nm = 0;tr[M+i].ct = 1;
}
for(int i = M-1;i > 0;i --) {
tr[i] = merg(tr[i<<1],tr[i<<1|1]);
}return ;
}
void addtree(int l,int r,int y) {
int s = M+l-1,t = M+r+1;
while(s || t) {
if(s<M) tr[s] = merg(tr[s<<1],tr[s<<1|1]) + lz[s];
if(t<M) tr[t] = merg(tr[t<<1],tr[t<<1|1]) + lz[t];
if((s>>1) ^ (t>>1)) {
if(!(s&1)) tr[s^1]=tr[s^1]+y,lz[s^1]+=y;
if(t & 1) tr[t^1]=tr[t^1]+y,lz[t^1]+=y;
}s >>= 1;t >>= 1;
}return ;
}
it findtree(int l,int r) {
it ls = it(),rs = it();
if(l > r) return ls;
int s = M+l-1,t = M+r+1;
while(s || t) {
ls = ls + lz[s];
rs = rs + lz[t];
if((s>>1) ^ (t>>1)) {
if(!(s&1)) ls = merg(ls,tr[s^1]);
if(t & 1) rs = merg(rs,tr[t^1]);
}s >>= 1;t >>= 1;
}return merg(ls,rs);
}
int main() {
freopen("txdy.in","r",stdin);
freopen("txdy.out","w",stdout);
n = read();m = read();
for(int i = 1;i <= m;i ++) {
s = read();o = read();
ins(s,o); ins(o,s);
}
int st = 1;
maketree(n);
LL ans = 0;
for(int i = 1;i <= n;i ++) {
addtree(1,i,1);
for(int j = hd[i];j;j = nx[j]) {
s = i; o = v[j];
while(o >= st && o <= i && Findroot(o) == Findroot(s)) {
del(st ++);
}
if(o >= st && o <= i) {
Link(s,o);
mp[min(s,o)][max(s,o)] = 1;
ind[s] ++; ind[o] ++;
if(ind[s] == 3) cnd ++;
if(ind[o] == 3) cnd ++;
}
if(v[j] < i) {
addtree(1,v[j],-1);
}
}
while(cnd > 0) del(st ++);
pl[i] = st;
it as = findtree(pl[i],i);
if(as.nm == 1) ans += as.ct;
}
AIput(ans,'\n');
return 0;
}手机扫一扫
移动阅读更方便
你可能感兴趣的文章