Qtree1
树剖裸题
注意把边权移到深度较深的点上，树剖跳的时候不要将LCA的答案统计上就行了
#include<stdio.h>
#include<string.h>
#define MAXN 100001
int read(){
;
;
char c = getchar();
while(!isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
];
void print(int x){
;
)
fwrite( , stdout);
else{
){
x = -x;
fwrite( , stdout);
}
while(x){
output[--dirN] = x % + ;
x /= ;
}
fwrite(output + dirN , , strlen(output + dirN) , stdout);
}
fwrite( , , stdout);
}
int max(int a , int b){
return a > b ? a : b;
}
struct node{
int l , r , maxN;
}Tree[MAXN << ];
struct Edge{
int end , upEd , w;
}Ed[MAXN << ];
] , size[MAXN] , son[MAXN] , fa[MAXN] , dep[MAXN];
, cntEd = , ts = ;
void addEd(int a , int b , int c){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
Ed[cntEd].w = c;
head[a] = cntEd;
}
void dfs1(int dir , int father , int w){
val[dir] = w;
dep[dir] = dep[fa[dir] = father] + ;
size[dir] = ;
int i;
for(i = head[dir] ; i ; i = Ed[i].upEd)
if(!dep[Ed[i].end]){
dfs1(Ed[i].end , dir , Ed[i].w);
size[dir] += size[Ed[i].end];
if(size[son[dir]] < size[Ed[i].end])
son[dir] = Ed[i].end;
}
}
void dfs2(int dir , int t){
top[dir] = t;
rk[ind[dir] = ++ts] = dir;
if(!son[dir])
return;
dfs2(son[dir] , t);
int i;
for(i = head[dir] ; i ; i = Ed[i].upEd)
if(Ed[i].end != fa[dir] && Ed[i].end != son[dir])
dfs2(Ed[i].end , Ed[i].end);
}
void pushup(int dir){
Tree[dir].maxN = max(Tree[dir << ].maxN , Tree[dir << | ].maxN);
}
void init(int dir , int l , int r){
Tree[dir].l = l;
Tree[dir].r = r;
if(l == r)
Tree[dir].maxN = val[rk[l]];
else{
init(dir << , l , l + r >> );
init(dir << | , (l + r >> ) + , r);
pushup(dir);
}
}
void change(int dir , int tar , int val){
if(Tree[dir].l == Tree[dir].r){
Tree[dir].maxN = val;
return;
}
>= tar)
change(dir << , tar , val);
else
change(dir << | , tar , val);
pushup(dir);
}
int findMax(int dir , int l , int r){
if(Tree[dir].l >= l && Tree[dir].r <= r)
return Tree[dir].maxN;
;
)
maxN = max(maxN , findMax(dir << , l , r));
)
maxN = max(maxN , findMax(dir << | , l , r));
return maxN;
}
void work(int x , int y){
if(x == y){
print();
return;
}
int tx = top[x] , ty = top[y] , maxN = -0x7fffffff;
while(tx != ty)
if(dep[tx] >= dep[ty]){
maxN = max(maxN , findMax( , ind[tx] , ind[x]));
x = fa[tx];
tx = top[x];
}
else{
maxN = max(maxN , findMax( , ind[ty] , ind[y]));
y = fa[ty];
ty = top[y];
}
if(ind[x] < ind[y])
maxN = max(maxN , findMax( , ind[x] + , ind[y]));
if(ind[y] < ind[x])
maxN = max(maxN , findMax( , ind[y] + , ind[x]));
print(maxN);
}
int cmp(int a , int b){
return dep[a] < dep[b] ? ind[b] : ind[a];
}
];
int main(){
N = read();
memset(head , , sizeof(head));
cntEd = ;
int i;
; i < N ; i++){
start[(i << ) - ] = read();
start[i << ] = read();
int c = read();
addEd(start[(i << ) - ] , start[i << ] , c);
addEd(start[i << ] , start[(i << ) - ] , c);
}
dfs1( , , );
dfs2( , );
init( , , N);
] != 'D'){
int a = read() , b = read();
] == 'Q')
work(a , b);
else
change( , cmp(start[a << ] , start[(a << ) - ]) , b);
}
;
}
Qtree1
Qtree2
倍增小水题
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
;
struct Edge{
int end , upEd , w;
}Ed[MAXN << ];
][] , head[MAXN] , dep[MAXN];
int N , cntEd;
inline void addEd(int a , int b , int c){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
Ed[cntEd].w = c;
head[a] = cntEd;
}
void dfs(int x , int f){
jump[x][][] = f;
dep[x] = dep[f] + ;
; jump[x][i - ][] ; ++i){
jump[x][i][] = jump[jump[x][i - ][]][i - ][];
jump[x][i][] = jump[x][i - ][] + jump[jump[x][i - ][]][i - ][];
}
for(int i = head[x] ; i ; i = Ed[i].upEd)
if(Ed[i].end != f){
jump[Ed[i].end][][] = Ed[i].w;
dfs(Ed[i].end , x);
}
}
inline pair < int , int > LCA(int x , int y){
;
if(dep[x] < dep[y])
swap(x , y);
; i >= ; --i)
<< i) >= dep[y]){
sum += jump[x][i][];
x = jump[x][i][];
}
if(x == y)
return make_pair(x , sum);
; i >= ; --i)
] != jump[y][i][]){
sum += jump[x][i][] + jump[y][i][];
x = jump[x][i][];
y = jump[y][i][];
}
][] , sum + jump[x][][] + jump[y][][]);
}
inline int Kth(int x , int y , int k){
int t = LCA(x , y).first;
>= k){
--k;
; i >= ; --i)
<< i))
x = jump[x][i][];
return x;
}
else{
k = dep[x] + dep[y] - (dep[t] << ) + - k;
; i >= ; --i)
<< i))
y = jump[y][i][];
return y;
}
}
inline char getc(){
char c = getchar();
while(!isupper(c))
c = getchar();
return c = getchar();
}
int main(){
for(int T = read() ; T ; --T){
memset(head , , sizeof(head));
memset(jump , , sizeof(jump));
cntEd = ;
N = read();
; i < N ; ++i){
int a = read() , b = read() , c = read();
addEd(a , b , c);
addEd(b , a , c);
}
dfs( , );
int a , b , c;
;
while(f)
switch(getc()){
case 'I':
printf("%d\n" , LCA(read() , read()).second);
break;
case 'T':
a = read();
b = read();
c = read();
printf("%d\n" , Kth(a , b , c));
break;
default:
f = ;
}
cout << endl;
}
;
}
Qtree2
Qtree3
树剖裸题+1
将对应白点的叶子节点的值设为INF，黑点的叶子节点的值设为自己的编号，线段树维护$min$即可
#include<bits/stdc++.h>
#define MAXN 100001
using namespace std;
namespace IO{
<< ) + );
, c, st[];
int f, tp;
char Getc() {
, maxn, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
}
void Flush() {
fwrite(obuf, , oS - obuf, stdout);
oS = obuf;
}
void Putc(char x) {
*oS++ = x;
if (oS == oT) Flush();
}
template <class Int> void Input(Int &x) {
, c = Getc(); c < : ;
; c <= ) + (x << ) + (c ^ );
x *= f;
}
template <class Int> void Print(Int x) {
');
) Putc('-'), x = -x;
+ ;
while (tp) Putc(st[tp--]);
}
void Getstr(char *s, int &l) {
for (c = Getc(); c < 'a' || c > 'z'; c = Getc());
; c <= 'z' && c >= 'a'; c = Getc()) s[l++] = c;
s[l] = ;
}
void Putstr(const char *s) {
, n = strlen(s); i < n; ++i) Putc(s[i]);
}
}
using namespace IO;
struct node{
int l , r , minN;
}Tree[MAXN << ];
struct Edge{
int end , upEd;
}Ed[MAXN << ];
int son[MAXN] , size[MAXN] , fa[MAXN] , dep[MAXN] , head[MAXN];
int top[MAXN] , ind[MAXN] , rk[MAXN] , N , cntEd , ts;
inline void addEd(int a , int b){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
head[a] = cntEd;
}
void dfs1(int dir , int father){
size[dir] = ;
dep[dir] = dep[fa[dir] = father] + ;
for(int i = head[dir] ; i ; i = Ed[i].upEd)
if(!dep[Ed[i].end]){
dfs1(Ed[i].end , dir);
size[dir] += size[Ed[i].end];
if(size[son[dir]] < size[Ed[i].end])
son[dir] = Ed[i].end;
}
}
void dfs2(int dir , int t){
top[dir] = t;
rk[ind[dir] = ++ts] = dir;
if(!son[dir])
return;
dfs2(son[dir] , t);
for(int i = head[dir] ; i ; i = Ed[i].upEd)
if(Ed[i].end != son[dir] && Ed[i].end != fa[dir])
dfs2(Ed[i].end , Ed[i].end);
}
inline int min(int a , int b){
return a < b ? a : b;
}
void init(int dir , int l , int r){
Tree[dir].l = l;
Tree[dir].r = r;
if(l == r)
Tree[dir].minN = ;
else{
init(dir << , l , (l + r) >> );
init(dir << | , ((l + r) >> ) + , r);
Tree[dir].minN = min(Tree[dir << ].minN , Tree[dir << | ].minN);
}
}
void change(int dir , int tar){
if(Tree[dir].l == Tree[dir].r){
Tree[dir].minN = Tree[dir].minN == ? Tree[dir].l : ;
return;
}
)
change(dir << , tar);
else
change(dir << | , tar);
Tree[dir].minN = min(Tree[dir << ].minN , Tree[dir << | ].minN);
}
int findMin(int dir , int l , int r){
if(Tree[dir].l >= l && Tree[dir].r <= r)
return Tree[dir].minN;
int minN;
){
minN = findMin(dir << , l , r);
)
return minN;
}
)
| , l , r);
;
}
inline int work(int tar){
;
){
minN = min(minN , findMin( , ind[top[tar]] , ind[tar]));
tar = fa[top[tar]];
}
minN = min(minN , findMin( , , ind[tar]));
? - : rk[minN];
}
int main(){
int N , M;
Input(N);
Input(M);
; i < N ; i++){
int a , b;
Input(a);
Input(b);
addEd(a , b);
addEd(b , a);
}
dfs1( , );
dfs2( , );
init( , , N);
while(M--){
int a;
Input(a);
){
Input(a);
change( , ind[a]);
}
else{
Input(a);
Print(work(a));
Putc('\n');
}
}
Flush();
;
}
Qtree3
Qtree4
点分树+堆，具体看这里
懒惰堆中$maintain$的时间改为询问之前$maintain$可以帮助卡常
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
;
struct Edge{
int end , upEd , w;
}Ed[MAXN << ];
] , dis[MAXN][] , dep[MAXN] , size[MAXN] , ST[][MAXN << ] , fir[MAXN] , logg2[MAXN << ] , l[MAXN];
int nowSize , minSize , minInd , ts , N , cntEd;
unsigned char vis[MAXN];
struct pq{
priority_queue < int > now , del;
inline void maintain(){
while(!del.empty() && del.top() == now.top()){
del.pop();
now.pop();
}
}
inline void push(int x){
now.push(x);
}
inline void pop(int x){
del.push(x);
}
inline int top(){
maintain();
return now.empty() ? -INF : now.top();
}
inline int sec(){
maintain();
if(now.empty())
return -INF;
int t = now.top();
now.pop();
maintain();
int p = now.empty() ? -INF : now.top();
now.push(t);
return p;
}
}ans , cur[MAXN] , ch[MAXN];
inline void addEd(int a , int b , int c){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
Ed[cntEd].w = c;
head[a] = cntEd;
}
void init_dfs(int now , int fa , int len){
fir[now] = ++ts;
ST[][ts] = now;
dep[now] = dep[fa] + ;
l[now] = len;
for(int i = head[now] ; i ; i = Ed[i].upEd)
if(Ed[i].end != fa){
init_dfs(Ed[i].end , now , len + Ed[i].w);
ST[][++ts] = now;
}
}
inline int cmp(int a , int b){
return dep[a] < dep[b] ? a : b;
}
inline void init_st(){
logg2[] = -;
; i <= N << ; ++i)
logg2[i] = logg2[i >> ] + ;
; << i <= N << ; ++i)
; j + ( << i) - <= N << ; ++j)
ST[i][j] = cmp(ST[i - ][j] , ST[i - ][j + ( << (i - ))]);
}
inline int LCA(int x , int y){
x = fir[x];
y = fir[y];
if(x < y)
swap(x , y);
];
<< t) + ]);
}
void getSize(int x){
vis[x] = ;
++nowSize;
for(int i = head[x] ; i ; i = Ed[i].upEd)
if(!vis[Ed[i].end])
getSize(Ed[i].end);
vis[x] = ;
}
void getRoot(int x){
vis[x] = size[x] = ;
;
for(int i = head[x] ; i ; i = Ed[i].upEd)
if(!vis[Ed[i].end]){
getRoot(Ed[i].end);
maxN = max(maxN , size[Ed[i].end]);
size[x] += size[Ed[i].end];
}
maxN = max(maxN , nowSize - size[x]);
if(maxN < minSize){
minSize = maxN;
minInd = x;
}
vis[x] = ;
}
inline int getLen(int x , int y){
);
}
int init_dfz(int x , int pre){
nowSize = ;
minSize = INF;
getSize(x);
getRoot(x);
x = minInd;
vis[x] = ;
fa[x][] = pre;
, p = x ; fa[x][i] ; p = fa[x][i++]){
dis[x][i] = getLen(x , fa[x][i]);
fa[x][i + ] = fa[fa[x][i]][];
ch[p].push(dis[x][i]);
}
for(int i = head[x] ; i ; i = Ed[i].upEd)
if(!vis[Ed[i].end])
cur[x].push(ch[init_dfz(Ed[i].end , x)].top());
cur[x].push();
cur[x].push();
ans.push(cur[x].top() + cur[x].sec());
vis[x] = ;
return x;
}
inline void init(){
init_dfs( , , );
init_st();
init_dfz( , );
}
inline void modify(int x){
vis[x] ^= ;
if(vis[x]){
ans.pop(cur[x].top() + cur[x].sec());
cur[x].pop();
cur[x].pop();
ans.push(cur[x].top() + cur[x].sec());
int p = x;
; fa[x][i] ; p = fa[x][i++]){
ans.pop(cur[fa[x][i]].top() + cur[fa[x][i]].sec());
cur[fa[x][i]].pop(ch[p].top());
ch[p].pop(dis[x][i]);
cur[fa[x][i]].push(ch[p].top());
ans.push(cur[fa[x][i]].top() + cur[fa[x][i]].sec());
}
}
else{
ans.pop(cur[x].top() + cur[x].sec());
cur[x].push();
cur[x].push();
ans.push(cur[x].top() + cur[x].sec());
int p = x;
; fa[x][i] ; p = fa[x][i++]){
ans.pop(cur[fa[x][i]].top() + cur[fa[x][i]].sec());
cur[fa[x][i]].pop(ch[p].top());
ch[p].push(dis[x][i]);
cur[fa[x][i]].push(ch[p].top());
ans.push(cur[fa[x][i]].top() + cur[fa[x][i]].sec());
}
}
}
inline void query(){
if(ans.top() <= -INF)
puts("They have disappeared.");
else
printf("%d\n" , ans.top());
}
inline char getc(){
char c = getchar();
while(!isupper(c))
c = getchar();
return c;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("4115.in" , "r" , stdin);
freopen("4115.out" , "w" , stdout);
#endif
N = read();
; i < N ; ++i){
int a = read() , b = read() , c = read();
addEd(a , b , c);
addEd(b , a , c);
}
init();
for(int M = read() ; M ; --M)
if(getc() == 'A')
query();
else
modify(read());
;
}
Qtree4
Qtree5
点分树+堆，与$Qtree4$类似
但是并不需要像$Qtree4$维护当前分治范围到父亲的堆，因为从子树中节点走到父亲再走到当前节点必定不优
#include<bits/stdc++.h>
#define INF (int)1e9
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
;
struct Edge{
int end , upEd;
}Ed[MAXN << ];
][MAXN << ] , logg2[MAXN << ] , fa[MAXN][] , size[MAXN] , dis[MAXN][];
int N , nowSize , minSize , minInd , cntST , cntEd;
bool vis[MAXN] , col[MAXN];
struct pq{
priority_queue < int , vector < int > , greater < int > > q1 , q2;
inline void maintain(){
while(!q1.empty() && !q2.empty() && q1.top() == q2.top()){
q1.pop();
q2.pop();
}
}
inline void push(int x){
q1.push(x);
}
inline void pop(int x){
q2.push(x);
}
inline int top(){
maintain();
return q1.empty() ? INF : q1.top();
}
}cur[MAXN];
inline void addEd(int a , int b){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
head[a] = cntEd;
}
void init_dfs(int x , int pre){
dep[x] = dep[pre] + ;
fir[x] = ++cntST;
ST[][cntST] = x;
for(int i = head[x] ; i ; i = Ed[i].upEd)
if(Ed[i].end != pre){
init_dfs(Ed[i].end , x);
ST[][++cntST] = x;
}
}
inline int cmp(int a , int b){
return dep[a] < dep[b] ? a : b;
}
void init_st(){
; i <= cntST ; ++i)
logg2[i] = logg2[i >> ] + ;
; << i <= cntST ; ++i)
; j + ( << i) - <= cntST ; ++j)
ST[i][j] = cmp(ST[i - ][j] , ST[i - ][j + ( << (i - ))]);
}
inline int LCA(int x , int y){
x = fir[x];
y = fir[y];
if(x > y)
swap(x , y);
];
<< t) + ]);
}
inline int calcLen(int x , int y){
);
}
void getSize(int x){
vis[x] = ;
++nowSize;
for(int i = head[x] ; i ; i = Ed[i].upEd)
if(!vis[Ed[i].end])
getSize(Ed[i].end);
vis[x] = ;
}
void getRoot(int x){
;
vis[x] = size[x] = ;
for(int i = head[x] ; i ; i = Ed[i].upEd)
if(!vis[Ed[i].end]){
getRoot(Ed[i].end);
size[x] += size[Ed[i].end];
maxN = max(maxN , size[Ed[i].end]);
}
maxN = max(maxN , nowSize - size[x]);
if(maxN < minSize){
minSize = maxN;
minInd = x;
}
vis[x] = ;
}
void init_dfz(int x , int p){
nowSize = ;
minSize = 0x7fffffff;
getSize(x);
getRoot(x);
x = minInd;
vis[x] = ;
fa[x][] = p;
; fa[x][i] ; ++i){
fa[x][i + ] = fa[fa[x][i]][];
dis[x][i] = calcLen(x , fa[x][i]);
}
for(int i = head[x] ; i ; i = Ed[i].upEd)
if(!vis[Ed[i].end])
init_dfz(Ed[i].end , x);
}
void init(){
init_dfs( , );
init_st();
init_dfz( , );
}
inline int query(int x){
int minN = cur[x].top();
; fa[x][i] ; ++i)
minN = min(minN , cur[fa[x][i]].top() + dis[x][i]);
: minN;
}
inline void modify(int x){
vis[x] ^= ;
vis[x] ? cur[x].pop() : cur[x].push();
; fa[x][i] ; ++i)
vis[x] ? cur[fa[x][i]].pop(dis[x][i]) : cur[fa[x][i]].push(dis[x][i]);
}
int main(){
N = read();
; i < N ; ++i){
int a = read() , b = read();
addEd(a , b);
addEd(b , a);
}
init();
for(int M = read() ; M ; --M)
if(read())
printf("%d\n" , query(read()));
else
modify(read());
;
}
Qtree5