[题目链接]

https://www.lydsy.com/JudgeOnline/problem.php?id=2002

[算法]

LCT动态维护森林连通性

时间复杂度 : O(NlogN ^ 2)

[代码]

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + ;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull; int n;
int k[MAXN]; struct Link_Cut_Tree
{
struct Node
{
int father , son[] , size;
bool tag;
} a[MAXN];
inline void init()
{
for (int i = ; i <= n; i++)
{
a[i].father = ;
a[i].son[] = a[i].son[] = ;
a[i].size = ;
a[i].tag = false;
}
}
inline void pushdown(int x)
{
if (a[x].tag)
{
swap(a[x].son[] , a[x].son[]);
a[a[x].son[]].tag ^= ;
a[a[x].son[]].tag ^= ;
a[x].tag = false;
}
}
inline void update(int x)
{
a[x].size = ;
if (a[x].son[]) a[x].size += a[a[x].son[]].size;
if (a[x].son[]) a[x].size += a[a[x].son[]].size;
}
inline bool get(int x)
{
pushdown(a[x].father);
return a[a[x].father].son[] == x;
}
inline bool nroot(int x)
{
return a[a[x].father].son[] == x | a[a[x].father].son[] == x;
}
inline void rotate(int x)
{
int f = a[x].father , g = a[f].father;
int tmpx = get(x) , tmpf = get(f);
int w = a[x].son[tmpx ^ ];
if (nroot(f)) a[g].son[tmpf] = x;
a[x].son[tmpx ^ ] = f;
a[f].son[tmpx] = w;
if (w) a[w].father = f;
a[f].father = x;
a[x].father = g;
update(f);
}
inline void access(int x)
{
for (int y = ; x; x = a[y = x].father)
{
splay(x);
a[x].son[] = y;
update(x);
}
}
inline void splay(int x)
{
int y = x , z = ;
static int st[MAXN];
st[++z] = y;
while (nroot(y)) st[++z] = y = a[y].father;
while (z) pushdown(st[z--]);
while (nroot(x))
{
int y = a[x].father , z = a[y].father;
if (nroot(y))
rotate((a[y].son[] == x) ^ (a[z].son[] == y) ? x : y);
rotate(x);
}
update(x);
}
inline void make_root(int x)
{
access(x);
splay(x);
a[x].tag ^= ;
pushdown(x);
}
inline int find_root(int x)
{
access(x);
splay(x);
while (a[x].son[])
{
pushdown(x);
x = a[x].son[];
}
return x;
}
inline void link(int x , int y)
{
make_root(x);
if (find_root(y) != x) a[x].father = y;
}
inline void cut(int x , int y)
{
make_root(x);
if (find_root(y) == x && a[x].father == y && !a[x].son[])
{
a[x].father = a[y].son[] = ;
update(y);
}
}
inline int query(int u)
{
make_root(u);
access(n + );
splay(n + );
return a[n + ].size - ;
}
inline void modify(int u , int val)
{
if (u + k[u] <= n) cut(u , u + k[u]);
else cut(u , n + );
if (u + val <= n) link(u , u + val);
else link(u , n + );
k[u] = val;
}
} LCT; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
} int main()
{ read(n);
LCT.init();
for (int i = ; i <= n; i++)
{
read(k[i]);
if (i + k[i] <= n) LCT.link(i , i + k[i]);
else LCT.link(i , n + );
}
int m;
read(m);
while (m--)
{
int type;
read(type);
if (type == )
{
int x;
read(x);
++x;
printf("%d\n" , LCT.query(x));
} else
{
int x , val;
read(x); read(val);
++x;
LCT.modify(x , val);
}
} return ; }

最新文章

  1. Android开发-之监听button点击事件
  2. Windows 搭建jdk、Tomcat、eclipse以及SVN、maven插件开发环境
  3. unity3D项目中如何避免硬代码(C#)
  4. 前端开发薪资之各地区对比(图文分析)(share)
  5. 嵌入式系统添加无线wifi模块
  6. [Voice communications] 让音乐响起来
  7. session机制详解以及session的相关应用
  8. C++语言-02-函数
  9. 01-事件处理简介/UIView拖拽
  10. 【CentOS】Eclipse中svn插件使用
  11. python学习笔记(三)--条件语句
  12. linux eval命令
  13. Windows phone 之样式的关联
  14. 转:Yelp开发团队发布内部网站设计指南
  15. 获得mysql内容,生成xml文件,另外,为了webservice发送
  16. 安装jar包到本地maven仓库
  17. Sqlserver 事务处理模板
  18. MQTT服务器的搭建(Windows平台)
  19. Mybatis优缺点
  20. python的序列化与反序列化

热门文章

  1. DICOM医学图像处理:Orthanc Plugin SDK实现WADO服务
  2. 权重轮询调度算法(WeightedRound-RobinScheduling)-Java实现
  3. NGUI版虚拟摇杆
  4. iOS开发 — (UINaVigationController)导航控制器,界面传值
  5. Python中的列表、元祖、字典
  6. [Maven实战](9)传递性依赖
  7. 【每日Scrum】第六天(4.27) TD学生助手Sprint2站立会议
  8. FALSE_IT
  9. 通过串口工具下发指令的Python脚本
  10. HDU 5336 XYZ and Drops 2015 Multi-University Training Contest 4 1010