首页 > 代码库 > Codeforces Round #425 (Div. 2) D 树链剖分 + 树状数组维护区间
Codeforces Round #425 (Div. 2) D 树链剖分 + 树状数组维护区间
一看就知道 可以LCA判断做 也可以树链剖分拿头暴力
然而快速读入和线段树维护区间会T70 于是只能LCA？
线段树的常数不小 于是需要另外一种办法来进行区间加减和查询区间和 就是使用树状数组
这个题的代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
#define pb push_back
int n , qn ;
vector<int > q [100050] ;
int top[100050] , fa[100050] , deep[100050] , num[100050] , p[100050] , fp[100050] , son[100050] , pos ;
inline int read()
{
int x=0;char ch=getchar();
while(ch<‘0‘||ch>‘9‘)ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
return x;
}
///----------
int c[100050] ;
int d[100050] ;
int lowbit(int x) {
return (x & (-x)) ;
}
void add(int c[] , int x ,int val) {
while(x <= n+5) {
c[x] += val ; x += lowbit(x) ;
}
}
int sum(int c[] , int x) {
int res = 0 ;
while(x > 0) {
res += c[x] ;
x -= lowbit(x) ;
}
return res ;
}
void add(int l , int r , int val) {
add(c , l , val) ; add(d , l , l * val) ;
add(c , r+1 , -val ) ; add(d , r + 1 , -val * (r+1)) ;
}
int sum(int x) {
return (x + 1) * sum(c , x) - sum(d , x) ;
}
int sum(int l , int r) {
return sum(r) - sum(l - 1) ;
}
///----------
void dfs1(int u , int pre , int d) {
deep[u] = d ;
fa[u] = pre ;
num[u] = 1 ;
for(int i = 0 ; i < q[u].size() ; i ++ ) {
int v = q[u][i] ;
if(v != pre) {
dfs1(v , u , d+1) ;
num[u] += num[v] ;
if(son[u] == -1 || num[v] > num[son[u]]) {
son[u] = v ;
}
}
}
}
void getpos(int u , int sp) {
top[u] = sp ;
p[u] = pos ++ ;
fp[p[u]] = u ;
if(son[u] == -1) return ;
getpos(son[u] , sp) ;
for(int i = 0 ; i < q[u].size() ; i ++ ) {
int v = q[u][i] ;
if(v != son[u] && v != fa[u]) {
getpos(v , v) ;
}
}
}
void chang(int u , int v , int val) {
int f1 = top[u] , f2 = top[v] ;
int tmp = 0 ;
while(f1 != f2) {
if(deep[f1] < deep[f2]) {
swap(f1 , f2) ; swap(u , v) ;
}
add(p[f1] , p[u] , val) ;
u = fa[f1] ;
f1 = top[u] ;
}
if(deep[u] > deep[v]) swap(u , v) ;
add(p[u] , p[v] , val) ;
}
int que(int u , int v) {
int f1 = top[u] , f2 = top[v] ;
int tmp = 0 ;
while(f1 != f2) {
if(deep[f1] < deep[f2]) {
swap(f1 , f2) ; swap(u , v) ;
}
tmp += sum(p[f1] , p[u]) ;
u = fa[f1] ;
f1 = top[u] ;
}
if(deep[u] > deep[v]) swap(u , v) ;
tmp += sum(p[u] , p[v]) ;
return tmp ;
}
int main () {
n = read() ;
qn = read() ;
for(int i = 2 ; i <= n ; i ++ ) {
int z ; z = read() ;
q[z].pb(i) ; q[i].pb(z) ;
}
memset(son , -1 , sizeof(son)) ;
pos = 1 ;
dfs1(1,0,0) ;
getpos(1 , 1) ;
while(qn -- ) {
int aa , bb , cc ;
aa = read() ; bb = read() ; cc = read() ;
int ans = 0 ;
chang(aa,bb,1) ;
ans = max(que(bb,cc) , ans) ;
chang(aa,bb,-1) ;
chang(aa,cc,1) ;
ans = max(que(bb,cc) , ans) ;
chang(aa,cc,-1) ;
chang(aa,bb,1) ;
ans = max(que(aa,cc) , ans) ;
chang(aa,bb,-1) ;
printf("%d\n" , ans) ;
}
}
其中的树状数组 拿两个数组来分别维护 具体代码
int c[100050] ;
int d[100050] ;
int lowbit(int x) {
return (x & (-x)) ;
}
void add(int c[] , int x ,int val) {
while(x <= n+5) {
c[x] += val ; x += lowbit(x) ;
}
}
int sum(int c[] , int x) {
int res = 0 ;
while(x > 0) {
res += c[x] ;
x -= lowbit(x) ;
}
return res ;
}
void add(int l , int r , int val) {
add(c , l , val) ; add(d , l , l * val) ;
add(c , r+1 , -val ) ; add(d , r + 1 , -val * (r+1)) ;
}
int sum(int x) {
return (x + 1) * sum(c , x) - sum(d , x) ;
}
int sum(int l , int r) {
return sum(r) - sum(l - 1) ;
}
树状数组天下无敌TAT 于是又上网学习了新姿势 我有姿势我自豪
树状数组单点修改 + 区间查询max
int num[5000] ;
int c[5000] ;
int n ;
int lowbit(int x)
{
return x & (-x);
}
void updata(int x)
{
int lx, i;
while (x <= n)
{
c[x] = num[x];
lx = lowbit(x);
for (i=1; i<lx; i<<=1)
c[x] = max(c[x], c[x-i]);
x += lowbit(x);
}
}
int query(int L, int R)
{
int ans = 0;
while (R >= L)
{
ans = max(num[R], ans);
R --;
for (; R-lowbit(R) >= L; R -= lowbit(R))
ans = max(c[R], ans);
}
return ans;
}
以及这里还有...矩形增减 + 矩形查询和的黑科技。。。
http://blog.csdn.net/lawrence_jang/article/details/8054173
Codeforces Round #425 (Div. 2) D 树链剖分 + 树状数组维护区间
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。